7

Pythonでシーケンスのすべての「順序付けられたサブセット」（正しい数学用語を使用していない場合は謝罪）を生成する必要があります。省略された要素はNone.Given[1, 2]に置き換えられ[(1, 2), (1, None), (None, 2), (None, None)]ます。各「順序付けられたサブセット」は、各位置で、シードシーケンスとまったく同じ要素であるか、であるというプロパティを持っている必要がありますNone。

以下を使用すると、要素が省略されたサブセットをかなり簡単に生成できます。

from itertools import combinations
for length in xrange(len(items), 0, -1):
    for combination in combinations(items, length):
        yield combination

しかし、欠落している要素を再構築する最も効果的な方法が何であるかを理解することはできません。私の最初の考えは、次のようなことをすることです。

from itertools import combinations
indexes = range(len(items))
for length in xrange(len(items), 0, -1):
    for combination in combinations(indexes, length):
        yield tuple(items[i] if i in combination else None for i in indexes)

誰かがこれの明らかな欠陥を見つけることができるかどうか、または私が逃したより効率的な解決策があるかどうか疑問に思っています。（itemsはかなり短いリストであり、通常は10要素未満であるため、内部ループでの「組み合わせ」のO（N）検索については気にしません）。

4

4 に答える 4

12 
from itertools import product, repeat
given = [1, 2]
with_nones = zip(given, repeat(None))
print(list(product(*with_nones)))
于 2012-08-17T20:57:14.367 に答える
2

空のリストから始めることができます。シード内のすべての要素について、すべての最終リストをコピーして、最後にシードを追加できます。

例えば

solutions = []
solutions.append([])
for elem in seed:
    newPartials = []
    for partial in solutions:
        newPartial = partial[:]
        newPartial.append(elem)
        newPartials.append(newPartial)
    solutions.extend(newPartials)

または、可能なソリューションの数を作成できます2^n。ここで、nはシードリストの長さであり、モジュラー演算を使用して、次のように要素を削除します。

solutions = []
for i in xrange(2**n):
    solutions.append(seed[:])
seedLen = len(seed)
for i in xrange(2**(n-1)): // % 0 case of following loop
    solutions[i].pop(0)
for elemLoc in xrange(1,seedLen):
    for solutionNum in xrange(2**n):
        if solutionNum % elemLoc = 0:
            solutions[solutionNum].pop(elemLoc)

この解決策は陽気に非効率的です。問題を解決するための興味深い方法であるため、私は主にそれを含めました。

于 2012-08-17T21:15:26.300 に答える
2

別の方法-itertoolsを使用しないことがいかに愚かであるかを誇示したい場合：

>>> given=[1,2]
>>> gz=zip(given,[None]*len(given))
>>> [(i,j) for i in gz[0] for j in gz[1]]
[(1, 2), (1, None), (None, 2), (None, None)]
于 2012-08-18T00:45:06.637 に答える
2

ここに別のものがあります：

>>> given=[1,2,3,4]
>>> rtr=[[]]
>>> for t in map(None,*(given,[None])):
...    rtr=[x+[y] for x in rtr for y in t]
... 
>>> rtr
[[1, 2, 3, 4], [1, 2, 3, None], [1, 2, None, 4], [1, 2, None, None], [1, None, 3, 4], [1, None, 3, None], [1, None, None, 4], [1, None, None, None], [None, 2, 3, 4], [None, 2, 3, None], [None, 2, None, 4], [None, 2, None, None], [None, None, 3, 4], [None, None, 3, None], [None, None, None, 4], [None, None, None, None]]
于 2012-08-18T01:51:25.297 に答える