生成配对的所有组合

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()); 
}