0

我正在使用递归算法来列出数组 p = {1,2,3} 的元素的所有可能排列。以下是我正在使用的简单递归实现：

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

问题是我不想打印它们，而是想将每个排列添加到二维数组中。目前，我正在将排列打印到文件中，然后将其读取到二维数组中，但我认为应该有更好的方法来做到这一点。

4

4 回答 4

1

使用动态数组。幸运的是，您提前知道了数组的总大小：

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

您必须add_row准确地调用nf时间。在你的程序结束时，说free(array);。

数组的k第 th行包含array[k * n]最多的元素array[k * n + n]，从零开始并采用半开惯例。

于 2012-09-18T14:35:19.970 回答
1

将这些声明为全局：

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;

这填充二维数组：

void addToArray(int size){
    int i;
    for(i=0 ; i<size ; i++)
        resultArray[index][i] = array[i];
    index++;
}
于 2012-09-18T14:43:54.797 回答
0

由于您可以提前知道有多少排列（n!对于长度数组n），您可以预先创建此数组，然后将其传递给递归函数。可以给递归函数一个参数，告诉它它正在生成n'th排列，以便它在写入包含所有排列的数组时知道正确的索引。所以算法是这样的（前面的伪代码）：

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 );
}
于 2012-09-18T14:39:00.340 回答
0

我不确定我是否理解这个问题。只需创建一个数组或列表并直接从您的函数中引用它。就像您从任何其他函数访问数组或列表一样。

或者，您可以将数组或列表作为参数传递，并在每次再次递归调用该函数时传递该参数。

于 2012-09-18T14:30:52.090 回答