python - 具有最大高度的 block 的组合

Question

考虑一个给定 N 个 block 的问题。它们必须排列在彼此之上(称为条形)，并且必须放置许多这样的条形，因此跨条形的 block 总数等于 N。并且每种配置可以具有任意数量的位置变化组合。

例如，如果我有 6 个 block ，那么(1,1,1,1,1,1)(1,2,2,1)(2,1,1,2)(2,2,1,1)...(1,1,2,2)

每一列都是一个 block 条。

我做了这样的事情:

def combinations_occur(N, limit = 3):
    l = []
    for i in xrange(1,N+1):
        tmp = []
        count = 0
        x = i if limit > i else limit
        while count != N:
            s = sum(tmp)
            extra = random.randint(1,x)
            while s + extra > N:
                extra -= 1
            tmp += [extra]
            #print sum(tmp),N
            if sum(tmp) == N:
                l += list(set(permutations(tmp,len(tmp))))
                break;
            else: count += 1
    return l

它使用 random 生成随机数 N 次，然后生成相同的排列以生成列表的列表。产生类似结果，例如 N = 6

(1, 1, 1, 1, 1, 1),
 (1, 1, 1, 1, 2),
 (1, 1, 1, 2, 1),
 (1, 1, 2, 1, 1),
 (1, 1, 2, 2),
 (1, 2, 1, 1, 1),
 (1, 2, 1, 2),
 (1, 2, 2, 1),
 (1, 2, 3),
 (1, 3, 2),
 (2, 1, 1, 1, 1),
 (2, 1, 1, 2),
 (2, 1, 2, 1),
 (2, 1, 3),
 (2, 2, 1, 1),
 (2, 2, 2),
 (2, 3, 1),
 (3, 1, 2),
 (3, 2, 1)

解不是最优的，解的顺序也不是最优的。有人可以帮助我解决这个问题吗？答案并不能涵盖所有可能性，我自然想知道如何解决它。

Answer 1

从 Elegant Python code for Integer Partitioning 获取答案并使用 itertools.permutations 对每个结果进行排列。使用 itertools.chain.from_iterable 连接这些:

from itertools import chain, permutations
chain.from_iterable(map(permutations, integer_partitions))