どのように連続する数値の一意の合計で正の整数のシーケンスを構築するには？たとえば、

Question

：

1,2,4,5-

-3,6,9-

7,11

12：1,2,4,5-は、以下の和を有します

すべての合計は一意です。

さて、1,2,3には、以下の合計があります。

1,2,3

3,5

を明らかにしていないすべての合計がユニークです。

1,2,4,8,16 ...だけでなく、可能な限り小さな数字をすべてピックするという目的で、最初の例と同様のシーケンスを生成する効率的な方法はありますか？私はおそらくこれをブルートフォースするためのプログラムを書くことができると理解していますが、私はそれがより良い方法で行えるかどうか不思議です。

Answer 1

あなたが探しているものはGolomb Rulerだと思います。上記の数値をマーク間の距離とみなした場合、ゴロム定規について説明しました。あなたが説明したように、定規上のマークのセットに重複がない場合、そのことがGolomb Rulerになります。

Golomb Rulerを記述する標準的な方法は、各マークの位置を表すことであり、マーク間の距離ではありません。したがって、1,2,4,5はGolomb Ruler 0-1-3-7-12と記述されます。ウィキペディアを引用

：

は現在、（ nは単項で与えられている）任意のn次のOGRsを見つけることの複雑さは不明です。過去には、それはNP困難な問題であるとの憶測がありました（ ）。 Golomb Rulersの構築に関連する問題は、確かにNP-hardであることが示されている。ここで、 は、Golomb Rulersを見つけることに類似のフレーバーを持つ既知のNP完全問題はないことにも注意する。

Answer 2

Seen <- emtpy set # Sums seen so far 
Open <- empty set # Sums ending at the last element 
for x from 1 to Limit do 
    if x in Seen then 
     # quick fail 
     continue with next x 
    end 
    # Build new set 
    Pending <- empty set 
    add x to Pending 
    for each s in Open do 
     add (s+x) to Pending 
    end 
    # Check if these numbers are all unique 
    if (Pending intersection Seen) is empty then 
     # If so, we have a new result 
     yield x 
     Open <- Pending 
     Seen <- Seen union Pending 
    end 
end 

それは、これまでに見たすべての合計を見て、和が最後の要素で終了。開始位置と終了位置を追跡する必要はありません。

Limitの値であるN場合、このアルゴリズムは、セット部材チェック及び挿入を想定し、 O（N ログN）を取る O（ログn）、及び交差点/ユニオンされています O（n log n）より遅くならない。

（私は最後の前提に誤解されるかもしれないが）

最初の数値は次のようになります。あなたはそれをブルートフォース場合

1, 2, 4, 5, 8