c++ - 2-组合C++

Question

我有一个包含 n 个元素的数组，我需要将它们的所有 2-组合放入长度为 2 的数组中。例如：

假设 comb 是一个二维数组。

n = 1,2,3

我需要像这样将所有 2-组合放入 comb[i][j] 中：

comb[0][0] = {1}
comb[0][1] = {2}

comb[1][0] = {1}
comb[1][1] = {3}

comb[2][0] = {2}
comb[2][1] = {3}  

我不知道怎么写代码！谢谢

我的答案：

O(n!) 答案：n = 总数 m= 可能的答案总数

int m = 0;
for (int i = 0; i < n - 1; i++){
    int first = a[i];
    for(int j = i+1 ; j < n ; j++){
        int second = a[j];
        comb[m][0] = first;
        comb[m][1] = second;
        ++m;
}

}

Answer 1

可以想到以下N^2的做法：

// Resulting combinations
vector<pair<int,int> > comb;
// Copy n into a double-ended queue - best would be for n to already be a deque
deque<int> Q(a.size());
copy(a.begin(), a.end(), Q.begin());
sort(Q.begin(), Q.end());

while(!Q.empty())
{
   // Get first element, remove it and equivalent elements
   int a = Q.front();
   while(Q.front() == a)
       Q.pop_front();

   // Find all unique combinations with first element
   int last=a;
   for(deque<int>::iterator it = Q.begin(); it != Q.end(); ++it)
   {
       if(*it != last)
           comb.push_back(pair<int,int>(a,*it));
        last = *it;
   }
}

可能很容易进一步优化这一点。

Answer 2

对于n索引 ith 中的每个元素，将n除第 i 个索引 jth 之外的所有元素放入 cell 中comb[length(n) - i][j]。

Answer 3

一种简单的方法是使用next_permutationSTL 库中提供的函数来生成数字的所有可能排列，然后选择每个排列的前两个元素。请注意，必须首先对序列进行排序，好像不会跳过先前的排列。

int nums[] = {1, 2, 3, 4};
while (next_permutation(nums, nums + 4)) {
    cout << nums[0] << ", " << nums[1] << endl;
}

请记住，您必须#include <algorithm>使用此功能。