C 中的迭代置换函数

Question

我正在尝试编写一个迭代函数来计算输入中给定的数字数组的所有排列。这是我到目前为止编写的代码。

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

该代码未能很好地计算所有排列并进入一个长循环。有谁可以帮助我吗？谢谢大家。

Answer 1

您的代码很接近，但包含一些问题。例如，while 循环 while (j < f) 会将 j 赋值给超出数组 a 范围的值。相反，请尝试：

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

示例输出：

C 中的迭代置换函数

iterative permute function in C

c

iteration

permutation