在Python中有效枚举有序子集

Question

我不确定我正在尝试编写的代码的相应数学术语.我想生成唯一整数的组合,其中每个组合的"有序子集"用于排除某些后来的组合.

希望一个例子可以说明这一点:

from itertools import chain, combinations
?
mylist = range(4)
max_depth = 3

rev = chain.from_iterable(combinations(mylist, i) for i in xrange(max_depth, 0, -1))
for el in list(rev):
    print el

---

该代码导致输出包含我想要的所有子集,但也包含一些我不需要的额外子集.我手动插入注释以指示我不想要的元素.

(0, 1, 2)
(0, 1, 3)
(0, 2, 3)
(1, 2, 3)
(0, 1)  # Exclude: (0, 1, _) occurs as part of (0, 1, 2) above
(0, 2)  # Exclude: (0, 2, _) occurs above
(0, 3)  # Keep
(1, 2)  # Exclude: (1, 2, _) occurs above
(1, 3)  # Keep: (_, 1, 3) occurs above, but (1, 3, _) does not
(2, 3)  # Keep
(0,)    # Exclude: (0, _, _) occurs above
(1,)    # Exclude: (1, _, _) occurs above
(2,)    # Exclude: (2, _) occurs above
(3,)    # Keep

---

因此,我的生成器或迭代器的所需输出将是:

(0, 1, 2)
(0, 1, 3)
(0, 2, 3)
(1, 2, 3)
(0, 3)
(1, 3)
(2, 3)
(3,)  

我知道我可以列出所有(通缉和不需要的)组合,然后筛选出我不想要的组合,但我想知道是否有更高效的,基于生成器或迭代器的方式.

Answer 1

您试图排除作为先前返回的组合的前缀的任何组合。这样做很简单。

• 如果元组t具有 length max_depth，则它不能是先前返回的元组的前缀，因为它作为前缀的任何元组都必须更长。
• 如果元组t以 结尾mylist[-1]，则它不能是先前返回的元组的前缀，因为没有可以合法添加到 的末尾t来扩展它的元素。
• 如果元组t的长度小于且不max_depth以 结尾mylist[-1]，则t是先前返回的元组的前缀t + (mylist[-1],)，并且t不应返回。

因此，您应该生成的组合正是长度的组合max_depth和以 结尾的较短的组合mylist[-1]。以下代码按照与原始代码完全相同的顺序执行此操作，并正确处理如下情况maxdepth > len(mylist)：

def nonprefix_combinations(iterable, maxlen):
    iterable = list(iterable)
    if not (iterable and maxlen):
        return
    for comb in combinations(iterable, maxlen):
        yield comb
    for length in xrange(maxlen-2, -1, -1):
        for comb in combinations(iterable[:-1], length):
            yield comb + (iterable[-1],)

（我在这里假设，在 where 的情况下maxdepth == 0，您仍然不想在输出中包含空元组，即使 for maxdepth == 0，它不是先前返回的元组的前缀。如果您确实想要空元组，在这种情况下，您可以更改if not (iterable and maxlen)为元组if not iterable。）