すべての可能な配列を列挙

Question

問題ステートメント：我々は、与えられ

1. T番号S1、S2の組.... ST

2. 範囲

   と呼ばれる整数

これは、S1（2 *範囲+ 1）をとることができることを意味し、V 012,2316,同様に、S2、... STは2 * Range + 1の値をとることができます。

（0〜1）問題1：すべての可能なシーケンスをどのように列挙しますか？ （S1、S2、... ST）、S1-Range + 1、S2、... ST）、...、（S1、S2 -Range、S3、... ST）など

問題2：合計がS1 + S2 + ... + STのシーケンスをリストするにはどうすればよいですか？問題1の場合

：私は検討していますアプローチは

for (i=0; i<pow(Range,T);i++) 
{ 
    Sequences that can be derived from i are 
    1. {Si + i mod pow(Range,i)} 
    2. {Si - i mod pow(Range,i)} 
} 

その他のよりエレガントな解決策を行うことですか？

また、問題2のアイデアはありますか？

Answer 1

＃1の場合、1つの方法は、数字を増やす方法と同じように考えることです。最後の桁をインクリメントし、オーバーフローしたときに初期値（0）に戻して次の桁をインクリメントします。

したがって、サイズTの配列を作成し、要素を（S1-Range、S2-Range、...、ST-Range）に初期化します。それを印刷します。

最後の値をST-Range + 1にインクリメントします。それを印刷します。 ST +レンジに達するまでインクリメントと印刷を続けます。インクリメントしようとすると、ST-Rangeにリセットされた後、1つの位置を左に移動し、それを増分します。それがあふれても繰り返す。左いっぱいに移動したら、完了です。それ以外の場合は印刷してください。 ＃2のために

// Input: T, S[T], Range 
create V[T] 
for (i in 1..T): 
    V[i] = S[i] - Range 
loop forever { 
    print V 
    i = T 
    V[i]++ 
    while V[i] > S[i] + Range { 
     V[i] = S[i] - Range 
     i-- 
     if i < 1: 
      return // we're done 
     V[i]++ 
    } 
} 

---

、それは少し違います。説明のために、Sの値を無視し、各位置のデルタ（-Range、...、0、...、+ Range）のフォーカスを無視します。

sum（D）= 0の場合、初期値のセットは（-Range、-Range、...、+ Range、+ Range）です。 Tが偶数の場合、前半は-Range、後半は+ Rangeです。 Tが奇数の場合、中間の値は0

いる今、あなたは反復が行ってみたい方法を見て：

-2 -2 0 2 2 
-2 -2 1 1 2 
-2 -2 1 2 1 
-2 -2 2 0 2 (A) 
-2 -2 2 1 1 
-2 -2 2 2 0 
-2 -1 -1 2 2 
-2 -1 0 1 2 
-2 -1 0 2 1 
-2 -1 1 0 2 

それはいつもの機能なので、ここでロジックは、あなたが最後の桁をスキップしていることです他の数字。インクリメントすることができる最も右の桁をインクリメントし、その右側の数字をsum（D）= 0を与える可能な低い値にリセットします。

ロジックはもう少し複雑なので、書き留めておきましょう。;-)

良いヘルパーメソッドの考え方は、開始デルタを与えられた特定の位置の後の数字を可能な限り小さな値にリセットする方法です。その後、reset(1, 0)を呼び出すことで配列を初期化することができます。開始位置0を使用して位置1をリセットします。

次に、AとマークされたステップでD [3]を2に増やすとreset(4, -2)と呼びます。つまり、開始デルタ-2を使用してポジション4..5をリセットします。最後の桁の最大値が2（範囲）の場合、D [4]は0より小さくならないことを意味します。