用于列表分解的优雅Python代码

Question

我尝试编写代码来解决所有可能的列表分解问题。我写的代码一团糟。我需要一个优雅的解决方案来解决这个问题，因为我想改进我的编码风格。

我试着写一个初始版本，如下所示，但是内存需求太大，执行速度太慢。

import itertools

powerset = lambda iterable: itertools.chain.from_iterable(
        itertools.combinations(list(iterable), r)
        for r in range(1, len(list(iterable)) + 1))
flatten = lambda list2d: [item for sublist in list2d for item in sublist]

x = list("abcd") 
xxx = [val for val in powerset([val1 for val1 in powerset(x)] )] 
xxxx = [val for val in xxx if x == list(sorted(flatten(val)))]

xxxx is :
[(('a', 'b', 'c', 'd'),),
 (('a',), ('b', 'c', 'd')),
 (('b',), ('a', 'c', 'd')),
 (('c',), ('a', 'b', 'd')),
 (('d',), ('a', 'b', 'c')),
 (('a', 'b'), ('c', 'd')),
 (('a', 'c'), ('b', 'd')),
 (('a', 'd'), ('b', 'c')),
 (('a',), ('b',), ('c', 'd')),
 (('a',), ('c',), ('b', 'd')),
 (('a',), ('d',), ('b', 'c')),
 (('b',), ('c',), ('a', 'd')),
 (('b',), ('d',), ('a', 'c')),
 (('c',), ('d',), ('a', 'b')),
 (('a',), ('b',), ('c',), ('d',))]

版本2：

import itertools

powerset = lambda iterable: itertools.chain.from_iterable(
        itertools.combinations(list(iterable), r)
        for r in range(1, len(list(iterable)) + 1))
flatten = lambda list2d: [item for sublist in list2d for item in sublist]

def makelist(list_1D):
    for val in powerset(list(powerset(list_1D))) :
        if list_1D == list(sorted(flatten(val))) :
            yield val
        if val == tuple(itertools.combinations(list_1D, 1)) :
            break
            
for d in makelist(list("abcd")) :
    print(d)

output:
(('a', 'b', 'c', 'd'),)
(('a',), ('b', 'c', 'd'))
(('b',), ('a', 'c', 'd'))
(('c',), ('a', 'b', 'd'))
(('d',), ('a', 'b', 'c'))
(('a', 'b'), ('c', 'd'))
(('a', 'c'), ('b', 'd'))
(('a', 'd'), ('b', 'c'))
(('a',), ('b',), ('c', 'd'))
(('a',), ('c',), ('b', 'd'))
(('a',), ('d',), ('b', 'c'))
(('b',), ('c',), ('a', 'd'))
(('b',), ('d',), ('a', 'c'))
(('c',), ('d',), ('a', 'b'))
(('a',), ('b',), ('c',), ('d',))

来自Time Complexity of finding all partitions of a set的版本3

def partition(collection):
    global counter
    if len(collection) == 1:
        yield [collection]
        return
    first = collection[0]
    for smaller in partition(collection[1:]):
        for n, subset in enumerate(smaller):
            yield smaller[:n] + [[first] + subset] + smaller[n + 1:]
        yield [[first]] + smaller

Answer 1

为了避免内存问题，我们需要最大限度地使用生成器/迭代器，并且永远不要创建组合列表。

这里有一种方法，可以通过将问题层层分解来实现。

首先，生成器获取给定数量元素的分区大小。然后，这将用于填充与每个大小对应的元素组合，但单个元素部分除外。最后完成单个元素部分，以避免重复。通过最后这样做，对于单个元素部分，我们总是有正确数量的未使用元素。

分区生成

# Generator for all partition sizes forming N
def partSize(N):
    if N<2: yield [1]*N;return
    for s in range(1,N+1):
        yield from ([s]+rest for rest in partSize(N-s))  

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

print(*partSize(4))
# [1, 1, 1, 1] [1, 1, 2] [1, 2, 1] [1, 3] [2, 1, 1] [2, 2] [3, 1] [4]

分区填充

# A generator that fills partitions 
# with combinations of indexes contained in A  
      
from itertools import combinations
def fillCombo(A,parts,R=None):
    if R is None: R = [tuple()]*len(parts)
    size = max(parts)  # fill largest partitions first
    if size < 2:       # when only single element partitions are left
        iA = iter(A)   # fill them with the remaining indexes
        yield [r if p!=1 else (next(iA),) for r,p in zip(R,parts)]
        return
    i,parts[i]= parts.index(size),0    # index of largest partition
    for combo in combinations(A,size): # all combinations of that size
        R[i] = combo                   # fill part and recurse
        yield from fillCombo(A.difference(combo),[*parts],[*R])      

将分区映射到索引值的

# for each partition pattern, fill with combinations
# using set of indexes in fillCombo so that repeated values
# are processed as distinct

def partCombo(A):
    for parts in partSize(len(A)):
        for iParts in fillCombo({*range(len(A))},parts):   # combine indexes
            yield [tuple(A[i] for i in t) for t in iParts] # get actual values

输出：

for pp in partCombo("abc"): print(pp)

[('a',), ('b',), ('c',)]
[('c',), ('a', 'b')]
[('b',), ('a', 'c')]
[('a',), ('b', 'c')]
[('a', 'b'), ('c',)]
[('a', 'c'), ('b',)]
[('b', 'c'), ('a',)]
[('a', 'b', 'c')]

这使用的内存非常少，但在时间上仍然具有指数级数。例如：

sum(1 for _ in partCombo("abcdefghi")) # 768,500 combinations

在我的笔记本电脑上花3.8秒

只需多添加一个字母，8,070,046个组合的执行时间就会增加到43秒。