0

5つの要素を持つ配列があるとしましょう。Cでこの配列のすべての可能な反復順列を計算するにはどうすればよいですか。

編集：私が言いたいのは、その5つの数字を使用してすべての可能な配列を作成することです。したがって、位置が重要です。

例：

array = [1,2,3,4,5]

[1,1,1,1,1]
[1,1,1,1,2]
[1,1,1,2,3]
.
.
4

4 に答える 4

4

組み合わせまたは順列を生成する一般的な方法は、再帰を使用することです。最初の要素の可能性のそれぞれを列挙し、1つの要素を減らした同じセットの組み合わせまたは順列のそれぞれにそれらを追加します。したがって、一度にk個取られるn個の順列の数を探していると言い、perms（n、k）という表記を使用すると、次のようになります。

perms(5,5) = {
    [1, perms(5,4)]
    [2, perms(5,4)]
    [3, perms(5,4)]
    [4, perms(5,4)]
    [5, perms(5,4)]
}

同様に、perms（5,4）の場合、次のようになります。

perms(5,4) = {
    [1, perms(5,3)]
    [2, perms(5,3)]
    [3, perms(5,3)]
    [4, perms(5,3)]
    [5, perms(5,3)]
}

したがって、perms（5,5）の一部は次のようになります。

[1, 1, perms(5,3)]
[1, 2, perms(5,3)]
[1, 3, perms(5,3)]
[1, 4, perms(5,3)]
[1, 5, perms(5,3)]
[2, 1, perms(5,3)]
[2, 2, perms(5,3)]
...

perms（n、k）の定義は簡単です。再帰的定義に関しては、基本ケースと再帰ステップの2つが必要です。基本的なケースは、k = 0の場合です。perms（n、0）は空の配列[]です。再帰的なステップでは、perms（ n、k -1）のすべての要素の前に、セット内の可能な値のそれぞれを付加することによって要素を生成します。

于 2013-01-04T15:44:59.017 に答える
3

質問が正しければ、1、2、3、4、5の数字で5桁の数字をすべて生成する必要があります。したがって、簡単な解決策があります。基数5から1までのすべての数字を生成し44444、0を1、1にマップします。 2などに。必要に応じて先行ゼロを追加します-またはに10なります。00010[1,1,1,2,1]

注：実際に数字を生成する必要はありません。5 ** 5（を除く）までの数字を繰り返すだけで、それぞれの数字を5進数で取得して、対応するシーケンスを見つけることができます。

于 2013-01-04T15:42:31.467 に答える
2

与えられた例では、各位置は、、、、、のいずれか1で占められている可能性があります。5つのポジションがあるため、可能性の総数= 。一般的には、です。（ここで、^はべき乗演算子です）。23455 * 5 * 5 * 5 * 5 = 5 ^ 5 = 3125N ^ N

これらの可能性を生み出すには、各位置に、、、、、、の数字を1つずつ入れ、152桁のカウンターと同様に、最後の位置から増分します。 345

したがって、から始め11111ます。最後の位置をインクリメントして11112...を取得します11115。次に、に折り返し1、次の桁をインクリメントして...など11121を続けます。最初の位置に到達するまでこれを繰り返し、で終了します。111221112555555

于 2013-01-04T15:43:39.430 に答える
2 
int increment(size_t *dst, size_t len, size_t base) {
    if (len == 0) return 0;
    if (dst[len-1] != base-1) {
        ++dst[len-1];
        return 1;
    } else {
        dst[len-1] = 0;
        return increment(dst, len-1, base);
    }
}

この関数を使用すると、から始まる（0 ... 4）のすべての反復順列を反復処理できます{0, 0, 0, 0, 0}。関数は、繰り返しの順列がなくなると0を返します。

次に、反復順列ごとに、コンテンツを配列へのインデックスとして使用して、（0 ... 4）ではなく配列の反復順列を取得します。

于 2013-01-04T15:48:02.030 に答える