代码之家 › 专栏 › 技术社区 › EoghanM

列表的所有可能的细分

discrete-mathematics itertools permutation python

7

EoghanM · 技术社区 · 8 年前

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

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”。我正在寻找一个好的资源,列举所有这些模式,这样人们就不会去重新发明轮子。

3 回复 | 直到 8 年前

1

3

Olivier Melançon iacob 8 年前

查找全部 partitions 一个列表的值相当于找到要在其上分割该列表的所有索引集。

举个例子 l = [1, 2, 3, 4] ,我们可以表示分区 [[1, 2], [3], [4]] 按索引列表 [2, 3] .特别是,这些索引列表和分区之间有一对一的对应关系。

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

代码

此解决方案使用 powerset 功能来自 itertools recipes .使用生成器比使用递归更有效。

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

2

4

Eugene Primako 8 年前

让我对这个问题作些数学解释。

想象一下:你有清单 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']

3

0

blhsing 8 年前

我的解决方案:

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