Challenge: Creating a list of tuples of different combinations with different value 'options' in each location of the tuple.

Question

Here's the challenge. And if you can solve it you're a better man than me. Lets say a can = 1 or 0, b can = 1 or 0, c can = 0,1 or 2, d can = 0,1,2 or 4, e only 0, and f = 0 or 1.

Make a list of tuples that have all of the combinations that sum to a specific number, under 5, for a selection of letters.

eg a,b,c,d and the number 4 would give (in no specific order)

[(1,1,1,1),(1,1,2,0),(1,1,0,2),(0,0,2,2),(0,0,0,4)]

or f,f,e,d,c and 3 would give

[(1,1,0,1,0),(1,1,0,0,1)(1,0,0,1,1),(1,0,0,2,0),(1,0,0,0,2),(0,1,0,2,0),(0,1,0,0,2)]

Creating all of the combinations and then dropping the ones that dont add up to the number is cheating and too inefficient.

I have tried using

list(itertools.product(*a))

but like I said that creates all combinations so it is cheating to use it can reduce it.

Answer 1

You could use a list comprehension with short-circuiting conditionals:

[(a,b,c,d) 
 for a in range(2)
 for b in range(2)
 if a+b <= 4
 for c in range(3)
 if a+b+c <= 4
 for d in [0,1,2,4]
 if a+b+c+d == 4]    

yields

[(0, 0, 0, 4),
 (0, 0, 2, 2),
 (0, 1, 1, 2),
 (0, 1, 2, 1),
 (1, 0, 1, 2),
 (1, 0, 2, 1),
 (1, 1, 0, 2),
 (1, 1, 1, 1),
 (1, 1, 2, 0)]

This finds all solutions without enumerating the entire set of Cartesian products. It short-circuits as soon as the partial sum is greater than the target sum.

---

To generalize this to a function which can accept an arbitrary collection of iterables from which to form Cartesian products, we could use

def constrained_product(target, *args):
    pools = map(tuple, args)
    if len(pools) == 1:
        for y in pools[0]:
            if y == target:
                yield (y,)
    else:
        for y in pools[-1]:
            for x in constrained_product(target-y, *pools[:-1]):
                yield x + (y,)

This is a lightly modified version of this pure-Python implementation of itertools.product:

def iterproduct(*args):
    """
    list(iterproduct('ABCD', 'xy')) --> Ax Ay Bx By Cx Cy Dx Dy
    """
    pools = map(tuple, args)
    if len(pools) == 1:
        for y in pools[0]:
            yield (y,)
    else:
        for x in iterproduct(*pools[:-1]):
            for y in pools[-1]:
                yield x + (y,)

The main difference is that it uses the conditional if y == target to constrain yielded items to those whose sum equals target.

It is similar to this pure-Python implementation shown in the docs except that it does not generate all products before yielding items.

---

For example, constrained_product could be used like this:

A = range(2)
B = range(2)
C = range(3)
D = [0,1,2,4]
E = [0]
F = range(2)

def constrained_product(target, *args):
    pools = map(tuple, args)
    if len(pools) == 1:
        for y in pools[0]:
            if y == target:
                yield (y,)
    else:
        for y in pools[-1]:
            for x in constrained_product(target-y, *pools[:-1]):
                yield x + (y,)

for item in constrained_product(4, A, B, C, D):
    print(item)
    # (1, 1, 2, 0)
    # (1, 1, 1, 1)
    # (1, 0, 2, 1)
    # (0, 1, 2, 1)
    # (1, 1, 0, 2)
    # (1, 0, 1, 2)
    # (0, 1, 1, 2)
    # (0, 0, 2, 2)
    # (0, 0, 0, 4)

for item in constrained_product(3, F, F, E, D, C):
    print(item)
    # (1, 1, 0, 1, 0)
    # (1, 0, 0, 2, 0)
    # (0, 1, 0, 2, 0)
    # (1, 1, 0, 0, 1)
    # (1, 0, 0, 1, 1)
    # (0, 1, 0, 1, 1)
    # (0, 0, 0, 2, 1)
    # (1, 0, 0, 0, 2)
    # (0, 1, 0, 0, 2)
    # (0, 0, 0, 1, 2)

---

If we can also assume that the values in args are all non-negative then we can speed up the code by adding an if-statement:

    for y in pools[-1]:
        if target-y >= 0:
            for x in constrained_product(target-y, *pools[:-1]):
                yield x + (y,)

If target-y < 0 then there is no point calling constrained_product(target-y, *pools[:-1]) since by assumption all the values in pools[:-1] are non-negative. We know there is no tuple which can sum to a negative amount, so we can save time by dropping this branch.

Using this modified version of constrained_product,

def constrained_product_nonneg(target, *args):
    pools = map(tuple, args)
    if len(pools) == 1:
        for y in pools[0]:
            if y == target:
                yield (y,)
    else:
        for y in pools[-1]:
            if target-y >= 0:
                for x in constrained_product_nonneg(target-y, *pools[:-1]):
                    yield x + (y,)

now

list(constrained_product_nonneg(0, *[A]*53))

finds the solution quickly:

In [35]: %timeit list(constrained_product_nonneg(0, *[A]*53))
10000 loops, best of 3: 170 µs per loop

Answer 2

Here's a tree based solution. It makes every valid answer for the system (which is maybe cheating) but it doesn't have to do duplicate calculations.

class tree_node:
     def __init__(self, v, s, p):
          self.value = v
          self.sum = s
          self.parent = p
          self.branchList = []

if __name__ == "__main__":

    # Initialize the tree. The sums will be in the leaves once it's built
    root = tree_node(None, 0, None)
    leaf_list = [root]

    # Define the rules of the problem
    a = [0, 1]
    b = [0, 1]
    c = [0, 1, 2]
    d = [0, 1, 4]
    e = [0]
    f = [0, 1]
    rules = [a, b, c, d, e, f]

    # Build the tree, one layer of nodes at a time
    for rule in rules:
       new_leaves = []
       for leaf in leaf_list:
           for r in rule:
                tn = tree_node(r, r + leaf.sum, leaf)
                new_leaves.append(tn)
       leaf_list = new_leaves


    # Traverse the tree starting from each matching leaf
    target = 4
    for n in leaf_list:
        if n.sum == target:
            sequence = [n.value]
            parent = n.parent
            while parent.value != None:
                sequence = sequence + [parent.value]
                parent = parent.parent
            sequence.reverse()
            print sequence