0

I want to loop through a list and check all the possible combinations in it. Currently, I'm using a series of nested for loops, and obviously I'm not ecstatic with the speed using this method. It's very slow and can take 20-30 minutes to go through all the combinations.

for n1 in list1:
    list.append(n1)
    for n2 in list2:
        list.append(n2)
        for n3 in list2:
            list.append(n3)
            for n4 in list3:
                list.append(n4)
                for n5 in list3:
                    list.append(n5)
                    for n6 in list4:
                        list.append(n6)
                        for n7 in list4:
                            list.append(n7)
                            for n8 in list5:
                                list.append(n8)
                                for n9 in list5:
                                    list.append(n9)
                                    some logic that determines a value
                                list.remove(n9)
                            list.remove(n8)
                        list.remove(n7)
                    list.remove(n6)
                list.remove(n5)
            list.remove(n4)
        list.remove(n3)
    list.remove(n2)
list.remove(n1)

I have no illusions that this is a good way of doing this. I just can't think of a better way of handling this. There ends up being a TON of combos, but I need to calculate the value of each one. There are 5 lists, the combinations I need to check consist of one from list 1, and two spots from list 2-5.

If anyone has suggestions on how to improve this or anyway in python to imrpove the speed of this, that would be appreciated.

The final combination looks something like this:

List1[n1], list2[n2], list2[n3], list3[n4], list3[n5], list4[n6], list4[n7], list5[n8], list5[n9].

Also, there are combinations where list2 for example could be list2[0],list2[1] and list2[1], list2[0] which for my purposes are the same thing. Eliminating duplicates like that could reduce my combinations, but I'm unsure of how to approach that.

  • 4
    have a look at the `itertools` module. It is very helpful – sshashank124 Mar 18 '14 at 12:24
  • Yes, sorry. This isn't my code, I just rewrote it to be more brief than the actual code I'm using so it's easier to see. –  Mar 18 '14 at 12:27
  • 2
    You shouldn't call your own variable `list`. And bear in mind that `list.remove` is `O(n)` as you search the whole list (and may get the wrong value if there are duplicates) - `list.pop()` will remove the last value – jonrsharpe Mar 18 '14 at 12:29
  • Thanks! Duplicates aren't an issue, but simply using list.pop() will probably speed it up and does the exact thing. Very helpful. –  Mar 18 '14 at 12:31
  • Can you clarify your statement: "combinations I need to check consist of one from list 1, and two spots from list 2-5" ? – Joel Cornett Mar 18 '14 at 12:32
  • Basically the final combination looks like this: List1, list2, list2, list3, list3, list4, list4, list5, list5. –  Mar 18 '14 at 12:33
  • Also, there are combinations where list2 for example could be list2[0],list2[1] and list2[1], list2[0] which for my purposes are the same thing. Eliminating duplicates like that could reduce my combinations, but I'm unsure of how to approach that. –  Mar 18 '14 at 12:34
  • 1
    I suggested [a simplification for this in one of your earlier question](http://stackoverflow.com/a/22405580/1639625). Did this not work? – tobias_k Mar 18 '14 at 12:37
  • Sorry @tobias_k I never saw that. I'm reading it now. Thank you. –  Mar 18 '14 at 12:38
  • @Tobias_K, I replied to your answer to my other question. Not sure if you'll see it since it's old so I thought I'd mention it here. –  Mar 18 '14 at 12:53

2 Answers2

4

It looks like you want to cover all combinations of one item picked from list1, then two each from list2 - list5. If correct, you can certainly make things more efficient:

from itertools import chain, combinations, product

for comb in product(combinations(list1, 1),
                    combinations(list2, 2),
                    combinations(list3, 2), ...):

Each comb will be in the form ((l1,), (l2, l2), (l3, l3), (l4, l4), (l5, l5)), but you can flatten this out using chain.from_iterable:

comb = list(chain.from_iterable(comb))

To get [l1, l2, l2, l3, l3, l4, l4, l5, l5].

For a neatness improvement if not actual efficiency, you can define the lists to use and how many items to pick from each up front:

lists = [(list1, 1), (list2, 2), (list3, 2), (list4, 2), (list5, 2)]

for comb in product(*(combinations(l, n) for l, n in lists)):
jonrsharpe
  • 115,751
  • 26
  • 228
  • 437
0

I'm now using this code suggested by @tobias_k

from itertools import product, combinations
player_combinations = product(combinations(C, 1),
                              combinations(PG, 2),
                              combinations(SG, 2),
                              combinations(PF, 2),
                              combinations(SF, 2))
lineuplist = []
for lineups in player_combinations:
    salary = 0
    names = []
    for players in lineups:
        salary += sum(int(player[2]) for player in players)
    if salarycap - undersalary <= salary <= salarycap:
        for players in lineups:
            names += [player[1] for player in players]
        lineuplist.append(names)
        print(str(names) + " $" + str(salary))

Anyone have suggestions for improvements now? Also, does using itertools repeat iterations of PG[0],PG[1] and PG[1], PG[0] reversal combinations like that?