CODEWITHSUNDEEP
pythoncombinations
user2290820
user2290820

Reputation: 2759

combinations of blocks with maximum height

Consider a problem where N number of blocks are given. They have to be arranged ontop of each other(call them bars) and many such bars have to be laid so total number of blocks across bars is equal to N. And each configuration can have as many combinations with positional changes.

For example if I have 6 blocks, then (1,1,1,1,1,1) (1,2,2,1) (2,1,1,2) (2,2,1,1) ... (1,1,2,2)

each column is a bar of blocks.

I did something like this:

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

which is using random to generate a random number N times and then generating a permutation of same to generate a list of lists. producing results like, for eg 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)

The solution is not optimal and the order of solution is not optimal as well. Could somebody help me in the approach plus the answer doesnt cover all the possibilities, naturally and I am wondering how to approach it.

Upvotes: 1

Views: 85

Answers (1)

Veedrac
Veedrac

Reputation: 60167

Take an answer from Elegant Python code for Integer Partitioning and for each result take the permutations with itertools.permutations. Join these with itertools.chain.from_iterable:

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

Upvotes: 1

Related Questions