Алгоритм генерации всех перестановок пар без повторения

Question

Хотя есть множество статей о генерации перестановок, у меня есть алгоритмическая потребность в перестановке, которая немного отличается.

Для набора элементов (a, b, c, .. n) Я строю пары: (ab), (cd), (ef), ... в любой комбинации элементов. Пары (ab) и (ba) идентичны. Также необходимые перестановки не должны различаться только в последовательности: (ab), (ef), (cd) идентична (ef), (cd), (ab)

В качестве примера я покажу исчерпывающий список перестановок для 6 элементов a, b, c, d, e, f.

Это список пар Я хотел бы, чтобы алгоритм генерации:

(ab), (cd), (ef) 
(ab), (ce), (df) 
(ab), (cf), (de) 
(ac), (bd), (ef) 
(ac), (be), (df) 
(ac), (bf), (de) 
(ad), (bc), (ef) 
(ad), (be), (cf) 
(ad), (bf), (ce) 
(ae), (bc), (df) 
(ae), (bd), (cf) 
(ae), (bf), (cd) 
(af), (bc), (de) 
(af), (bd), (ce) 
(af), (be), (cd) 

Я пытался представить себе алгоритм для 4 пар (8 элементов), но я не мог.

Типичным для решения является то, что все линии начинаются с элемента a. Любой другой исходный элемент может привести к конфликту с двумя правилами: (ab) равно (ba) и (cd), (ab) равно (ab), (cd). Таким образом, начинать все с элемента a является самым простым способом избежать дубликатов.

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

Надежда, что кто-то здесь может показать мне хороший алгоритм (желательно на Паскале или в C).

Answer 1

Поскольку каждая пара имеет подпапку из 2-х элементов, поэтому я предполагаю, что длина списка символов будет ровной.

Алгоритм

1. Возьмите первый элемент из списка и вы пара это с каждым из элементов, оставшихся в списке.
2. Затем, чтобы каждая пара удаляла эти два элемента из вашего списка, теперь ваша проблема сводится к списку, имеющему на два элемента меньше.
3. Теперь повторите эту процедуру, пока размер вашего списка не станет равным 2.
4. Теперь это последняя пара пара требуемой пары.
5. Все готово.

Python код

Здесь я обеспечиваю код, реализующий выше алгоритма в Python:

# Keep coding and change the world..And do not forget anything..Not Again.. 


def func(chr_list, pair=""): 
    l = len(chr_list) 
    if l == 2: 
     print pair + '(' + chr_list[0] + chr_list[1] + ')' 
    else: 
     i = 0 
     l -= 1 
     ch1 = chr_list[0] 
     chr_list = chr_list[1:] 
     while i < l: 
      ch2 = chr_list[i] 
      chr_list.remove(ch2) 
      func(chr_list[:], pair + '(' + ch1 + ch2 + '), ') 
      chr_list.insert(i, ch2) 
      i += 1 


func(['a', 'b', 'c', 'd', 'e', 'f']) 

Надеется, что это поможет вам.