Permutation of char array In C

Question

I have been working on an algorithm to find all permutations of the elements of a char array for a few days now and well it just doesn't seem to work.

The char array is an **array, which I iterate through based on the number entered by the user and I then malloc space for each word(40 chars each). The number entered by the user is the length of the array, and it is the number they expect to enter. This part works as expected.

What I am having trouble with is iterating through the char array and calculating the permutation of the entire set(**array). I then want to have another char array consisting of all permutations of the set. Now just permutations of the unit indices's of **array, not each indices's individual characters.

Does anybody have any tips on how to successfully do this, regardless of the size of the initial set? I assume it would be much easier if the set size where static.

My starting array looks like this as an example

char *array[] = {
    "Hello",
    "Calculator",
    "Pencil",
    "School Bus"
};

Which would be held in **array, with "Hello" in array[0] and "School Bus" in array[3], with '\0' at the end of each.

I want the permutation to be on the indices, not the characters.

So

"Hello"

.

.

.

"School BusSchool BusSchool BusSchool Bus"

Answer 1

here my code that give us the r-permutation of a n! possible permutations. Code works with all kind of size (I only check with 3!, 4!, 5! and 8! and always works correct, so I suppouse that works right):

#include <stdio.h>
#include <stdint.h>


enum { NPER = 4, };

static const char *DukeQuote[NPER] = { 
    "Shake it, baby!",
    "You wanna dance?",
    "Suck it down!",
    "Let's rock!",
};

void fill(const uint32_t, uint32_t * const);
void fact(const uint32_t, uint32_t * const);
void perm(uint32_t, const uint32_t, const uint32_t * const, uint32_t * const);


int main(void)
{
  uint32_t f[NPER+1];
  uint32_t p[NPER];
  uint32_t r, s;

  /* Generate look-up table for NPER! factorial */
  fact(NPER, f);

  /* Show all string permutations */
  for(r = 0; r < f[NPER]; r++)
  {
    perm(r, NPER, f, p);

    for(s = 0; s < NPER; s++)
      printf("%s, ", DukeQuote[p[s]]);
    printf("\n");
  }

  return 0;
}

/* Generate look-up table for n! factorial. 
That's a trick to improve execution */
void fact(const uint32_t n, uint32_t * const f)
{
  uint32_t k;

  for(f[0] = 1, k = 1; k <= n; k++)
    f[k] = f[k-1] * k;
}

/* Fill the vector starting to 0 up to n-1 */
void fill(const uint32_t n, uint32_t * const p)
{
  uint32_t i;

  for(i = 0; i < n; i++)
    p[i] = i;
}

/* Give us the r-permutation of n! possible permutations.
r-permutation will be inside p vector */
void perm(uint32_t r, const uint32_t n, const uint32_t * const f, uint32_t * const p)
{
  uint32_t i, j;

  fill(n, p);

  for(i = n-1; i > 0; i--)
  {
    uint32_t s;

    j = r / f[i];
    r %= f[i];
    s = p[j];

    for(; j < i; j++) 
      p[j] = p[j+1];
    p[i] = s;
  }

}

For instance, if you want the first permutation of 4! possibles then:

perm(0, 4, f, p)

where p will have:

p = [3, 2, 1, 0]

Take care, 0 is 1th, 1 is 2th, and so on.

You can use p[i] like indices in your string array, how I've used in DukeQuote array.

PD1: This code implements the correct definition of a permutation (A r-permutation is a bijection. The cardinal of the set of all bijections N_n to N_n is exactly n!)

PD2: I hope that my mistakes in my poor English doesn't influence in the goal of my explanation.

Answer 2

Here's one solution. Remember that the time complexity is factorial, and that if you're storing all the permutations then the space required is also factorial. You're not going to be able to do very many strings.

