C - Get all permutations of a string and assign a number to every character that repeats

Question

This has been a nightmare for me. I already managed to get the first part; get all permutations from a string thanks to this code (C language). It works!

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

/* Function to swap values at two pointers */
void swap(char *x, char *y) 
{ 
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 

/* Function to print permutations of string 
   This function takes three parameters: 
   1. String 
   2. Starting index of the string 
   3. Ending index of the string. */
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 
       } 
   } 
} 

/* Driver program to test above functions */
int main() 
{ 
    char str[] = "CASA"; 
    int n = strlen(str); 
    permute(str, 0, n-1); 
    return 0; 
} 

Now, how can I do the second part? I already output the 24 different permutations.

What needs to be done is, assign a number to each character that repeats. I haven't found a way to do this in C so far. For example, my output for the word "CASA" should be this. (it doesn't matter if the number is subscript or not by the way, I just want to identify which one is the first/second/third of the same character).

Answer 1

You can create an auxiliary data structure that represents your indexed letters, for example

struct tag {
    char str[4];
};

Now, instead of permuting your string directly, you can create a tag for each letter and permute that:

void swap(struct tag *a, int i, int j) 
{
    struct tag temp = a[i]; a[i] = a[j]; a[j] = temp;
} 

void do_permute(struct tag *tag, int lo, int hi) 
{
    if (lo == hi) { 
        for (int i = 0; i < hi; i++) {
            if (i) printf(" ");
            printf("%s", tag[i].str);
        }

        printf("\n"); 
    } else { 
        for (int i = lo; i < hi; i++) { 
            swap(tag, lo, i); 
            do_permute(tag, lo + 1, hi); 
            swap(tag, lo, i); 
       } 
    } 
}

This is more or less your original function, but I've taken the liberty of making the upper bound exclusive, as is usual in C. (I'm always a bit uneasy when I see <='s in for loop conditions.)

Of course, you must create the tags. You can do this in a front-end function to the back-end above. This function should also determine the length of the string. You can create your tags in two steps:

• Keep a count of all individual characters. Assign an index to each letter.
• In a second pass, remove the number from each letter that ocurs only once.

Now you're good to go:

void permute(const char *str)
{
    int l = strlen(str);
    struct tag *tag = malloc(l * sizeof(*tag));
    int count[256] = {0};

    // first pass: assign individual indices for each letter

    for (int i = 0; i < l; i++) {
        unsigned char k = str[i];

        count[k]++;
        snprintf(tag[i].str, sizeof(tag[i].str), "%c%d", str[i], count[k]);
    }

    // second pass: remove index for single instances

    for (int i = 0; i < l; i++) {
        unsigned char k = str[i];

        if (count[k] == 1) tag[i].str[1] = '\0';
    }

    do_permute(tag, 0, l);

    free(tag);
}

Now permute("CASA") will write a list of indexed permutations. (But note how you can pass a string literal – the string is not changed in any way while permuting.)

See everything put together in an example here.