5

I have two sets of options:

optionList1 = [a1,a2,a3,...,an]
optionList2 = [b1,b2,b3,...,bn]

The number of elements in the optionlists are not necessarily equal and I have to choose from the first optionlist twice. How do I ensure that I have tried every combination of 2 options from the first list and one from the second list. An example selection set below...

selectedOptions = [an1,an2,bn]
thenickname
  • 6,684
  • 14
  • 41
  • 42
  • 1
    sorry, but I'm a bit unclear about what you are trying to do. Do you need a table of all possible combinations of elements the element, where none are from the same list? Should any node ever be None? – fncomp Feb 05 '11 at 09:18
  • I guess I was slow to figure out what you wanted. – fncomp Feb 05 '11 at 09:22

5 Answers5

7

Combine product and permutations from itertools assuming you don't want duplicates from the first list:

>>> from itertools import product,permutations
>>> o1 = 'a1 a2 a3'.split()
>>> o2 = 'b1 b2 b3'.split()
>>> for (a,b),c in product(permutations(o1,2),o2):
...     print a,b,c
... 
a1 a2 b1
a1 a2 b2
a1 a2 b3
a1 a3 b1
a1 a3 b2
a1 a3 b3
a2 a1 b1
a2 a1 b2
a2 a1 b3
a2 a3 b1
a2 a3 b2
a2 a3 b3
a3 a1 b1
a3 a1 b2
a3 a1 b3
a3 a2 b1
a3 a2 b2
a3 a2 b3
Mark Tolonen
  • 166,664
  • 26
  • 169
  • 251
  • 1
    Very nice! Also note that you can replace `permutations` with `combinations` if you don't want repeated pairs with different ordering. – shang Feb 05 '11 at 10:59
  • @shang, I had that originally but it wasn't clear what the OP wanted. I thought permutations was more likely. OP could be OK with duplicates, too, then `product(o1,o1,o2)` would be fine. – Mark Tolonen Feb 05 '11 at 11:02
6

Assuming you don't want duplicate entries from list1, here's a generator that you can use to iterate over all combinations:

def combinations(list1, list2):
    return ([opt1, opt2, opt3]
            for i,opt1 in enumerate(list1)
            for opt2 in list1[i+1:]
            for opt3 in list2)

This, however, doesn't select the same options from list1 in different orderings. If you want to get both [a1, a2, b1] and [a2, a1, b1] then you can use:

def combinations(list1, list2):
    return ([opt1, opt2, opt3]
            for opt1 in list1
            for opt2 in list1
            for opt3 in list2 if opt1 != opt2)
shang
  • 24,642
  • 3
  • 58
  • 86
  • 2
    In python terms, a generator is something that uses `yield`. This one has the disadvantage of storing the whole list with options in memory. – Peter Smit Feb 05 '11 at 09:23
  • 1
    And of course the OP can call this with the first two parameters being the same list. combinations(optionList1,optionList1,optionList2) just in case its not clear. – Spacedman Feb 05 '11 at 09:24
  • 1
    The function actually returns a generator expression, so it doesn't build the whole list in memory. – shang Feb 05 '11 at 09:24
6

You can use itertools.product for this. It returns all possible combinations.

For example

for a1, a2, b in itertools.product(optionlist1,optionlist1,optionlist2):
    do_something(a1,a2,b)

This will produce "doubles" as [a1,a1,b2] and [a2,a3,b2],[a3,a2,b2]. You can fix this with a filter. The following prevents any doubles*: 

for a1,a2,b in itertools.ifilter(lambda x: x[0]<x[1], itertools.product(optionlist1,optionlist1,optionlist2)):
    do_something(a1,a2,b)

(*) This assumes that the options have some natural ordering which will be the case with all primitive values.

shang's answer is also very good. I wrote some code to compare them: 

from itertools import ifilter, product
import random
from timeit import repeat

def generator_way(list1, list2):
    def combinations(list1, list2):
        return ([opt1, opt2, opt3]
                for i,opt1 in enumerate(list1)
                for opt2 in list1[i+1:]
                for opt3 in list2)
    count = 0
    for a1,a2,b in combinations(list1,list2):
        count += 1

    return count

def itertools_way(list1,list2):
    count = 0
    for a1,a2,b in ifilter(lambda x: x[0] < x[1], product(list1,list1,list2)):
        count += 1
    return count

list1 = range(0,100)
random.shuffle(list1)
list2 = range(0,100)
random.shuffle(list2)

print sum(repeat(lambda: generator_way(list1,list2),repeat = 10, number=1))/10
print sum(repeat(lambda: itertools_way(list1,list2),repeat = 10, number=1))/10

And the result is: 

0.189330005646
0.428138256073

So the generator method is faster. However, speed is not everything. Personally I find my code 'cleaner', but the choice is yours!

(Btw, they give both identical counts, so both are equally correct.)

Community
  • 1
  • 1
Peter Smit
  • 27,696
  • 33
  • 111
  • 170
3

It sounds to me like you're looking for itertools.product()

>>> options_a = [1,2]
>>> options_b = ['a','b','c']
>>> list(itertools.product(options_a, options_a, options_b))
[(1, 1, 'a'),
 (1, 1, 'b'),
 (1, 1, 'c'),
 (1, 2, 'a'),
 (1, 2, 'b'),
 (1, 2, 'c'),
 (2, 1, 'a'),
 (2, 1, 'b'),
 (2, 1, 'c'),
 (2, 2, 'a'),
 (2, 2, 'b'),
 (2, 2, 'c')]
Gabriel Grant
  • 5,415
  • 2
  • 32
  • 40
  • I'm not sure I understand: as far as I can tell, this works the same way regardless of the length of either list. As to whether it answers the question, it is difficult to say, as the question itself was somewhat ambiguous: the OP didn't specify whether groups of option selections with duplicate items from the first set of options are to be included. Because of this ambiguity I can't assert that this is *precisely* the solution to the OP's problem, but to say it "doesn't even come close" seems rather extreme. – Gabriel Grant Feb 07 '11 at 02:20
2

One way to do is to use itertools.product.

for x, y, z in itertools.product(optionlist1,optionlist1,optionlist2):
    print x,y,z
Senthil Kumaran
  • 54,681
  • 14
  • 94
  • 131
  • This doesn't try all the combinations. Instead it matches up the indices in the list, only returning (a1,a1,b1),(a2,a2,b2)....(an,an,bn) if both would be same length. – Peter Smit Feb 05 '11 at 09:24
  • @Peter. Yes, I was just updating it with the correct answer. I find you have pointed out the correct answer. – Senthil Kumaran Feb 05 '11 at 09:29
  • You don't need to append the list with empty values. itertools.product() can handle lists (or iterators) with different lengths. – Peter Smit Feb 05 '11 at 09:40
  • Including empty values is not just unnecessary, it will cause an incorrect result. – Gabriel Grant Feb 05 '11 at 09:48