-1

I have an array of n elements, I need to put all 2- combination of them into arrays of length 2. for example:

suppose comb is a 2 dimensional array.

n = 1,2,3

I need to put all 2- combinations to comb[i][j] like that:

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

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

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

I do not know how to write the code! Thanks

My Answer:

The O(n!) answer: n = total number m= total possible answer

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

}

7
  • 2
    Is this homework? What have you tried? Anyway, you should remove those braces.
    – chris
    May 5, 2012 at 20:27
  • I'm afraid if StackOverflow would be helpful for doing your homework ;-)
    – g13n
    May 5, 2012 at 20:32
  • @g13n, SO can definitely give great help with homework, but if it's homework, you should be doing it yourself. Most of the time, all it takes is an idea to build on. If you come to get other people to do your homework, why did you enroll in the course in the first place?
    – chris
    May 5, 2012 at 20:34
  • what the hell is going on here ? who said that its homework? its a part of a project and I wanted to know the optimized solution for data more than 1000 000! . if you do not know the answer do not spam it !
    – Bipario
    May 5, 2012 at 20:44
  • @Bipario, I was merely asking because it has the looks of a homework question. Whether it is influences what type of answers you will receive.
    – chris
    May 5, 2012 at 20:56

3 Answers 3

1

Can think of the following N^2 approach:

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

Probably easy to optimize this further.

2
  • Think that an algortihm with worst-case time of less than O(n^2) will probably not be possible, since the output with unique numbers scales at n^2, e.g. there are 3 combinations for 3 and 45 combinations for 10 unique elements.
    – smocking
    May 5, 2012 at 22:08
  • Thanks. This is a good answer. I have O(n!) answer , I post it now
    – Bipario
    May 5, 2012 at 23:51
0

One easy way is using the next_permutation function available in the STL library in order to generate all the possible permutations of your numbers, and then pick the first two elements of each one. Note that the sequence must be first sorted, as if not the previous permutations will be skipped.

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

Remember that you must #include <algorithm> to use this function.

6
  • thanks. I have many numbers, not just 3. so computing all the permutation costs alot of memory. The order is not important for me and I just want to store all the 2- combinations. Is there any other optimized way?
    – Bipario
    May 5, 2012 at 20:43
  • It doesn't matter how many numbers you have, as this uses no extra memory (the elements are rearranged in the original array)
    – Win32
    May 5, 2012 at 20:44
  • 1
    Are you sure? so, I should only call the next_permutation and only select the first two elements of each permutation? what about the order of the algorithm?
    – Bipario
    May 5, 2012 at 20:51
  • 1
    @Bipario: this is an O(n!) algorithm, and generates a lot more rows than you need. fails if the numbers are not sorted. also I guess it's a too high-level solution for your homework. you shouldn't accept this as an answer. May 5, 2012 at 20:58
  • 1
    @Bipario, the problem is that it's getting permutations of a larger set than you need. For example, you'd be going through {1,2,3,4}, {1,2,4,3}, for just {1,2} in both cases if all you want is two elements.
    – chris
    May 5, 2012 at 21:05
0

For each element in n indexed ith put every elements in n except the ith indexed jth in cell comb[length(n) - i][j].

4
  • wrong indexes.. and please don't give a full solution for his homework. May 5, 2012 at 20:38
  • @Karoly I must be tired I don't see the problem ?
    – log0
    May 5, 2012 at 20:40
  • compare your algo with his example May 5, 2012 at 20:42
  • Well there is no point to give me hints ... Edit my answer if you want. Anyway I think my answer is enough to help the OP. My answer does not assume that 0 address the first element and is also not very explicit about j, but well the goal is to not give directly the answer...
    – log0
    May 5, 2012 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.