算法生成所有排列的成對而不重複

儘管有大量關於生成排列的文章，但我對排列的算法需求稍有不同。給定一組元素（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

算法生成所有排列的成對而不重複

回答

相關問題