Python получить группы комбинаций, которые каждый член появляется только один раз - PullRequest
Новая
       8

Python получить группы комбинаций, которые каждый член появляется только один раз

0 голосов
/ 15 января 2019

Я пытаюсь получить группы перестановок / комбинаций (r = 2), чтобы каждый участник появлялся только один раз

Я использовал пакет python 'комбинации', чтобы получить комбинации.

Например: члены: a, b, c, d. Комбинации: [a, b], [a, c], [a, d], [b, c], [b, d] ...

Мой желаемый результат: [{[a, b], [c, d]}, {[a, c], [b, d]}, {[a, d], [b, c]} ...]

Я хотел бы знать, какова терминология для этого случая и есть ли уже реализация для этого.

Спасибо.

Ответы [ 2 ]

0 голосов
/ 15 января 2019

Вы можете найти перестановки до r и затем отфильтровать результаты: 

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]]

Выход: 

[[['a', 'b'], ['c', 'd']], [['a', 'c'], ['b', 'd']], [['a', 'd'], ['b', 'c']], [['b', 'c'], ['a', 'd']], [['b', 'd'], ['a', 'c']], [['c', 'd'], ['a', 'b']]]
0 голосов
/ 15 января 2019

Вот способ сделать это: 

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')}]

Объяснение

Вы можете использовать itertools.combinations дважды, чтобы получить все 2 комбинации кортежей из: 

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

И выбирайте только те, чей набор элементов пересекается с набором исходного списка, len(set(l) & set(chain(*i))) == len(l)) для каждой возможной комбинации.

...