2

次の順序で、n 桁の数値のすべての可能な値を生成しようとしています。ここで、シーケンスは個々の数字の合計によって決定されます。

たとえば、次の場合n = 3:

111     sum = 3
112     sum = 4
121
211
122     sum = 5
212
221
113
131
311
114     sum = 6
141
411
:::
999     sum = 27

合計グループ内の順序は重要ではありません。

どんな助け、アイデアもいただければ幸いです

4

4 に答える 4

6

重要なデータの独自のスタックを維持している場合は、いつでも再帰問題を反復問題に変えることができます。これは、再帰を回避する理由が言語でサポートされていない場合です。

しかし、言語がそれをサポートしている場合、再帰的なソリューションははるかに洗練されています。

再帰を避けるために私が考えることができる他の唯一の理由は、スタックの深さが限られていることです。その場合、再帰的なソリューションの反復変換により、必要なスタック スペースが少なくなるため、問題が軽減されます。

ただし、n 個の数値を処理するためのスタックの深さは、log 10 nに対してのみ増加することを理解する必要があります。つまり、桁ごとに余分なスタック フレームしか得られません (32 ビット整数の全範囲を処理するには、10 個のスタック フレームしかありません)。

余談ですが、その時点に到達するまでに、アルゴリズムの実行に非常に時間がかかり、スタックフレームの問題が最も少なくなります:-)

再帰的な Python ソリューションは次のとおりです。

def recur (numdigits,sum,pref="",prefsum=0):
    if numdigits == 0:
        if prefsum == sum:
            print "%s, sum=%d"%(pref,prefsum)
    else:
        for i in range (1,10):
            recur (numdigits-1,sum,"%s%d"%(pref,i),prefsum+i)

def do (n):
    for i in range (1,n*9+1):
        recur (n,i)

do (2)
do (3)

出力するもの (2 と 3 の場合):

11, sum=2          111, sum=3
12, sum=3          112, sum=4
21, sum=3          121, sum=4
13, sum=4          211, sum=4
22, sum=4          113, sum=5
31, sum=4          122, sum=5
14, sum=5          131, sum=5
23, sum=5          212, sum=5
32, sum=5          221, sum=5
41, sum=5          311, sum=5
15, sum=6          114, sum=6
 :    :             :     :
89, sum=17         989, sum=26
98, sum=17         998, sum=26
99, sum=18         999, sum=27

ソリューションはまだいくらか最適化される可能性があることに注意してください。再帰がいかにエレガントであるかを示すために、最初の形式のままにしました。純粋な反復ソリューションが続きますが、私はまだ再帰的なソリューションを好みます。

次のプログラムを実行し、UNIX で と を使用して、目的の順序を取得しますsort。awk例えば：

go | sort | awk '{print $2}'

これは外部ツールを使用してソートを行いますが、C コード内で簡単にソートすることもできます (メモリが許す限り)。

#include <stdio.h>

int main (void) {
    int i, sum, carry, size;
    int *pDigit;

    // Choose your desired size.

    size = 2;

    // Allocate and initialise digits.

    if ((pDigit = malloc (size * sizeof (int))) == NULL) {
        fprintf (stderr, "No memory\n");
        return 1;
    )

    for (i = 0; i < size; i++)
        pDigit[i] = 1;

    // Loop until overflow.

    carry = 0;
    while (carry != 1) {
        // Work out sum, then output it with number.
        // Line is sssssssssssssssssss ddddd
        //   where sss...sss is the fixed-width sum, zero padded on left (for sort)
        //   and ddd...ddd is the actual number.

        sum = 0;
        for (i = 0; i < size; i++)
            sum += pDigit[i];

        printf ("%020d ", sum);
        for (i = 0; i < size; i++)
            printf ("%d", pDigit[i]);
        printf ("\n");

        // Advance to next number.

        carry = 1;
        for (i = 0; i < size; i++) {
            pDigit[size-i-1] = pDigit[size-i-1] + carry;
            if (pDigit[size-i-1] == 10)
                pDigit[size-i-1] = 1;
            else
                carry = 0;
        }
    }

    return 0;
}
于 2009-11-11T14:01:26.900 に答える
4

std::next_permutationを使用できますか?

next_permutation() 関数は、指定された範囲の要素 [start,end) を、次の辞書編集的に大きな要素順列に変換しようとします。成功した場合は true を返し、それ以外の場合は false を返します。

厳密な弱い順序付け関数オブジェクト cmp が提供されている場合、要素を比較するときに < 演算子の代わりに使用されます。

これを参照してください：以前のSOの回答

于 2009-11-11T14:02:41.280 に答える
0

パターンがある限りどのパターンを使用してもかまわない場合 (特定のパターンを念頭に置いているかどうかは投稿から完全には明らかではありません)、n=3 の場合、 から始めて111に達するまで増やします999。

ところで、あなたが求めている用語は正確には「順列」ではありません。

于 2009-11-11T14:12:46.987 に答える
0

問題を 2 つのバケットに減らすことができます。

2 つのバケット分割は単純です。バケット A のマイナス 1 とバケット B のマイナス 1 から始めて、A が 1 つだけになるまで、A から B に 1 つを入れます。

3 つのバケット分割は次のとおりです。バケット A ですべてマイナス 2、B と C でそれぞれ 1 つから始めます。A を 1 減らし、B と C で 3 つの 2 つのバケット分割すべてを収集し、A が 1 つだけになるまで繰り返します。

于 2009-11-11T16:16:07.973 に答える