生成对的所有排列而不重复的算法

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 开始是避免重复的最简单方法。

我试图通过高德纳 (Knuth) 找到答案，但我的数学水平太低，无法在排列组合一章给出的大约 100 个练习中找到这个特定的练习。它可能在那里，但我找不到。

希望这里有人能告诉我一个好的算法(最好是用 Pascal 或 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'])

希望对您有所帮助。