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

这是另一个：

>>> 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 回答
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

您可以从一个空列表开始，对于种子中的每个元素，您可以复制所有最终列表并在末尾添加种子。

例如

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 回答