Разбиение последовательности на множества уникальных пар

Question

Мне нужна функция, которая может разбить последовательность на пары, а затем объединить их так, чтобы все элементы в комбинации были уникальными. Я пробовал несколько подходов, используя python's itertools, но не нашел решения.

В качестве иллюстрации я хотел бы функцию, которая будет принимать эту последовательность: [1, 2, 3, 4]

и разделить его на следующие 3 комбинаций:

[[1, 2], [3, 4]] 
[[1, 3], [2, 4]] 
[[1, 4], [2, 3]] 

он должен также работают для более длинных последовательностей, но не должны обрабатывать последовательности нечетной длины. например.

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

распадается на следующие 15 комбинаций:

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

... и так далее.

CAS, называемый Maple, выполняет эту функцию под именем setpartition.

Редактировать: исправлена ​​критическая ошибка ввода в конце поздней ночи, указанная wks, и уточненные выходы.

Answer 1

itertools действительно ваш друг:

from itertools import permutations 

def group(iterable, n=2): 
    return zip(*([iter(iterable)] * n)) 

for each in permutations([1, 2, 3, 4, 5, 6]): 
    print map(list, group(each)) 

Результат:

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

[EDIT] @FrederikNS: После того, как вы уточнить ваш вопрос and found an answer yourself, вот мое решение:

from itertools import combinations 

def setpartition(iterable, n=2): 
    iterable = list(iterable) 
    partitions = combinations(combinations(iterable, r=n), r=len(iterable)/n) 
    for partition in partitions: 
     seen = set() 
     for group in partition: 
      if seen.intersection(group): 
       break 
      seen.update(group) 
     else: 
      yield partition 

for each in setpartition([1, 2, 3, 4]): 
    print each 
print 
for each in setpartition([1, 2, 3, 4, 5, 6]): 
    print each 

Результат:

((1, 2), (3, 4)) 
((1, 3), (2, 4)) 
((1, 4), (2, 3)) 

((1, 2), (3, 4), (5, 6)) 
((1, 2), (3, 5), (4, 6)) 
((1, 2), (3, 6), (4, 5)) 
((1, 3), (2, 4), (5, 6)) 
((1, 3), (2, 5), (4, 6)) 
((1, 3), (2, 6), (4, 5)) 
((1, 4), (2, 3), (5, 6)) 
((1, 4), (2, 5), (3, 6)) 
((1, 4), (2, 6), (3, 5)) 
((1, 5), (2, 3), (4, 6)) 
((1, 5), (2, 4), (3, 6)) 
((1, 5), (2, 6), (3, 4)) 
((1, 6), (2, 3), (4, 5)) 
((1, 6), (2, 4), (3, 5)) 
((1, 6), (2, 5), (3, 4)) 

Answer 2

Попробуйте это:

def function(list): 
    combinations = [] 
    for i in list: 
     for i2 in list: 
      if not [i2, i] in combinations: 
       combinations.append([i, i2]) 
    return combinations 

Это возвращает все возможные комбинации.

Надеюсь, это поможет!

Answer 3

я, наконец, получил это мой сам (ответ pillmuncher действительно дал мне толчок в правильном направлении, и функциональная группа является полностью его):

def group(iterable, n=2): 
    return zip(*([iter(iterable)] * n)) 

def set_partition(iterable, n=2): 
    set_partitions = set() 

    for permutation in itertools.permutations(iterable): 
     grouped = group(list(permutation), n) 
     sorted_group = tuple(sorted([tuple(sorted(partition)) for partition in grouped])) 
     set_partitions.add(sorted_group) 

    return set_partitions 

partitions = set_partition([1,2,3,4], 2) 
for part in partitions: 
    print(part) 

это печатает:

((1, 4), (2, 3)) 
((1, 3), (2, 4)) 
((1, 2), (3, 4))