python get groups of combinations that each member appear only once

Question

I'm trying to get groups of permutations/combinations (r=2) that each member appear only once

I used python 'combinations' package to have the combinations.

For example: the members are: a,b,c,d. The combinations are: [a,b],[a,c],[a,d],[b,c],[b,d]...

My desired output is: [ {[a,b],[c,d]},{[a,c],[b,d]},{[a,d],[b,c]}...]

I would like to know what is the terminology for that case and if there is already implementation for that.

Thanks.

Sourpuss

Have you tried using itertools.product() and then grouping according to your needs? – Colourable

Answer 1

Here's a way to do it:

from itertools import combinations, chain
l = ['a','b','c','d']
c = list(combinations(l,2))
[set(i) for i in list(combinations(c,2)) if (len(set(l) & set(chain(*i))) == len(l))]
[{('a', 'b'), ('c', 'd')}, {('a', 'c'), ('b', 'd')}, {('a', 'd'), ('b', 'c')}]

Explanation

You can use itertools.combinations twice, in order to get all the 2 tuple combinations from:

list(combinations(l,2))
[('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]

And select only those whose set of elements intersect with that of the original list, len(set(l) & set(chain(*i))) == len(l)) for every possible combination.

Ubangishari

Great! I used this solution to solve my problem for general cases using (len(arr)/2) as the desire size of the groups. I put an additional condition to support case on odd number of elements at 'c'. On that case I can assume that one of the element will be missed in the second combinations list. – Sourpuss

Answer 2

You can find the permutations up to r and then filter the results:

def combinations(d, d1, r, _c = [], _start=[]):
  if len([i for b in _c for i in b]) == len(d1):
    yield _c
  else:
    for i in d:
       if i not in _start:
         if len(_start+[i]) < r:
           yield from combinations(d, d1, r, _c, _start=_start+[i])
         else:
           _d = sorted(_start+[i])
           yield from combinations([i for i in d if i not in _d], d1,r,  _c+[_d], [])

data = ['a', 'b', 'c', 'd']
_r = list(combinations(data, data, 2))
new_d = [a for i, a in enumerate(_r) if a not in _r[:i]]

Output:

[[['a', 'b'], ['c', 'd']], [['a', 'c'], ['b', 'd']], [['a', 'd'], ['b', 'c']], [['b', 'c'], ['a', 'd']], [['b', 'd'], ['a', 'c']], [['c', 'd'], ['a', 'b']]]

Tanka