2-組み合わせC++

Question

は、私は、例えば、長さ2の配列にそれらの全て2-組合せを配置する必要があり：

仮定する櫛は、2次元アレイです。私は櫛ために、すべての2 - の組み合わせを配置する必要があり

n = 1,2,3 

ような[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 =トータル可能答えプットi番目のインデックス付けnの各要素について

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

簡単な方法の1つは、数字の可能なすべての順列を生成するために、next_permutation関数をSTLライブラリで使用し、それぞれの最初の2つの要素を選択することです。シーケンスが最初にソートされる必要があることに注意してください。前の並べ替えがスキップされないかのように

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

この機能を使用するには、#include <algorithm>を使用する必要があります。これをさらに最適化することが

// 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

セルcomb[length(n) - i][j]のi番目のインデックス付きj番目を除く、nのすべての要素。

Answer 3

は、次のN^2のアプローチを考えることができます。