0

For Example:

[[1, 2, 3], [2], [1, 2, 3], [5, 6]]

Will generate:

[[1, 2, 3, 5], [1, 2, 3, 6], [3, 2, 1, 5], [3, 2, 1, 6]]

Any lists containing 2 of the same elements are not allowed: i.e [2, 2, 3, 5]

I've tried using itertools.product(*list) to generate a list of all possible combinations and then looking through that list for any lists with duplicates in it, but this is far too cost intensive for my purposes. Anyone got any ideas?

bdesham
  • 15,430
  • 13
  • 79
  • 123
user2985264
  • 5
  • 3
  • 3
    It’s not clear to me what your criteria are for generating lists. Could you post your inefficient solution, just so we can see more clearly what it is you’re trying to do? – bdesham Nov 12 '13 at 22:25
  • Why not also `[2,3,1,5]` or `[3,1,2,6]`? – Tim Pietzcker Nov 12 '13 at 22:26
  • The lists must be generated in order i.e you pick an element from the first list, then the second, and so on. (so maybe itertools was a bad idea :D) – user2985264 Nov 12 '13 at 22:27
  • pick 3 from [1, 2, 3, 5] then 2 from [2], then 1 from [1, 2, 3] then 5 from [5, 6], sorry if im being a little unclear. – user2985264 Nov 12 '13 at 22:29
  • But you *have* to pick an element from each list? And you are sure that that will always be possible? – Tim Pietzcker Nov 12 '13 at 22:30
  • Yes, the domain in my implementation for every list will be [1, 2, 3, 4, 5, 6, 7, 8, 9] or just a single number i.e [1] from 1-9, and the length of list will always be 9 (9 lists inside) – user2985264 Nov 12 '13 at 22:31
  • So a list like `[[1,2], [1], [2]]` can never happen? – Tim Pietzcker Nov 12 '13 at 22:33
  • No that will not be possible. An element will either be a list containing the numbers one to nine, or list containing a single number from one to nine, and there will always be nine elements. – user2985264 Nov 12 '13 at 22:35

2 Answers2

2

How about this?

In [34]: var = [[1, 2, 3], [2], [1, 2, 3], [5, 6]]

In [35]: [i for i in itertools.product(*var) if len(i) == len(set(i))]
Out[35]: [(1, 2, 3, 5), (1, 2, 3, 6), (3, 2, 1, 5), (3, 2, 1, 6)]

In [36]: var = [[1,2,3,4], [5]]

In [37]: [i for i in itertools.product(*var) if len(i) == len(set(i))]
Out[37]: [(1, 5), (2, 5), (3, 5), (4, 5)]
oz123
  • 27,559
  • 27
  • 125
  • 187
user2390183
  • 975
  • 8
  • 17
1

You could take the formula for product found in the itertools docs and just add a tweak:

def alt_product(*args, repeat=1):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool if y not in x] #tweak
    for prod in result:
        yield tuple(prod)

demo:

li = [[1, 2, 3], [2], [1, 2, 3], [5, 6]]

list(alt_product(*li))
Out[35]: [(1, 2, 3, 5), (1, 2, 3, 6), (3, 2, 1, 5), (3, 2, 1, 6)]

This is likely to be much friendlier on memory since it does not build a list of all combinations and then filter; instead it filters as it goes.

roippi
  • 25,533
  • 4
  • 48
  • 73