生成对的所有排列而无需重复的算法 [英] Algorithm to generate all permutations of pairs without repetition

问题描述

尽管有很多关于生成置换的文章，但我对置换的算法需求却有所不同。

Although there are numerous articles about generating permutations, I have an algorithmic need for permutation that's just a bit different.

给出一组元素（a，b， c，.. n）我构造成对：（ab），（cd），（ef），...以任何元素组合。
对（ab）和（ba）是相同的。
所需的排列也不应仅在顺序上有所不同：（ab），（ef），（cd）与（ef），（cd），（ab）相同

Given a set of elements (a, b, c, .. n) I construct pairs: (ab), (cd), (ef), ... in any combination of elements. Pairs (ab) and (ba) are identical. Also the needed permutations should not be different only in sequence: (ab), (ef), (cd) is identical to (ef), (cd), (ab)

作为示例，我将显示6个元素a，b，c，d，e，f的置换的详尽列表。

As an example, I'll show the exhaustive list of permutations for 6 elements a, b, c, d, e, f.

是我希望算法生成的对的列表：

This is the list of pairs I would like the algorithm to generate:

(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个元素）

I tried to envision the algorithm for 4 pairs (8 elements), but I couldn't.

该解决方案的典型代表是，所有行均以元素a开头。任何其他起始元素都可能与（ab）等于（ba）和（cd），（ab）等于（ab），（cd）的两个规则冲突。因此，以元素a开头是避免重复的最简单方法。

Typical for the solution is, that all lines start with element a. Any other starting element could give a conflict with the two rules that (ab) equals (ba) and (cd), (ab) equals (ab), (cd). So starting all with element a is the easiest way to avoid duplicates.

我试图用Knuth找到答案，但是我对数学家的了解太少了可以在有关排列和组合的一章中找到的100个左右中找到该特定练习。

I tried to find the answer with Knuth, but I'm too little of a mathematician to be able to find this particular exercise in the 100 or so given in the chapter on permutations and combinations. It's probably there, but not for me to find.

希望这里有人可以向我展示一个好的算法（最好是在Pascal或C语言中）。

Hope someone here can show me a good algorithm (preferably in Pascal or in C).

推荐答案

由于您的每对子对都有2个元素，所以我假设您字符列表的长度是偶数。

As your each pair has sub pair of 2 elements so I am assuming length of you character list is even.

算法

1. 获取列表中的第一个元素，并将其与剩余的每个元素配对


2. 然后使每对从列表中删除这两个元素，现在您的问题就减少到列表中少了两个元素。


3. 现在重复此过程，直到列表大小变为2。


4. 现在这是所需对中的最后一个子对。


5. 您已完成。

1. Take first element of you list and pair this with each of element remaining in the list.
2. Then making each pair remove that two elements from your list and now your problem is reduced to a list having two elements less.
3. Now repeat this procedure until your list size becomes 2.
4. Now this one is the last sub pair of the required pair.
5. You are done.

Python代码

此处我提供了在python中实现上述算法的代码：

Here I am providing code implementing above algorithm in 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'])

希望这对您有所帮助。

Hope this will help you.

这篇关于生成对的所有排列而无需重复的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！