列表的所有可能细分

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

另外，问这个问题的目的是弄清楚这是什么术语；我叫它 'subdivisions';该答案称其为 'partitions'。我正在寻找一个很好的资源，它列举了所有这些模式，这样人们就不会去重新发明轮子。

Answer 1

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

假设：您有列表 abcd。如果你在里面放一些分隔符——比如 a|bc|d——你会把它分成子列表。所有可能的分隔符都是 a|b|c|d（它们的数量是 N-1，其中 N 是列表的大小）。我们称它们为（分隔符）1、2、3。

然后你列表的所有细分将由所有 combinations of set {1, 2, 3}. There will be 2**3 = 8 of them: each element can be in combination or not. (All these combinations are called 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']

Answer 2

找到一个列表的所有 partitions 等同于找到要对列表进行切片的所有索引集。

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

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

代码

此解决方案使用 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]]

Answer 3

我的解决方案：

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') returns:

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

列表的所有可能细分

All possible subdivisions of a list

python

permutation

discrete-mathematics

itertools

代码

例子