これをもう一度試してみましょう。
いくつかの観察。
- タプルのソート済み配列では、最初の値は常にゼロになります。
- 配列の長さは常に、配列に存在するタプルの数と同じになります。
- これらをランダムに生成する必要があります。
- タプルは「ソートされた」順序で生成されます。
これらの仕様に基づいて、手続き型の方法を考え出すことができます。
- シリアル整数の 2 つのリストを生成します。1 つは選択用、もう 1 つはシード用です。
- シード リスト の各数値に対して
[0, 1, 2, 3]、要素にまだない数値をランダムに追加および削除します。 [01, 13, 20, 32]
- シリアル整数の別のリストを生成し、繰り返します。
[012, 130, 203, 321]
しかし、これはうまくいきません。いくつかの反復では、コーナーに戻り、数値を生成できません。例えば、[01, 13, 20, 32].. appending [3, 0, 1... crap, I'm stuck.
これを修正する唯一の方法は、行全体で真のシャッフルを行い、1 つが収まるまで再シャッフルすることです。これにはかなりの時間がかかる場合があり、セットが長くなるにつれて痛みが増すだけです.
したがって、手続き的に言えば：
解決策 1:ランダム生成
- リストに範囲を設定します。[0, 1, 2, 3]
- 別のリストを作成します。[0, 1, 2, 3]
- リストをシャッフルします。[1, 0, 2, 3]
- 合うものが見つかるまでシャッフルします... [1, 2, 3, 0]
- 3 番目の要素で繰り返します。
この手順では、コンピューターはソリューションを非常に迅速に検証できますが、ソリューションを非常に迅速に生成することはできません。ただし、これは真にランダムな回答を生成する 2 つの方法のうちの 1 つにすぎません。
したがって、最速の保証された方法は、生成手順ではなく、検証手順を利用することです。まず最初に、すべての可能な順列を生成します。
from itertools import permutations
n = 4
candidates = [i for i in permutations(xrange(n),3)]
それで。
解決策 2:ランダム検証
- 0 から始まるトリプレットを選択します。
- 0 で始まらないトリプレットをランダムにポップします。
- ランダムに選択されたトリプレットが中間解であるかどうかを確認します。
- そうでない場合は、別のトリプレットをポップします。
- はいの場合、トリプレットを追加し、REPOPULATE THE TRIPLET QUEUEを実行します。
- n 回繰り返します。# またはキューを使い果たすまで、n 回繰り返すと自然に TRUE になります
次のトリプレットの解は解セットにあることが数学的に保証されているため、それ自体を使い果たした場合、ランダム化された解が表示されるはずです。このアプローチの問題点は、考えられるすべての結果の確率が等しいという保証がないことです 。
解決策 3:反復検証
等確率の結果を得るには、ランダム化を取り除き、可能なすべての 3 タプルの組み合わせ (n-lists long) を生成し、それらのソリューション候補のそれぞれを検証します。
候補解のリストを検証してすべての解を生成し、そのリストから解をランダムにポップする 関数を作成します。
from itertools import combinations
results = [verify(i) for i in combinations(candidates, n)]
# this is 10626 calls to verify for n=4, 5 million for n=5
# this is not an acceptable solution.
ソリューション 1 も 3 も非常に高速ではありません (O(n**2)) が、基準を考えると、真にランダムなソリューションが必要な場合は、これが得られるのと同じくらい高速である可能性があります。解決策 2 は、これら 3 つの中で最速であることが保証され、多くの場合、解決策 1 または 3 を大幅に上回り、解決策 3 が最も安定した結果をもたらします。これらのアプローチのどれを選択するかは、出力で何をしたいかによって異なります。
その後：
最終的に、コードの速度は、コードをどの程度ランダムにするかによって決まります。要件を満たすタプル シリーズの非常に最初の (そして最初の 1 つだけの) インスタンスを吐き出すアルゴリズムは、順列を 1 回順番に攻撃するだけで、O(n) 時間で実行されるため、非常に高速に実行できます。 . ただし、ランダムには何もしません...
また、verify(i) の簡単なコードを次に示します。これは、2 つのタプルが同じインデックスに同じ番号を持たない可能性があるという観察に基づいています。
def verify(t):
""" Verifies that a set of tuples satisfies the combinations without duplicates condition. """
zipt = zip(*t)
return all([len(i) == len(set(i)) for i in zipt])
n = 4 フルソリューションセット
((0, 1, 2), (1, 0, 3), (2, 3, 0), (3, 2, 1))
((0, 1, 2), (1, 0, 3), (2, 3, 1), (3, 2, 0))
((0, 1, 2), (1, 2, 3), (2, 3, 0), (3, 0, 1))
((0, 1, 2), (1, 3, 0), (2, 0, 3), (3, 2, 1))
((0, 1, 3), (1, 0, 2), (2, 3, 0), (3, 2, 1))
((0, 1, 3), (1, 0, 2), (2, 3, 1), (3, 2, 0))
((0, 1, 3), (1, 2, 0), (2, 3, 1), (3, 0, 2))
((0, 1, 3), (1, 3, 2), (2, 0, 1), (3, 2, 0))
((0, 2, 1), (1, 0, 3), (2, 3, 0), (3, 1, 2))
((0, 2, 1), (1, 3, 0), (2, 0, 3), (3, 1, 2))
((0, 2, 1), (1, 3, 0), (2, 1, 3), (3, 0, 2))
((0, 2, 1), (1, 3, 2), (2, 0, 3), (3, 1, 0))
((0, 2, 3), (1, 0, 2), (2, 3, 1), (3, 1, 0))
((0, 2, 3), (1, 3, 0), (2, 0, 1), (3, 1, 2))
((0, 2, 3), (1, 3, 2), (2, 0, 1), (3, 1, 0))
((0, 2, 3), (1, 3, 2), (2, 1, 0), (3, 0, 1))
((0, 3, 1), (1, 0, 2), (2, 1, 3), (3, 2, 0))
((0, 3, 1), (1, 2, 0), (2, 0, 3), (3, 1, 2))
((0, 3, 1), (1, 2, 0), (2, 1, 3), (3, 0, 2))
((0, 3, 1), (1, 2, 3), (2, 1, 0), (3, 0, 2))
((0, 3, 2), (1, 0, 3), (2, 1, 0), (3, 2, 1))
((0, 3, 2), (1, 2, 0), (2, 1, 3), (3, 0, 1))
((0, 3, 2), (1, 2, 3), (2, 0, 1), (3, 1, 0))
((0, 3, 2), (1, 2, 3), (2, 1, 0), (3, 0, 1))
n = 5 には 552 個の一意の解があります。こちらが最初の20件です。
((0, 1, 2), (1, 0, 3), (2, 3, 4), (3, 4, 0), (4, 2, 1))
((0, 1, 2), (1, 0, 3), (2, 3, 4), (3, 4, 1), (4, 2, 0))
((0, 1, 2), (1, 0, 3), (2, 4, 0), (3, 2, 4), (4, 3, 1))
((0, 1, 2), (1, 0, 3), (2, 4, 1), (3, 2, 4), (4, 3, 0))
((0, 1, 2), (1, 0, 4), (2, 3, 0), (3, 4, 1), (4, 2, 3))
((0, 1, 2), (1, 0, 4), (2, 3, 1), (3, 4, 0), (4, 2, 3))
((0, 1, 2), (1, 0, 4), (2, 4, 3), (3, 2, 0), (4, 3, 1))
((0, 1, 2), (1, 0, 4), (2, 4, 3), (3, 2, 1), (4, 3, 0))
((0, 1, 2), (1, 2, 0), (2, 3, 4), (3, 4, 1), (4, 0, 3))
((0, 1, 2), (1, 2, 0), (2, 4, 3), (3, 0, 4), (4, 3, 1))
((0, 1, 2), (1, 2, 3), (2, 0, 4), (3, 4, 0), (4, 3, 1))
((0, 1, 2), (1, 2, 3), (2, 0, 4), (3, 4, 1), (4, 3, 0))
((0, 1, 2), (1, 2, 3), (2, 3, 4), (3, 4, 0), (4, 0, 1))
((0, 1, 2), (1, 2, 3), (2, 4, 0), (3, 0, 4), (4, 3, 1))
((0, 1, 2), (1, 2, 3), (2, 4, 1), (3, 0, 4), (4, 3, 0))
((0, 1, 2), (1, 2, 4), (2, 0, 3), (3, 4, 0), (4, 3, 1))
((0, 1, 2), (1, 2, 4), (2, 0, 3), (3, 4, 1), (4, 3, 0))
((0, 1, 2), (1, 2, 4), (2, 3, 0), (3, 4, 1), (4, 0, 3))
((0, 1, 2), (1, 2, 4), (2, 3, 1), (3, 4, 0), (4, 0, 3))
((0, 1, 2), (1, 2, 4), (2, 4, 3), (3, 0, 1), (4, 3, 0))
したがって、このようなソリューションを生成できますが、時間がかかります。これを利用する場合は、生成されたソリューションをそのままキャッシュし、必要なときにランダムに引き出します。ちなみに、n=5 は力ずくで完了するのに 1 分弱かかりました。解は O(n**2) であるため、n=6 で 1 時間以上、n=7 で 1 日かかると予想されます。真のランダム化されたソリューションを返す唯一の方法は、このようにすることです。
編集：等分布のないランダム解：
以下は、この問題を解決するために私が書いたコードで、Solution 2の実装です。これは部分的で不均等な分散ソリューションであり、十分な時間が与えられれば、保証された すべての可能なソリューションを生成するため、投稿することにしました。
def seeder(n):
""" Randomly generates the first element in a solution. """
seed = [0]
a = range(1, n)
for i in range(1, 3):
seed.append(a.pop(random.randint(0,len(a)-1)))
return [seed]
def extend_seed(seed, n):
""" Semi-Randomly generates the next element in a solution. """
next_seed = [seed[-1][0] + 1]
candidates = range(0, n)
for i in range(1, 3):
c = candidates[:]
for s in next_seed:
c.remove(s)
for s in seed:
try:
c.remove(s[i])
except ValueError:
pass
next_seed.append(c.pop(random.randint(0,len(c)-1)))
seed.append(next_seed)
return seed
def combo(n):
""" Extends seed until exhausted.
Some random generations return results shorter than n. """
seed = seeder(n)
while True:
try:
extend_seed(seed, n)
except (ValueError, IndexError):
return seed
def combos(n):
""" Ensures that the final return is of length n. """
while True:
result = combo(n)
if len(result) == n:
return result