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

問題は、それらを印刷する代わりに、すべての順列を2D配列に追加したいということです。現在、順列をファイルに出力してから2D配列に読み取っていますが、これを行うにはもっと良い方法があるはずです。

4

4 に答える 4

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;

これは、2次元配列を埋めるためのものです。

void addToArray(int size){
    int i;
    for(i=0 ; i<size ; i++)
        resultArray[index][i] = array[i];
    index++;
}
于 2012-09-18T14:43:54.797 に答える
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);ます。

配列のk3番目の行は、ゼロベースでハーフオープンの規則array[k * n]までの要素で構成されます。array[k * n + n]

于 2012-09-18T14:35:19.970 に答える
0

問題を理解できるかわかりません。配列またはリストを作成し、関数から直接参照するだけです。他の関数から配列またはリストにアクセスするのと同じように。

または、配列またはリストを引数として渡し、関数を再度再帰的に呼び出すたびにその引数を渡すこともできます。

于 2012-09-18T14:30:52.090 に答える
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 に答える