CODEWITHSUNDEEP
pythonlistcombinations
askingquestions
askingquestions

Reputation: 25

Find all combinations of pairings between two lists x and y, such that all elements from y are paired with exactly one from x

I am trying to find in python3 each unique combination of elements from two lists x and y, such that for each combination, all elements from list y are paired up with exactly one element from list x (min(x,y) ^ max(x,y) combos). For example, with the following:

x = ['a', 'b', 'c']
y = [1, 2, 3]

combos = get_combos(x,y)
for combo in combos:
    print(combo)

...I want to write get_combos(x, y) such that it returns a list of 27 combos of pairs which, when printed, looks like:

[('a', 1) ('a', 2) ('a', 3)]
[('a', 1) ('a', 2) ('b', 3)]
[('a', 1) ('a', 2) ('c', 3)]
[('a', 1) ('b', 2) ('a', 3)]
[('a', 1) ('b', 2) ('b', 3)]
[('a', 1) ('b', 2) ('c', 3)]
[('a', 1) ('c', 2) ('a', 3)]
[('a', 1) ('c', 2) ('b', 3)]
[('a', 1) ('c', 2) ('c', 3)]
[('b', 1) ('a', 2) ('a', 3)]
[('b', 1) ('a', 2) ('b', 3)]
[('b', 1) ('a', 2) ('c', 3)]
[('b', 1) ('b', 2) ('a', 3)]
[('b', 1) ('b', 2) ('b', 3)]
[('b', 1) ('b', 2) ('c', 3)]
[('b', 1) ('c', 2) ('a', 3)]
[('b', 1) ('c', 2) ('b', 3)]
[('b', 1) ('c', 2) ('c', 3)]
[('c', 1) ('a', 2) ('a', 3)]
[('c', 1) ('a', 2) ('b', 3)]
[('c', 1) ('a', 2) ('c', 3)]
[('c', 1) ('b', 2) ('a', 3)]
[('c', 1) ('b', 2) ('b', 3)]
[('c', 1) ('b', 2) ('c', 3)]
[('c', 1) ('c', 2) ('a', 3)]
[('c', 1) ('c', 2) ('b', 3)]
[('c', 1) ('c', 2) ('c', 3)]

I have looked at itertools.combinations, itertools.product, and itertools.permutations, but none of them seem to give me exactly what I'm looking for. itertools.permutations gets me close when used with zip (see this answer), but there the resulting lists are exclusive in the sense that no element from either list may be repeated in a single combination (e.g. [('a', 1), ('a', 2), ('c', 3)] would be left out), which is not what I want. Will itertools work for this or is this something that needs to be written from scratch?

Upvotes: 1

Views: 927

Answers (4)

Ajax1234
Ajax1234

Reputation: 71471

Basic recursive solution without imports:

x = ['a', 'b', 'c']
y = [1, 2, 3]
def groups(d, c=[]):
  if len(c) == len(x):
    yield list(zip(c, y))
  else:
    for i in d:
       yield from groups(d, c+[i])

print(list(groups(x)))

Output:

[[('a', 1), ('a', 2), ('a', 3)], [('a', 1), ('a', 2), ('b', 3)], [('a', 1), ('a', 2), ('c', 3)], [('a', 1), ('b', 2), ('a', 3)], [('a', 1), ('b', 2), ('b', 3)], [('a', 1), ('b', 2), ('c', 3)], [('a', 1), ('c', 2), ('a', 3)], [('a', 1), ('c', 2), ('b', 3)], [('a', 1), ('c', 2), ('c', 3)], [('b', 1), ('a', 2), ('a', 3)], [('b', 1), ('a', 2), ('b', 3)], [('b', 1), ('a', 2), ('c', 3)], [('b', 1), ('b', 2), ('a', 3)], [('b', 1), ('b', 2), ('b', 3)], [('b', 1), ('b', 2), ('c', 3)], [('b', 1), ('c', 2), ('a', 3)], [('b', 1), ('c', 2), ('b', 3)], [('b', 1), ('c', 2), ('c', 3)], [('c', 1), ('a', 2), ('a', 3)], [('c', 1), ('a', 2), ('b', 3)], [('c', 1), ('a', 2), ('c', 3)], [('c', 1), ('b', 2), ('a', 3)], [('c', 1), ('b', 2), ('b', 3)], [('c', 1), ('b', 2), ('c', 3)], [('c', 1), ('c', 2), ('a', 3)], [('c', 1), ('c', 2), ('b', 3)], [('c', 1), ('c', 2), ('c', 3)]]

