combinations/permutations with no repeats across groupings

2
votes

I'm looking for C or Python code to implement either of the two pseudocode functions:

function 1:

list1 = [0,1,2] #any list of single-integer elements
list2 = [0,3,4]
list3 = [0,2,4]

function1(list1, list2, list3)

>>> (0,3,2),(0,3,4),(0,4,2),(1,0,2),(1,0,4),(1,3,0),(1,3,2),(1,3,4),
    (1,4,0),(1,4,2),(2,0,4),(2,3,0),(2,3,4),(2,4,0)

Basically, it's generating all permutations that are valid, as defined by having a) one element from each list and b) no elements with the same value.

function 2:

list1 = [(0,1),(0,2),(0,3)] #any list of double-integer tuples
list2 = [(0,4),(1,4),(2,4)]

function2(list1, list2)
>>> ((0,1),(2,4)) , ((0,2),(1,4)) , ((0,3),(1,4)) , ((0,3),(2,4))

Function 2 generates any permutation that has one tuple from each list and no elements within each tuple repeated.

I looked at the Python itertools help and couldn't find anything that replicated these pseudo-functions. Any ideas?

Thanks,

Mike

5
pythoncpermutationcombinatorics
Are you hoping we'll do your homework? – Mike Graham
32-year old with wife and kid...no. Hoping you'll help me write a Jenny Craig menu program. function1 = treating meals at a meal level (e.g. 0 = "salad"). function2 = treating meals at an ingredient level (e.g. 0,1 = "carrots","lettuce"). – MikeRand

5 Answers

4
votes
from itertools import product
def function1(*seqs):
  return (x for x in product(*seqs) if len(x) == len(set(x)))

>>> list(function1([0,1,2], [0,3,4], [0,2,4]))
[(0, 3, 2), (0, 3, 4), (0, 4, 2), (1, 0, 2), (1, 0, 4), (1, 3, 0), (1, 3, 2), (1, 3, 4), (1, 4, 0), (1, 4, 2), (2, 0, 4), (2, 3, 0), (2, 3, 4), (2, 4, 0)]
3
votes

Pär Wieslander gave a good general solution for function1. Here is a general solution for function2

from itertools import product
def function2(*args):
    return [i for i in product(*args) if (lambda x: len(x) == len(set(x)))([k for j in i for k in j])]

Of course you can return a generator expression instead if it suits your purpose better.
For example:

def function2(*args):
    return (i for i in product(*args) if (lambda x: len(x) == len(set(x)))([k for j in i for k in j]))
1
votes
>>> [(x,y,z) for x in list1 for y in list2 for z in list3 if (x != y and y != z
and x != z)]
[(0, 3, 2), (0, 3, 4), (0, 4, 2), (1, 0, 2), (1, 0, 4), (1, 3, 0), (1, 3, 2), (1
, 3, 4), (1, 4, 0), (1, 4, 2), (2, 0, 4), (2, 3, 0), (2, 3, 4), (2, 4, 0)]

for the first one

1
votes
def f2(first, second):
    for a in first:
        for b in second:
            if len(set(a + b)) == 4:
                yield (a, b)
0
votes

For anyone wondering, here was the final implementation:

def function2(arg1, arg2):
    return [i for i in product(*arg1) if (lambda x: len(x) == len(set(x)))
            ([k for j in i for k in j] + arg2)]

Two changes from gnibbler's excellent solution:

1) arg1 is now a list that includes every list that would have been in args*. Rather than having to list out each of args*, I just pass arg1 and unpack it in the product(*arg1). Not sure if there's a better way to do this...

2) arg2 is a list of things I want to exclude from any of the combinations. Including them in the parameters for the lambda function lets me further constrain the results of the product(*arg1) without introducing combinations.

With named variables to show you what I'm doing with it, here's the exact code:

def makeMyMenu(allmeals, dont_eat):
    return [menu for menu in product(*allmeals) if (lambda x: len(x) == len(set(x)))
            ([ingredient for meal in menu for ingredient in meal] + dont_eat)]