How to add results to an array in a recursive algorithm?

Question

I am using a recursive algorithm to list all possible permutations of elements of an array p = {1,2,3}. Following is the simple recursive implementation I am using:

void swap(int x, int y){
    int temp = array[x];
    array[x]=array[y];
    array[y]=temp;    
    return;
}

void printArray(int size){
    int i;

    for (i=0;i<size;i++)
        printf("%d ", array[i]);

    printf("\n");    
    return;
}

void permute(int k,int size){
    int i;

    if (k==0)
        printArray(size);
    else{
        for (i=k-1;i>=0;i--){
            swap(i,k-1);
            permute(k-1,size);
            swap(i,k-1);
        }
    }    
    return;
}

The problem is instead of printing them I want to add every permutation to a 2D array. Currently, I am printing the permutations to a file and then reading it to a 2D array, but I think there should be a better way to do this.

score 1 · Answer 1 · answered Sep 18 '12 at 14:35

Use a dynamic array. Thankfully, you know the total size of the array in advance:

size_t const n = 3;             //  array size, e.g. [ 0, 1, 2 ]

size_t const nf = factorial(n); //  number of permutations

int * array = malloc(nf * n * sizeof *array);  // space for a flat array of n*nf
size_t  cur = 0;                               // current row

void add_row(int * src)
{
    for (size_t i = 0; i != n; ++i)
    {
        array[cur * n + i] = src[i];
    }
    ++cur;
}

You must call add_row exactly nf times. At the end of your program, say free(array);.

The k^th row of the array comprises elements array[k * n] up to array[k * n + n], zero-based and in half-open convention.

score 1 · Accepted Answer · answered Sep 18 '12 at 14:43

1

declaring these as global:

int **resultArray;
resultArray = malloc( (n!) * sizeof(int *));    // n! : factorial of n
for(i=0; i<(n!); i++)
    resultArray[i] = malloc(size * sizeof(int));
int index = 0;

this to fill in the 2 dimensional array:

void addToArray(int size){
    int i;
    for(i=0 ; i<size ; i++)
        resultArray[index][i] = array[i];
    index++;
}

answered Sep 18 '12 at 14:43

Rami Jarrar

4,523
7
36
52

Please note that `n!` is not valid C code, you have to create a function that calculates the factorial of n. Also please [allocate 2D arrays properly](http://stackoverflow.com/questions/12462615/how-do-i-correctly-set-up-access-and-free-a-multidimensional-array-in-c). – Lundin Sep 18 '12 at 14:55
aha,, that's why i added a comment that its the factorial of n beside it :),, and thnx for the 2D declaration :) – Rami Jarrar Sep 18 '12 at 15:00

score 0 · Answer 3 · answered Sep 18 '12 at 14:30

I'm not sure I understand the problem. Just create an array or list and reference it directly from your function. Just like you'd access the array or list from any other function.

Alternatively, you could pass the array or list as an argument, and just pass that argument each time you recursively call the function again.

score 0 · Answer 4 · answered Sep 18 '12 at 14:39

Since you can tell how many permutations there are in advance (n! for an array of length n) you could create this array up front and then pass it to the recursive function. The recursive function could be given an argument telling it that it's generating the n'th permutation, so that it knows the correct index when writing into the array containing all permutations. So the algorithm goes like this (pseudo-code ahead):

void doPermute( array, arrayLen, n, permutations ) {
  if ( n < fact(arrayLen) ) {
    /* At this point, generate permutation of array and write it to
     * permutations[n].
     */

    /* Recurse, generating next permutation. */
    doPermute( array, arrayLen, n + 1, permute );
  }
}

int **permute( array, arrayLen ) {
  /* Allocate an array big enough to hold `arrayLen!` versions of the input
   * array.
   */
  int **permutations = malloc( fact( arrayLen ) * (sizeof(int) * arrayLen) );

  /* Invoke recursion */
  doPermute( array, arrayLen, 0, permutations );
}

How to add results to an array in a recursive algorithm?

4 Answers4