CODEWITHSUNDEEP
pythontuplescombinatorics
JPP
JPP

Reputation: 143

Constrained Composition of Tuples

I have this problem of combinatorics: Let m=(m1,...,mk) be a vector of k positive integers. A k-composition (a1,...,ak) of n is m-constrained if ai≤mi for all 1≤i≤k. For example, (1,1,3) and (2,1,2) are the only (2,1,4)-constrined 3-partitions of 5.

Write a function constrained_compositions that takes a natural number n and a vector m of k positive integers, and prints the set of all m-constrained k-compositions of n. Note that k can be inferred from m.

Googling found this useful function:

def compositions(k, n):
# inputs: k and n are of type 'int'
# output: a set of tuples
assert n > k > 1
to_process = [[i] for i in range(1, n+1)]
while to_process:
    l = to_process.pop()
    s = sum(l)
    le = len(l)
    for i in range(1, n-s+1): 
        news = s + i
        if news <= n:
            newl = list(l)
            newl.append(i)
            if le == k-1 and news == n:
                yield tuple(newl)
            elif le < k-1 and news < n:
                to_process.append(newl)

And implemented to get the tuples that match the constrain like this:

def constrained_compositions(n, m):
# inputs: n is of type 'int' and m is a list of integers
# output: a set of tuples
k = len(m)
max_num = max(m)
l = []
comp = list(compositions(k,n))
for i in comp:
    for j in i:
        if j <= max_num:
            l.append(i)
print(set(l))

But this is my result:

{(2, 3, 2), (2, 1, 4), (4, 2, 1), (5, 1, 1), (3, 3, 1), (3, 2, 2), (3, 1, 3), (1, 5, 1), (1, 4, 2), (2, 2, 3), (2, 4, 1), (1, 2, 4), (4, 1, 2), (1, 1, 5), (1, 3, 3)}

And it should be:

{(1, 1, 5), (1, 2, 4), (2, 1, 4), (2, 2, 3), (3, 1, 3), (3, 2, 2)}

Thanks in advance for your help?

Upvotes: 0

Views: 1055

Answers (2)

sari paisley
sari paisley

Reputation: 71

This works for me fine:

def constrained_compositions(n, m):
    C = set()

    
    def help_comp(k, l):
        D = set()
        if k == 1:
            for i in range(m[0]):
                D.add((i+1,))
        else:
            for j in help_comp(k=k-1, l=l):
                for i in range(m[(len(list(j)))]):
                    i=i+1
                    if i <= m[(len(list(j)))]:
                        D.add((j)+(i,))
        return D

    if len(m) == 1 & m[0] != n:
        return C

    if n == 0 and m[0] !=n:
        return C

    if len(m) == 1 and m[0] == n:
        C.add((n,))

    else:
        for i in range(m[-1]):
            i=i+1
            for j in help_comp(k=len(m)-1, l=n):
                if sum(list((i,)+(j))) == n:
                    if i <= m[-1]:
                        C.add((j)+(i,))
    return C

Upvotes: 0

user2390182
user2390182

Reputation: 73480

One part in your code that is a bit off, is that you only consider the max value from m and check all elements of your compositions against it, without regard for their actual position.

Here is a recursive generator that produces the constrained compositions directly:

def constrained_compositions(n, m):
    if n == 0 and not m:
        yield ()
    if n < 0 or not m:
        return
    for i in range(1, min(n, m[0])+1):
        for cc in constrained_compositions(n-i, m[1:]):
            yield (i,) + cc

>>> list(constrained_compositions(7, [3, 2, 5]))
[(1, 1, 5), (1, 2, 4), (2, 1, 4), (2, 2, 3), (3, 1, 3), (3, 2, 2)]

This defines a success and a failure base case. Otherwise, it makes sure the first element of the composition i is within the given restriction <= m[0] and recurses with the remainders of both n and m: n-i and m[1:]

Upvotes: 2

Related Questions