46 項目のリストがあります。それぞれに番号が関連付けられています。これらのアイテムをペアで 23 ペアのセットにしたいです。各セットで関数を評価したい。このようなセットを生成するにはどうすればよいですか?
itertools の組み合わせ関数を使用してすべての 2-ples を生成できますが、23 ペアのすべてのセットを生成する方法がわかりません。
これを行うにはどうすればよいですか、または参照できるサンプル コードはありますか?
46 項目のリストがあります。それぞれに番号が関連付けられています。これらのアイテムをペアで 23 ペアのセットにしたいです。各セットで関数を評価したい。このようなセットを生成するにはどうすればよいですか?
itertools の組み合わせ関数を使用してすべての 2-ples を生成できますが、23 ペアのすべてのセットを生成する方法がわかりません。
これを行うにはどうすればよいですか、または参照できるサンプル コードはありますか?
>>> L=range(46)
>>> def f(x, y): #for example
... return x * y
...
>>> [f(x, y) for x, y in zip(*[iter(L)] * 2)]
[0, 6, 20, 42, 72, 110, 156, 210, 272, 342, 420, 506, 600, 702, 812, 930, 1056, 1190, 1332, 1482, 1640, 1806, 1980]
編集:
ペアのパワーセットについては、同じ方法でペアを作成することから始めます。range
代わりにPython3 を使用する場合xrange
S = zip(*[iter(L)] * 2) # set of 23 pairs
[{j for i, j in enumerate(S) if (1<<i)&k} for k in xrange(1<<len(S))]
これは非常に大きなリストになります。ジェネレータ式を使用することをお勧めします
for item in ({j for i, j in enumerate(S) if (1<<i)&k} for k in xrange(1<<len(S))):
func(item)
まず、リストからすべてのペアを取得する自然な方法は次のとおりです。
>>> N = 10
>>> input_list = range(N)
>>> [(a,b) for a, b in zip(input_list[::2], input_list[1::2])]
[(0, 1), (2, 3), (4, 5), (6, 7), (8, 9)]
そのようなペアをすべて生成したい場合は、次のようにします (これを以下のケース 1と呼びます)。
>>> set_of_all_pairs = set()
>>> input_list = range(N)
>>> import itertools
>>> for perm in itertools.permutations(input_list):
pairs = tuple([(a,b) for a, b in zip(perm[::2], perm[1::2])])
set_of_all_pairs.add(pairs)
このままでは、ペアの順序が区別され (たとえば、(1,4) は (4,1) とは異なります)、ペアの順序が意味のあるものと見なされます。したがって、セットに追加する前にペアとペアのセットを並べ替えると、次のようになります。
>>> set_of_all_pairs = set()
>>> input_list = range(N)
>>> import itertools
>>> for perm in itertools.permutations(input_list):
pairs = sorted([tuple(sorted((a,b))) for a, b in zip(perm[::2], perm[1::2])])
set_of_all_pairs.add(tuple(pairs))
これは効率的なアルゴリズムではありませんが (以下でケース 3と呼びます)、N の値が小さい場合は機能します。
N=6 の場合、sorted メソッドを使用します。
set([((0, 4), (1, 3), (2, 5)),
((0, 4), (1, 5), (2, 3)),
((0, 1), (2, 3), (4, 5)),
((0, 3), (1, 5), (2, 4)),
((0, 2), (1, 5), (3, 4)),
((0, 4), (1, 2), (3, 5)),
((0, 3), (1, 4), (2, 5)),
((0, 1), (2, 4), (3, 5)),
((0, 5), (1, 4), (2, 3)),
((0, 5), (1, 2), (3, 4)),
((0, 2), (1, 3), (4, 5)),
((0, 3), (1, 2), (4, 5)),
((0, 2), (1, 4), (3, 5)),
((0, 1), (2, 5), (3, 4)),
((0, 5), (1, 3), (2, 4))])
解空間が指数関数的に急速に拡大することに注意してください。(たとえば、N=6 の場合は 15、N=8 は 105、N=10 の場合は 945、N=46 の場合は 25373791335626257947657609375 ~ 2.5 x 10 28になります)。
この質問では、N 個の要素 (すべての要素が異なるという最も一般的なケースを想定) のリストを (N/2) 個のペアのセットに分割し、これを 1 回行うだけでなく、これらのペアリングのすべてのセットを生成するよう求めています。この答えはそうする唯一のものです。はい、指数関数的に遅く、N=46 では完全に実行不可能です。そのため、N=10 を使用しました。
この問題には 3 つの合理的な解釈があります。
ケース 1:タプル内のペア内 (関数の引数が対称ではないなど) とペアのセット内のペアの順序の両方で順序付けが重要である場合、N! が得られます。私たちの答えの数字を組み合わせる方法。この場合、ペア (0,1) と (1,0) の両方が異なると見なされることを意味し、N=4 の場合と同様に、ペアリングは とは{(0,1), (2,3)}
異なると見なされ{(2,3),(0,1)}
ます。
ケース 2:ペアでは順序が重要ですが、ペアリングのセットでは順序は関係ありません。これは、(0,1) と (1,0) を別個のペアと見なすことを意味しますが、(N=4 の場合) セットはセット{(0,1),(2,3)}
と同一で{(2,3), (0,1)}
あり、両方を考慮する必要はないと見なします。この場合、N!/(N/2)! になります。任意のセットに (N/2) があるように、ペアリング! 異なる注文。(上記では明示的に指定しませんでしたが、タプルのソートはやめてください)。
ケース 3:ペア内でもペアリングのセット内でも、順序は無関係です。これは、(0,1) と (1,0) を同じペア (関数の引数は対称) と見なすことを意味するため、N!/( (N/2)! & 2^(N/2) ) のセットを持つことになります。のペア ( factorial(N)/(factorial(N/2)*2**(N/2))
)。各組み合わせの (N/2) ペアのそれぞれには、寄与する 2 つの内部順序があります。
したがって、問題の表現方法に応じて、次のようにする必要があります。
Case 1 | Case 2 | Case 3
----------------------------------------------
N N! | N!/(N/2)! | N!/((N/2)! 2^(N/2))
6 720 | 120 | 15
8 40320 | 1680 | 105
10 3628800 | 30240 | 945
46 5.5x10^57 | 2.1x10^35 | 2x10^28
私のアルゴリズムはすべての順列を通過するため、ケース 3 のアルゴリズムの方がはるかに高速である可能性がありますが、実際にはケース 1 よりもケース 3 の実行の方が遅くなります (並べ替えのため)。ただし、ケース3でさえ漸近実行時間では階乗であり、N〜46を解くことは完全に不可能であるため、漸近表記では私の答えは依然として最適です。ケース 3 の実現可能性の限界 (N ~ 16) で問題サイズを実行する必要がある場合 (たとえば、518918400.0 のペアリングを生成する必要がある場合)、すべての N! を反復するこのソリューションを許可します。順列、並べ替え、および重複の破棄は最適ではありません。