Upvotes: 1

Daweo
Daweo

Reputation: 36838

For me it looks like task for itertools.product and zip, I would do:

import itertools
x = ['a', 'b', 'c']
y = [1, 2, 3]
for t in itertools.product(x,repeat=3):
    print(list(zip(t,y)))

Output:

[('a', 1), ('a', 2), ('a', 3)]
[('a', 1), ('a', 2), ('b', 3)]
[('a', 1), ('a', 2), ('c', 3)]
[('a', 1), ('b', 2), ('a', 3)]
[('a', 1), ('b', 2), ('b', 3)]
[('a', 1), ('b', 2), ('c', 3)]
[('a', 1), ('c', 2), ('a', 3)]
[('a', 1), ('c', 2), ('b', 3)]
[('a', 1), ('c', 2), ('c', 3)]
[('b', 1), ('a', 2), ('a', 3)]
[('b', 1), ('a', 2), ('b', 3)]
[('b', 1), ('a', 2), ('c', 3)]
[('b', 1), ('b', 2), ('a', 3)]
[('b', 1), ('b', 2), ('b', 3)]
[('b', 1), ('b', 2), ('c', 3)]
[('b', 1), ('c', 2), ('a', 3)]
[('b', 1), ('c', 2), ('b', 3)]
[('b', 1), ('c', 2), ('c', 3)]
[('c', 1), ('a', 2), ('a', 3)]
[('c', 1), ('a', 2), ('b', 3)]
[('c', 1), ('a', 2), ('c', 3)]
[('c', 1), ('b', 2), ('a', 3)]
[('c', 1), ('b', 2), ('b', 3)]
[('c', 1), ('b', 2), ('c', 3)]
[('c', 1), ('c', 2), ('a', 3)]
[('c', 1), ('c', 2), ('b', 3)]
[('c', 1), ('c', 2), ('c', 3)]

Note odometer-like nature of itertools.product

Upvotes: 1

ychnh
ychnh

Reputation: 197

Try this

import itertools
L = ['a','b','c']
P = list( itertools.product(L, repeat=3) )
[ [(x,1),(y,2),(z,3)] for x,y,z in P ]

Upvotes: 0

Christian Sloper
Christian Sloper

Reputation: 7510

Here is a combination of combinations_with_replacement and permutations that yield the 27.

a = set([])
for i in combinations_with_replacement(['a','b','c'],3):
    for j in permutations(i):
        a.add(j)

assert len(a) == 27

for i in a:
    print(list(zip(i,[1,2,3])))

yields:

[('b', 1), ('b', 2), ('b', 3)]
[('a', 1), ('a', 2), ('c', 3)]
[('b', 1), ('a', 2), ('b', 3)]
[('c', 1), ('a', 2), ('c', 3)]
[('c', 1), ('b', 2), ('a', 3)]
[('c', 1), ('c', 2), ('c', 3)]
[('a', 1), ('c', 2), ('a', 3)]
[('c', 1), ('b', 2), ('c', 3)]
[('c', 1), ('a', 2), ('a', 3)]
[('a', 1), ('a', 2), ('a', 3)]
[('a', 1), ('c', 2), ('b', 3)]
[('a', 1), ('c', 2), ('c', 3)]
[('c', 1), ('c', 2), ('a', 3)]
[('c', 1), ('b', 2), ('b', 3)]
[('a', 1), ('b', 2), ('a', 3)]
[('c', 1), ('c', 2), ('b', 3)]
[('a', 1), ('a', 2), ('b', 3)]
[('b', 1), ('c', 2), ('a', 3)]
[('b', 1), ('b', 2), ('c', 3)]
[('c', 1), ('a', 2), ('b', 3)]
[('b', 1), ('a', 2), ('c', 3)]
[('b', 1), ('c', 2), ('c', 3)]
[('b', 1), ('a', 2), ('a', 3)]
[('a', 1), ('b', 2), ('c', 3)]
[('a', 1), ('b', 2), ('b', 3)]
[('b', 1), ('b', 2), ('a', 3)]
[('b', 1), ('c', 2), ('b', 3)]

Upvotes: 0

Related Questions