生成配對的所有組合

Question

如何生成配對的所有組合？例如，如果我有1, 2, 3, 4我要生成

(1, 2), (3, 4) 
(1, 3), (2, 4) 
(1, 4), (2, 3) 

我首先想到的是遞歸生成一對，並嘗試從剩餘的號碼加入對。但是，這會導致重複，因爲即使要添加的對是唯一生成的，也會生成(1, 2), (3, 4)以及(3, 4), (1, 2)。然後我可以刪除所有重複的東西，但有一個更清潔的算法？

我的僞代碼嘗試：

add_pair(current list, remaining nums) 
    generate pairs from remaining nums 
    for every pair generated: 
     remove numbers used in pair from remaining nums 
     add pair + add_pair(current list, remaining nums) to current list 

我不是很舒服的遞歸又那麼這可能會無法正常工作。在其他地方提到的另一種解決方法是回溯，但我不確定這將如何有效地使用。

Answer 1

避免重複枚舉問題的一種非常常見的技術是以規範的方式構造部分對象（在這種情況下，是一些列表元素的配對）。在這裏，這可能意味着循環列表中第一個元素的可能配對，並枚舉其餘元素的配對。我們可以只列出一個配對（配對按第一個元素出現的位置排序），所以沒有重複。在C++中：

#include <algorithm> 
#include <cstdio> 
#include <vector> 

typedef std::vector<int> IntVec; 

// elems has paired elements followed by unpaired elements 
// first is an iterator to the first unpaired element 
void EnumeratePairings(IntVec* elems, IntVec::iterator first) { 
    if (first == elems->end()) { 
    // visit the pairing 
    // for demonstration purposes, we print it out 
    IntVec::const_iterator i(elems->begin()); 
    while (i != elems->end()) { 
     std::printf("(%d, ", *i); 
     ++i; 
     if (i == elems->end()) break; 
     std::printf("%d), ", *i); 
     ++i; 
    } 
    std::printf("\n"); 
    return; 
    } 
    IntVec::iterator second(first); 
    ++second; 
    // make sure that there are at least two elements 
    if (second == elems->end()) return; 
    IntVec::iterator third(second); 
    ++third; 
    // for each possible pairing involving the first element, 
    // enumerate the possibilities recursively 
    for (IntVec::iterator j(second); 
     j != elems->end(); 
     ++j) { 
    // pair *first with *j 
    std::swap(*second, *j); 
    EnumeratePairings(elems, third); 
    // don't undo the swap yet 
    // this way, the unpaired elements are in order 
    // for subsequent iterations 
    } 
    // restore the order of the unpaired elements 
    std::rotate(second, third, elems->end()); 
} 

int main(void) { 
    IntVec elems; 
    for (int i(1); i != 7; ++i) elems.push_back(i); 
    EnumeratePairings(&elems, elems.begin()); 
}