void CalculatePermutations(unsigned long permSize, const char** candidates, const char** currentPerm, unsigned long currentPermIdx, const char** ouputBuffer, unsigned long* nextOutputIdx)
{
    //base case (found a single permutation)
    if(currentPermIdx >= permSize){
        unsigned long i = 0;
        for(i = 0; i < permSize; ++i){
            ouputBuffer[*nextOutputIdx] = currentPerm[i];
            (*nextOutputIdx)++;
        }
        return;
    }

    //recursive case
    unsigned long i = 0;
    for(i = 0; i < permSize; ++i){
        if(candidates[i]){
            currentPerm[currentPermIdx] = candidates[i]; //choose this candidate
            candidates[i] = NULL; //mark as no longer a candidate
            CalculatePermutations(permSize, candidates, currentPerm, currentPermIdx + 1, ouputBuffer, nextOutputIdx);
            candidates[i] = currentPerm[currentPermIdx]; //restore this as a possible candidate
        }
    }
}

int main(int argc, char** argv)
{
    const char* allStrings[8] = {"0", "1", "2", "3", "4", "5", "6", "7"};
    static const char* allPermutations[322560]; // = fact(8) * 8
    const char* permBuffer[8];
    unsigned long nextOutputIdx = 0;

    CalculatePermutations(8, allStrings, permBuffer, 0, allPermutations, &nextOutputIdx);

    for(unsigned long i = 0; i < 322560; ++i){
        printf("%s", allPermutations[i]);
        if(i % 8 == 7){
            printf("\n");
        } else {
            printf(", ");
        }
    }

    return 0;
}

Answer 3

By your edit, I am taking that you have an array of four elements. Your desired output is a combination of these elements and is the concatenation of between one and four elements. The output may contain an input element more than once. Is this a correct summary?

If so, think of your output in four cases: for output generated from one, two, three, or four elements. For output generated from n elements, you have n^n possibilities. For all four of these cases combined, this gives you 1^1 + 2^2 + 3^3 + 4^4 = 288 possible outputs.

Your 1-element output permutations are simply: 0, 1, 2, 3

Your 2-element output permutations can be generated by the pseudo-code:

for i = 0 to 3 {
    for j = 0 to 3 {
        next_permutation = {i, j}
    }
}

For 3- and 4-element output, permutations can be generated using three and four nested loops, respectively. For some arbitrary number of input elements x, you can generate permutations using the same technique with x number of nested loops. Be warned that the number of loops requires grows exponentially with the number of input elements, so this can get ugly fairly fast.

You can use the numbers from these permutations as indices into your initial array in order to generate the output as strings (as in your sample).

Update: Here's a recursive pseudo-code function that can generate these pseudo-permutations:

int output_array[dimension] = {0};
generate_combinations (unsigned dimension, int index) {
    for i = 0 to (dimension-1) {
        output_array[index] = i;
        if index == 0
            next_permutation = output_array
        else
            generate_combinations(dimension, index-1)
        endif
    }
}

You would use this with dimension set to the number of elements in your input array and index = dimension - 1. Hopefully, your input dimensionality won't be so large that this will recurse too deeply for your CPU to handle.

Answer 4

Here's a dumb permutation generator (up to N=32... or 64).

#include <stdio.h>

const int N = 5;
int x[N];

int main( void ) {

  int i,j;

  x[0]=-1;
  unsigned mask = -1; // unused numbers

  for( i=0;; ) {
    for( j=x[i]+1; j<N; j++ ) { // check remaining numbers
      if( (mask>>j)&1 ) { // bit j is 1 -> not used yet
        x[i] = j; // store the number
        mask ^= (1<<x[i]); // mask used
        // try going further, or print the permutation
        if( ++i>=N ) { for( j=0; j<N; j++ ) printf( "%3i", x[j] ); printf( "\n" ); }
          else x[i]=-1; // start next cell from 0
        break;
      }
    }
    // go back if there's no more numbers or cells
    if( (j>=N) || (i>=N) ) {
      if( --i<0 ) break;
      mask ^= (1<<x[i]); 
    }
  }

}