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

here's challenge. , if can solve you're better man me. lets can = 1 or 0, b can = 1 or 0, c can = 0,1 or 2, d can = 0,1,2 or 4, e 0, , f = 0 or 1.

make list of tuples have of combinations sum specific number, under 5, selection of letters.

eg a,b,c,d , number 4 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 , 3 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 of combinations , dropping ones dont add number cheating , inefficient.

i have tried using

list(itertools.product(*a)) 

but said creates combinations cheating use can reduce it.

you use a list comprehension with short-circuiting conditionals:

[(a,b,c,d)   in range(2)  b in range(2)  if a+b <= 4  c in range(3)  if a+b+c <= 4  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 solutions without enumerating entire set of cartesian products. short-circuits partial sum greater target sum.

---

to generalize function can accept arbitrary collection of iterables form cartesian products, use

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

this lightly modified version of pure-python implementation of itertools.product:

def iterproduct(*args):     """     list(iterproduct('abcd', 'xy')) --> ax ay bx cx cy dx dy     """     pools = map(tuple, args)     if len(pools) == 1:         y in pools[0]:             yield (y,)     else:         x in iterproduct(*pools[:-1]):             y in pools[-1]:                 yield x + (y,) 

the main difference uses conditional if y == target constrain yielded items sum equals target.

it similar this pure-python implementation shown in docs except not generate products before yielding items.

---

for example, constrained_product used 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:         y in pools[0]:             if y == target:                 yield (y,)     else:         y in pools[-1]:             x in constrained_product(target-y, *pools[:-1]):                 yield x + (y,)  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)  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 can also assume values in args non-negative can speed code adding if-statement:

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

if target-y < 0 there no point calling constrained_product(target-y, *pools[:-1]) since assumption values in pools[:-1] non-negative. know there no tuple can sum negative amount, can save time dropping branch.

using modified version of constrained_product,

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

now

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

finds solution quickly:

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