iterative permute function in C

user_8195968 0
Viewed 44

I'm trying to write an iterative function that computes all the permutations of an array of numbers given in input. Here is the code I've written so far.

void permute(int *a, int size){
  int j=0, i, h=0, m;
  bool flag=true;
  int f = factorial(size);
  int *arr, *res;
  int counter=0;

  arr = malloc(f*sizeof(int));
  

  for(i=0; i<f; i++)
    arr[i] = 0;

  while (j < f) {
    if(arr[j]<j)
    {
      if(j%2 == 0)
      {
        swap(a[0],a[j]);
      } else {
        swap(a[arr[j]], a[j]);
      }

      arr[j]++;

      j=0;
    } else{
      arr[j] = 0;
      j++;
    }
    printf("%d\n",a[j] );
    }
}

The code doesn't compute well all the permutations and goes into a long loop. Can someone help me, please? Thanks to everyone.

permutation iteration c
1 Answers

Your code is close but includes some problems. For instance, the while loop while (j < f) will assign j to a value out of bound of the array a. Instead would you please try:

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

int factorial(int x)
{
    int i;
    int y = 1;

    for (i = 1; i <= x; i++) {
        y *= i;
    }
    return y;
}

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

void permute(int *a, int size)
{
    int i, j = 0;
    int f = factorial(size);
    int *arr;

    arr = calloc(f, sizeof(int));       // the members are initialized to 0

    // print the original array
    for (i = 0; i < size; i++) {
        printf("%d%s", a[i], i == size - 1 ? "\n" : " ");
    }

    while (j < size) {
        if (arr[j] < j) {
            if (j % 2 == 0) {
                swap(a + 0, a + j);
            } else {
                swap(a + arr[j], a + j);
            }

            // print the rearranged array
            for (i = 0; i < size; i++) {
                printf("%d%s", a[i], i == size - 1 ? "\n" : " ");
            }

            arr[j]++;
            j = 0;
        } else {
            arr[j] = 0;
            j++;
        }
    }
    free(arr);
}

int main()
{
    int a[] = {1, 2, 3};                // example
    permute(a, sizeof a / sizeof a[0]); // the 2nd argument is the array length

    return 0;
}

Output of the example:

1 2 3
2 1 3
3 1 2
1 3 2
2 3 1
3 2 1
user_85723800
Related