列表的所有可能子集

Question

列表的所有可能子集

pythonpermutationpython-itertoolsdiscrete-mathematics

7

我刚刚写了一个小型的递归程序来生成列表的所有可能子集。

def subdivisions(ls):
    yield [ls]
    if len(ls) > 1:
        for i in range(1, len(ls)):
            for lhs in subdivisions(ls[:i]):
                yield lhs + [ls[i:]]

>>> for x in subdivisions('abcd'): print x
... 
['abcd']
['a', 'bcd']
['ab', 'cd']
['a', 'b', 'cd']
['abc', 'd']
['a', 'bc', 'd']
['ab', 'c', 'd']
['a', 'b', 'c', 'd']

我已经使用暴力方法破解了这个问题，花费了很长时间来弄清楚。我想知道这被称为什么，因为我相信它有一个名称。

总的来说，我想知道如何从数学角度学习这些内容，以及是否有良好的著名编程库涵盖了像这样的有用算法（我知道https://docs.python.org/3/library/itertools.html）。

[编辑] 这被标记为重复的问题 - get all possible partitions of a set - 有不同的答案。

它正在寻找{{{1,2,3},{}} , {{1},{2,3}} , {{1,2},{3}} , {{1,3},{2}}, {{1},{2},{3}}} 而对于我来说（在它的术语中），一个正确的答案将是{{{1,2,3}} , {{1},{2,3}} , {{1,2},{3}} , {{1},{2},{3}}} 此外，问这个问题的目的是弄清楚这个术语是什么; 我称其为“分区”; 那个答案称其为“划分”。我正在寻找一个良好的资源，列举所有这些模式，以便人们不必重新发明轮子。

- EoghanM

这是不同的；'abcd' 有24个排列，它们不保留顺序。同样，组合会产生不同的结果，因为你会得到单一大小的列表子集。 - EoghanM

https://en.wikipedia.org/wiki/Partition_of_a_set - Eugene Primako

非常感谢@EugenePrimako！区别在于这是一个列表（有序）而不是集合，并且我想保留顺序。我已经从编程的角度提供了自己的答案，希望得到一些资源指针，以便不必重新发明轮子。 - EoghanM

1

@Prune，我不明白这个Python问题如何与您提出的Java问题重复？ - pylang

2

@pylang：感谢您的提醒，我看到了区别。问题已重新开放。 - Prune

显示剩余3条评论

3个回答

3

找到列表的所有分区等同于找到切片列表的所有索引集。

例如，给定列表l = [1, 2, 3, 4]，我们可以通过索引列表[2, 3]表示分区[[1, 2],[3],[4]]。特别地，这样的索引列表和分区之间存在一一对应关系。

这意味着，给定列表l，我们可以找到range(1,len(l))的幂集并找到每个相应的分区。

代码

此解决方案使用itertools recipes中的powerset函数。使用生成器比使用递归更有效率。

from itertools import chain, combinations

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def partitions(lst):
    for indices in powerset(range(1, len(lst))):
        partition = []
        i = 0
        for j in indices:
            partition.append(lst[i:j])
            i = j
        partition.append(lst[i:])

        yield partition

例子

print(*partitions([1, 2, 3]))
# [[1, 2, 3]] [[1], [2, 3]] [[1, 2], [3]] [[1], [2], [3]]

- Olivier Melançon

标记为最佳答案，因为其中包含了 https://docs.python.org/3/library/itertools.html#itertools-recipes 的链接，这正是我在查找itertools以寻找现有解决方案时所错过的。 - EoghanM

0

我的解决方案：

from itertools import chain, product
def p(l):
    return {(l,)} | {tuple(chain(*s)) for i in range(1, len(l)) for s in product(p(l[:i]), p(l[i:]))}

p('abcd') 返回：

{('a', 'bcd'), ('abcd',), ('abc', 'd'), ('ab', 'c', 'd'), ('ab', 'cd'), ('a', 'b', 'cd'), ('a', 'bc', 'd'), ('a', 'b', 'c', 'd')}

- blhsing

优美简洁的解决方案 - 只适用于Python3，对吧？不幸的是，当传入一个列表时无法工作：

p(['a', 'b', 'c', 'd']) TypeError: unhashable type: 'list'

- EoghanM

谢谢。它在Python 2.7中也可以工作。但你说得对，将列表传递给它是行不通的，因为这个解决方案依赖于使用集合来消除重复项，而序列需要是可哈希的才能被添加到集合中，而列表则不是。不过，在传递之前，您可以将列表转换为元组。 - blhsing

酷，生成重复项然后将其丢弃似乎不如其他解决方案高效。 - EoghanM

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eugene Primako · Accepted Answer

让我给你解释一下这个问题的数学意义。

想象一下：你有一个列表abcd。如果在其中加入一些分隔符，比如a|bc|d，就可以将其划分为子列表。所有可能的分隔符都是a|b|c|d（它们的数量是N-1，其中N是列表的大小）。我们称它们（分隔符）为1、2、3。

然后，您的列表的所有子分区将由集合{1, 2, 3}的所有组合生成。总共有2**3 = 8种组合方式：每个元素可以被包含或不被包含。（所有这些组合都被称为幂集）。

这可以帮助您在没有递归的情况下列出所有的子区：您只需从0b000到0b111进行二进制数字迭代（range(0, 2**(N-1))）：

from itertools import zip_longest, chain

def yield_possible_splits(string):
    N = len(string)
    for i in range(2 ** (N-1)):
        spaces_bitmask = bin(i).replace('0b', '').rjust(N, '0')
        spaces = [' ' if bit == '1' else '' for bit in spaces_bitmask]
        yield ''.join(chain(*zip_longest(spaces, string, fillvalue='')))

或者使用itertools.product等效变体代替二进制操作：

from itertools import zip_longest, chain, product

def yield_possible_splits(string):
    N = len(string)
    for spaces in product(['', ' '], repeat=N-1):
        yield ''.join(chain(*zip_longest(string, spaces, fillvalue='')))

用法：

print(list(yield_possible_splits('abcd')))
# ['abcd', 'abc d', 'ab cd', 'ab c d', 'a bcd', 'a bc d', 'a b cd', 'a b c d']