python - 列表的所有可能分割

Question

我刚刚编写了一个小的递归程序来生成列表的所有可能分割:

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}}}

此外，提出问题的目的是弄清楚 this 的术语是什么；我称之为“分割”；该答案称其为“分区”。我正在寻找一个很好的资源，它列举了所有这些模式，这样人们就不会去重新发明轮子。

Answer 1

让我对这个问题给出一些数学解释。

假设:您有列表 abcd。如果您在其中放置一些分隔符 - 如 a|bc|d - 您将把它分成子列表。所有可能的分隔符都是 a|b|c|d(它们的数量是 N-1，其中 N 是列表的大小)。我们称它们为(分隔符)1、2、3。

然后列表的所有分割将由所有 combinations 生成集合 {1, 2, 3}。将有 2**3 = 8 个:每个元素可以组合也可以不组合。 (所有这些组合都称为 powerset )。

这可以帮助您无需递归地列出所有分割:您只需迭代从 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']