-1

n 個の要素の配列があります。それらの 2 つの組み合わせすべてを長さ 2 の配列に入れる必要があります。次に例を示します。

櫛が2次元配列であるとします。

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

}

4

3 に答える 3

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

おそらくこれをさらに最適化するのは簡単です。

于 2012-05-05T22:02:14.377 に答える
0

簡単な方法の 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>この機能を使用する必要があることに注意してください。

于 2012-05-05T20:39:59.390 に答える
0

nインデックス付き ithの各要素に対してn、 cell 内の i 番目のインデックス付き j を除くすべての要素を配置しますcomb[length(n) - i][j]。

于 2012-05-05T20:37:19.993 に答える