python - リスト内の要素の元のシーケンスを乱すことなく、リスト内の要素の可能なすべての組み合わせを作成する方法は?

Question

Python 2.7.3 にリストがあるとします。

s=['a','b','a','a']

この場合、次のようになる元のシーケンスを乱すことなく、このリスト要素の可能なすべての組み合わせを計算したいと思います。

['a','b','ab','ba','aa','abaa','aba','baa']

8つの必要な組み合わせ。

Answer 1

元の質問は少し不明確だと思います。組み合わせをより適切に定義する必要がありますが、考えられる解釈は次のとおりです。

私はチェーンを主に複数のジェネレーターを組み合わせるために使用します。ほとんどのアルゴリズムでは、シーケンスの長さごとにジェネレーターがあります。与えられた例では、シーケンスの長さは 1、2、3、4 です。シーケンスの長さごとに、部分問題を解きます。

各「a」を異なる値として扱う数学的組み合わせ。これには 15 の要素と重複があります。副問題は、combinations関数を適用するだけですitertools

from itertools import chain, combinations
s=['a','b','a','a']
list(chain(*(combinations(s,i) for i in range(1,1+len(s)))))
Out[3]: 
[('a',),
 ('b',),
 ('a',),
 ('a',),
 ('a', 'b'),
 ('a', 'a'),
 ('a', 'a'),
 ('b', 'a'),
 ('b', 'a'),
 ('a', 'a'),
 ('a', 'b', 'a'),
 ('a', 'b', 'a'),
 ('a', 'a', 'a'),
 ('b', 'a', 'a'),
 ('a', 'b', 'a', 'a')]

上記と同じですが、重複はありません。これには 9 つの要素があり、主に も含まれ'aaa'ます。

from itertools import chain, combinations
s=['a','b','a','a']
set(chain(*(combinations(s,i) for i in range(1,1+len(s)))))
Out[6]: 
set([('b',),
 ('b', 'a'),
 ('a', 'b'),
 ('a', 'a', 'a'),
 ('a', 'a'),
 ('a', 'b', 'a'),
 ('a',),
 ('a', 'b', 'a', 'a'),
 ('b', 'a', 'a')])

最後に、すべてのサブシーケンスを見つけたい場合があります。これには 10 個の要素がありますが、ここでも重複しています。zip部分問題は賢いトリックで解決できます。指定された部分問題のシーケンス長であるN引数を zip に提供し、 でリストをアンパックしてこれらを渡します。各引数は元のリストですが、1 つ離れた位置から開始します。したがって、最初の引数は、2 番目の引数は... です。Zip は基本的に、各引数の最初の要素を取得してタプルに結合することにより、これらのリストを結合します。次に、各引数の 2 番目の要素を取得し、リストの 1 つの末尾に到達するまで、それらをタプルに結合します。たとえば、結果はになります。タプルが 3 つになると停止します。N*s[0:]s[1]zip(s[0:],s[1:])[('a','b'),('b','a'),('a','a')]len(s[1:])==3. ご覧のとおり、これにより長さ 2 のすべてのサブシーケンスが生成されます。

from itertools import chain
s=['a','b','a','a']
list(chain(*(zip(*(s[i:] for i in range(n))) for n in range(1,1+len(s)))))
Out[4]: 
[('a',),
 ('b',),
 ('a',),
 ('a',),
 ('a', 'b'),
 ('b', 'a'),
 ('a', 'a'),
 ('a', 'b', 'a'),
 ('b', 'a', 'a'),
 ('a', 'b', 'a', 'a')]

最後に、上記と同じですが、独自の要素を使用すると、例と同じ出力になります。

from itertools import chain
s=['a','b','a','a']
set(chain(*(zip(*(s[i:] for i in range(n))) for n in range(1,1+len(s)))))
set([('a', 'b', 'a'),
     ('b', 'a'),
     ('a', 'b'),
     ('a', 'b', 'a', 'a'),
     ('b', 'a', 'a'),
     ('a', 'a'),
     ('b',),
     ('a',)])

これらのうちの少なくとも 1 つがあなたの望むものであることを願っています。また、指定された出力から指定した文字列のリストに移動することは、いくつかの結合を適用すること以上のものではありません。