all combinations of differences of two lists

Question

I have two lists, one being the canonical good list, and the other being the current bad list. I want to try all combinations of deviations of the bad list from the good list. For example:

good = (0,1,2,3)
bad =  (0,10,20,3)

after applying operator op(good, bad), I should get back

ret = ((0,1,2,3), (0,10,2,3), (0,10,20,3), (0,1,20,3))

in any order for the sub list.

The lists I am working with are the output of stty -g, which are 36 elements, and the lists differ by 16 elements.

score 3 · Accepted Answer · edited May 23 '17 at 10:25

Zip the good and bad lists, map each resulting tuple to a set and feed that to itertools.product():

from itertools import product

for combo in product(*map(set, zip(good, bad))):
    print(combo)

Demo:

>>> good = (0,1,2,3)
>>> bad =  (0,10,20,3)
>>> from itertools import product
>>> for combo in product(*map(set, zip(good, bad))):
...     print(combo)
... 
(0, 1, 2, 3)
(0, 1, 20, 3)
(0, 10, 2, 3)
(0, 10, 20, 3)

This will take any size of inputs; not just good and bad, but you can add in ugly as well:

>>> ugly =  (1,2,4,3)
>>> for combo in product(*map(set, zip(good, bad, ugly))):
...     print(combo)
... 
(0, 1, 4, 3)
(0, 1, 2, 3)
(0, 1, 20, 3)
(0, 10, 4, 3)
(0, 10, 2, 3)
(0, 10, 20, 3)
(0, 2, 4, 3)
(0, 2, 2, 3)
(0, 2, 20, 3)
(1, 1, 4, 3)
(1, 1, 2, 3)
(1, 1, 20, 3)
(1, 10, 4, 3)
(1, 10, 2, 3)
(1, 10, 20, 3)
(1, 2, 4, 3)
(1, 2, 2, 3)
(1, 2, 20, 3)

Generalized to a function:

def op(*sequences):
    return product(*map(set, zip(*sequences)))

for combo in op(good, bad):
    print(combo)

for combo in op(good, bad, ugly):
    print(combo)

Because a set is used to produce unique values from each combined set of inputs, the output order is not the same as the order of the inputs. If order is important, you can replace set with a dupe-removing order-preserving function instead:

def unique_with_order(seq):
    seen = set()
    seen_add = seen.add
    return [x for x in seq if x not in seen and not seen_add(x)]

def ordered_op(*sequences):
    return product(*map(unique_with_order, zip(*sequences)))

which produces output ordered according to the order of the inputs:

>>> for combo in ordered_op(good, bad):
...     print(combo)
... 
(0, 1, 2, 3)
(0, 1, 20, 3)
(0, 10, 2, 3)
(0, 10, 20, 3)
>>> for combo in ordered_op(bad, good):
...     print(combo)
... 
(0, 10, 20, 3)
(0, 10, 2, 3)
(0, 1, 20, 3)
(0, 1, 2, 3)

score 2 · Answer 2 · answered Oct 02 '13 at 20:25

What you want is the Cartesian product of the good-or-bad value at each index, except that when good and bad have the same value, you only want one of them, not two copies of it.

So, let's zip the two lists, and reduce each component where good==bad to a single value:

>>> gb = (([g,b] if g!=b else [g] for (g, b) in zip(good, bad))

Then the Cartesian product:

>>> ret = itertools.product(*gb)

And since you want it as a tuple:

>>> ret = tuple(ret)
>>> print ret
((0, 1, 2, 3), (0, 1, 20, 3), (0, 10, 2, 3), (0, 10, 20, 3))

all combinations of differences of two lists

2 Answers2