列表的所有可能细分

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)

---

[编辑]这个标记为重复的问题 - 得到一组的所有可能分区 - 获得不同的答案.

它正在寻找{ {{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}}}

此外,提出问题的关键是要弄清楚这是什么术语; 我称之为'细分'; 那个答案叫它'分区'.我正在寻找一个很好的资源,列举所有这些模式,以便人们不再重新发明轮子.

Answer 1

查找列表的所有分区相当于查找要对列表进行切片的所有索引集。

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

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

代码

该解决方案使用itertools Recipespowerset中的函数。使用生成器比使用递归更有效。

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