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

Question

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; 
}

For starters, you can't store all permutations in a single output array, you need one array for each permutation. Secondly, it might be easier if you came up with an iterative algorithm instead of recursive. Thirdly, right now you swap around characters in the original array, instead of doing that write the characters to the corresponding places in the output array. Lastly, don't forget that strings in C are really called null-terminated byte strings, and that a string of four characters need space for five to include the terminator. — Some programmer dude
– Some programmer dude, Commented Sep 9, 2019 at 6:09

Rishikesh Raje · Accepted Answer · 2019-09-09 06:29:45Z

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

Mohit Jain · Accepted Answer · 2019-09-09 06:47:34Z

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; 
}

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related