CODEWITHSUNDEEP
calgorithmcombinationspermutation
Biminha123
Biminha123

Reputation: 3

Char permutation algorithm in C that stores the output in an array

I need to store the permutations of four letters in C i was trying to use this algorithm but no idea how to store the output in some array if someone can correct this for me or give another algorithm i would appreciate

#include <stdio.h> 
#include <string.h> 


void swap(char* x, char* y) 
{ 
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 


void permute(char* a, int l, int r) 
{ 
    int i; 
    if (l == r) 
        printf("%s\n", a); 
    else { 
        for (i = l; i <= r; i++) { 
            swap((a + l), (a + i)); 
            permute(a, l + 1, r); 
            swap((a + l), (a + i)); // backtrack 
        } 
    } 
} 

int main() 
{ 
    char str[] = "AGTC"; 
    int n = strlen(str); 
    permute(str, 0, n - 1); 
    return 0; 
}

Upvotes: 0

Views: 1011

Answers (2)

Mohit Jain
Mohit Jain

Reputation: 280

You could do it by using malloc. For this you need to know the number of combinations. Combination would be factorial of size of string given.

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 


void swap(char* x, char* y) 
{ 
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 


void permute(char* a, int l, int r, char arr[], int n) 
{ 
    int i;
    static long count = 0;
    if (l == r) 
    {
        //printf("%s\n", a);
        memcpy(arr+count*n, a, n);
        count++;
    }
    else { 
        for (i = l; i <= r; i++) { 
            swap((a + l), (a + i)); 
            permute(a, l + 1, r, arr, n); 
            swap((a + l), (a + i)); // backtrack 
        } 
    } 
} 

long factorial(int n)
{
   int c = 0;
   long fact = 1;
   for (c = 1; c <= n; c++)
       fact = fact * c;

   return fact;
}

int main() 
{ 
    char str[] = "AGTC"; 
    int n = strlen(str);
    long t_comb = factorial(n);

    char *arr = NULL;
    char *print = NULL;

    arr = (char *)malloc(t_comb * n);
    if(arr == NULL)
    {
      printf("error\n");
    }

    print = (char *)malloc(n+1);
    memset(print, '\0', n+1);

    permute(str, 0, n - 1, arr, n); 
    long itr = 0;
    for(itr = 0 ; itr < t_comb ; itr++)
    {
        memcpy(print, arr+itr*n, n);
        printf("%s\n", print);
    }

    /* After using */
    free(print);
    free(arr);

    return 0; 
}

Upvotes: 0

Rishikesh Raje
Rishikesh Raje

Reputation: 8614

You should note that you will require quite a large size array to store all the permutations. If you have a 4 byte string, this will be a 2D array of 24*5. So this is only practical if you know ahead of time the max size of the string you want to support.

The code below works for max 4 byte strings. For higher size, you need to increase both the dimensions of the 2D array storage. e.g. for 5 byte it will be 120*6

// global
char store[24][5];

void permute(char* a, int l, int r) 
{ 
    int i;
    static int storeindex;
    if (l == r) 
    {
        strcpy(store[storeindex++],a);
    }        
    else { 
        for (i = l; i <= r; i++) { 
            swap((a + l), (a + i)); 
            permute(a, l + 1, r); 
            swap((a + l), (a + i)); // backtrack 
        } 
    } 
}

Additional note - The algorithm given above does not print distinct permutations. If the input string has duplicates, this algorithm will print permutations with duplicates. e.g. if input is AAAA output is 24 lines of AAAA

Upvotes: 1

Related Questions