3

長さNの自然数ベクトル と エントリの合計Sを扱います。ベクトル内で> 0と見なされます。

同じ構成(N,S)=(4,7)のすべてのベクトルをリストしたいのですが、回転は除外する必要があります。

質問:最適なアルゴリズムは何ですか?
(私の実際の実装は、下限と上限のインデックス値の境界のベクトルを使用してネストされた for ループを提供する Pari/GP にあります)

ネストされたforループを使用してリストを生成するという点で、最初に「ブルートフォース」ソリューションを試しましたが、連結された2重のconcat(E,E)をリストEE[]に保存し、次に、それぞれに対して新しいベクトルE=[e_1,e_2,e_3,e_4]このベクトルが既にチェックされたリストEE[]の連結されたベクトルにあるかどうかをチェックし、そうでない場合は新しい有効なエントリ
EE[k]=E||Eとして追加します= [e_1,e_2,e_3,e_4,e_1,e_2,e_3,e_4] . ここでの比較は、文字列の比較に似ています。一致は、位置1または最大Nから始まる場合に常に見つかります。

この方法は機能しますが、私にはブルートフォースのように見え、その組み合わせ構造により、NとSが増加すると爆発します。

より良い方法はありますか？

注: ターゲット言語はPari/GP
注: 疑似アルゴリズムで十分ですが、おそらく Pari/GP のツールを使用すると、よりコンパクトなソリューション/表記が可能になります。

例、(N,S)=(4,7)
以下は非常に単純な例です。

ネストされたループによって、次の方法でベクトルEを取得すると仮定します。

[1,1,1,4] --- first vector: store as [1,1,1,4;1,1,1,4] in EE
[1,1,2,3] --- 2nd vector: not in EE so far, append as [1,1,2,3;1,1,2,3] to EE
[1,2,1,3] ...
[2,1,1,3] ...
[1,1,3,2] --- ignore!! This is a rotation of an earlier entry (is in EE)
[1,2,2,2] 
...

これにより、ベクトルEEのリストが連続して作成されます。

[1,1,1,4;1,1,1,4]
[1,1,2,3;1,1,2,3]
[1,2,1,3;1,2,1,3]
[2,1,1,3;2,1,1,3]
[1,2,2,2;1,2,2,2]

このリストは最初のN列のみで、後で使用するベクトルのリストです。

追加の健全性チェック: for (N,S)=(4,16) フィルター処理されていないリストlength_unfiltered = 455と、回転が削除された後のlength_filtered=116を取得します。

4

2 に答える 2

0

これはアンドリューの回答に対する単なるコメントであり、「回答」ではありませんが、コメント ボックスには長すぎます。

Andrew のルーチンにより、小さな(N,S)=(2,2)から(16,16)までのフィルター処理されたバージョンの統計をすばやく作成できました。これまでに見たことのない組み合わせ三角形の数値が得られます。(おそらく最初の列は 1 で埋める必要があります)
おそらく OEIS にエントリする価値があります... - まあ、それはOEISにあります :-)

私が得た：

       1  2   3    4    5    6    7    8    9   10   11   12  13 14 15 16 -> N
 --+----------------------------------------------------------------------
 1 |   0  .   .    .    .    .    .    .    .    .    .    .   .  .  .  .
 2 |   0  1   .    .    .    .    .    .    .    .    .    .   .  .  .  .
 3 |   0  1   1    .    .    .    .    .    .    .    .    .   .  .  .  .
 4 |   0  2   1    1    .    .    .    .    .    .    .    .   .  .  .  .
 5 |   0  2   2    1    1    .    .    .    .    .    .    .   .  .  .  .
 6 |   0  3   4    3    1    1    .    .    .    .    .    .   .  .  .  .
 7 |   0  3   5    5    3    1    1    .    .    .    .    .   .  .  .  .
 8 |   0  4   7   10    7    4    1    1    .    .    .    .   .  .  .  .
 9 |   0  4  10   14   14   10    4    1    1    .    .    .   .  .  .  .
10 |   0  5  12   22   26   22   12    5    1    1    .    .   .  .  .  .
11 |   0  5  15   30   42   42   30   15    5    1    1    .   .  .  .  .
12 |   0  6  19   43   66   80   66   43   19    6    1    1   .  .  .  .
13 |   0  6  22   55   99  132  132   99   55   22    6    1   1  .  .  .
14 |   0  7  26   73  143  217  246  217  143   73   26    7   1  1  .  .
15 |   0  7  31   91  201  335  429  429  335  201   91   31   7  1  1  .
16 |   0  8  35  116  273  504  715  810  715  504  273  116  35  8  1  1
 |
 |
 v
 S
于 2021-10-17T20:00:48.257 に答える