リスト内の要素の2^nは-2組み合わせ

Question

Iは、次のリストを持っているを見つける：

list1 = ['g1','g2','g3','g4'] 

私はn、リスト内の項目の総数である2^n-2組み合わせを検索します。 n = 4の場合、結果は2^4 -2 = 14、つまり14の組み合わせになります。

の組み合わせは以下のとおりです。

[[['g1'],['g2','g3','g4']],[['g2'],['g1','g3','g4']], [['g3'],['g1','g2','g4']],['g4'],['g1','g2','g3']],[['g1','g2'],['g3','g4']],[['g1','g3'],['g2','g4']],[['g1','g4'],['g3','g4']],[['g2','g3'],['g1','g4']], 
[['g2','g4'],['g1','g3']],[['g3','g4'],['g1','g2']],[['g1','g2','g3'],['g4']],[['g2','g3','g4'],['g1']],[['g3','g4','g1'],['g2']],[['g4','g1','g2'],['g3']]] 

は、私は1つのアプローチを知っている：最初の繰り返しで は、単一の要素を取り、リストと第二のリスト内の他の要素にそれを置く：2回目の反復で['g1'],['g2','g3','g4'] は中2つの要素を取りますリストと他の要素を2番目のリストに追加します。 ['g1','g2'],['g1','g4'] 他のアプローチはありますか？ 私はこのプログラムをPythonで書いています。 私のアプローチはコストがかかります。これをすばやく行うライブラリメソッドはありますか？

Answer 1

ここitertools

import itertools as iter 

list1 = ['g1', 'g2', 'g3', 'g4'] 
combinations = [iter.combinations(list1, n) for n in range(1, len(list1))] 
flat_combinations = iter.chain.from_iterable(combinations) 
result = map(lambda x: [list(x), list(set(list1) - set(x))], flat_combinations) 
# [[['g1'], ['g4', 'g3', 'g2']], [['g2'], ['g4', 'g3', 'g1']], [['g3'], ['g4', 'g2', 'g1']],... 
len(result) 
# 14 

Answer 2

itertools.combinations（反復可能、R）入力イテラブルから要素の

戻りR長の部分配列を用いた機能的なアプローチです。 組み合わせは、辞書順ソート順で出力されます。したがって、入力 イテラブルがソートされている場合、組み合わせタプルはソートされた オーダで生成されます。アウト

from itertools import combinations 
list1 = ['g1','g2','g3','g4'] 
for n in range(1,len(list1)): 
    for i in combinations(list1,n): 
     print(set(i), set(list1) - set(i)) 

：

{'g1'} {'g2', 'g3', 'g4'} 
{'g2'} {'g1', 'g3', 'g4'} 
{'g3'} {'g1', 'g2', 'g4'} 
{'g4'} {'g1', 'g2', 'g3'} 
{'g1', 'g2'} {'g3', 'g4'} 
{'g1', 'g3'} {'g2', 'g4'} 
{'g1', 'g4'} {'g2', 'g3'} 
{'g2', 'g3'} {'g1', 'g4'} 
{'g2', 'g4'} {'g1', 'g3'} 
{'g3', 'g4'} {'g1', 'g2'} 
{'g1', 'g2', 'g3'} {'g4'} 
{'g1', 'g2', 'g4'} {'g3'} 
{'g1', 'g3', 'g4'} {'g2'} 
{'g2', 'g3', 'g4'} {'g1'} 

私は中国のコーダ（私は推測）からソリューションを好きこの

Answer 3

を試すことができます。私自身の解決策は次のとおりです。

import itertools 


def flatten(*z): 
    return z 


list1 = ['g1','g2','g3','g4'] 

sublists = [] 
for i in range(1, len(list1)): 
    sublists.extend(itertools.combinations(list1, i)) 

pairs = [] 
for a, b in itertools.product(sublists, sublists): 
    if len(a) + len(b) == len(list1) and \ 
    len(set(flatten(*a, *b))) == len(list1): 
     pairs.append((a, b)) 

print(pairs, len(pairs))