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

尽管有大量关于生成排列的文章，但我对排列的算法需求稍有不同。给定一组元素（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左右。它可能在那里，但不适合我找。

希望这里的某个人能够给我一个很好的算法（最好用帕斯卡或C语言）。

来源

2016-07-22 Rocky Luck

http://stackoverflow.com/questions/32493769/sets-of-all-disjoint-pairs/32494810#32494810 – MBo

将第一个元素与其后的所有元素相结合（使用循环），然后对每个元素（ a，x）与该组的其余部分一起递归 – m69

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

算法

取第一个元素，你列出和将这些信息与每个剩余列表中的元素。
然后让每一对从你的列表中删除这两个元素，现在你的问题被简化为一个有两个元素少的列表。
现在重复此过程，直到列表大小变为2.
现在，这一个是所需配对的最后一个子对。
你完成了。

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

希望这会帮助你。

来源

2016-07-22 19:22:24 HNMN3

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

回答

相关问题