All combinations of two pairs of elements of an array

Question

Suppose I have an array of objects. Without loss of generality, it could be an array of indices: $$a = (0, 1, 2, ..., n)$$ Now suppose I want to choose two pairs of elements of this array. The order is not of the matter inside pairs so for pairs itself.

For example if $$a = (1,2,3,4)$$ then all those combinations would be $$(1,2), (3,4)\\(2,3), (1,4)\\...$$ But combinations like $$(1,2), (3,4)\quad \text{and}\quad (4,3), (1,2)$$ should be considered as equivalent.

I am a little bit confused how to write compact and effective algorithm for my purpose. I feel that there is a way to do it for general case (not just for pairs) but I cannot find it. If you know, please share.

So far, here is my code.

#include <iostream>
#include <algorithm> 
#include <vector>
int main()
{
 std::vector< int > targetVector = { 1, 2, 3, 4, 5 };
 std::vector< int > index_pair = { 2, 2, 1, 1, 0 };
 int pair1, pair2;
 do
 {
 //reset pairs to 00000
 pair1 = pair2 = 0;
 for ( int i = 0; i < (int)index_pair.size(); i++ )
 {
 if( index_pair[i] == 1 ) { pair1 += ( 1 << (i+1) ); }
 if( index_pair[i] == 2 ) { pair2 += ( 1 << (i+1) ); }
 }
 if ( pair1 > pair2 )
 {
 for ( auto index : index_pair )
 {
 std::cout << index;
 }
 std::cout << "\n";
 }
 }while( prev_permutation( index_pair.begin(), index_pair.end() ) );
 return 0;
}

Here is the output that seems to be right.

22110
22101
22011
21210
21201
21021
20211
20121
12210
12201
12021
10221
02211
02121
01221

• papagaga: There's no substantial difference I can see between what you're asking and the more classical combinatoric problem of enumerating distinct subsets in a set: en.wikipedia.org/wiki/Combination. Just cut your 4-element subset in two and you'll have your pairs. So you would find a general answer in stackoverflow.com/questions/9430568/…. Or, if you want to generate them one at a time, and if you don't mind the self-promotion: codereview.stackexchange.com/questions/184586/…
• paraxod: I think it only works if an array consists of exactly 4 elements. Then yes, it is sufficient to choose only one pair. This does not work if there are more than 4 elements because one pair can belong to different combinations.
• Toby Speight: How do you get the pair (4,5) from the array (1,2,3,4)? Am I missing something, or is there a typo?
• paraxod: Good catch! Thank you for noticing. Edited.

Answer 1

Unused variables

We never use targetVector, so we can omit its definition.

Reduce scope

We can move pair1 and pair2 inside of the do loop.

Don't cast to signed

This looks like a misguided attempt to appease a compiler warning:

 for (int i = 0; i < (int)index_pair.size(); i++) {

Whilst it's good that you have enabled a good set of warnings, the better response would be to change the type of i to match (especially as we intend to use it as an indexer):

 for (std::size_t i = 0u; i < index_pair.size(); ++i) {

We can also simplify the if chain if we use a small array for pair:

 std::size_t pair[3] = {};
 for (std::size_t i = 0u; i < index_pair.size(); ++i)
 pair[index_pair[i]] += 1u << (i+1);
 if (pair[1] > pair[2]) {

We could use range-based for instead:

 std::size_t n = 0;
 for (auto i: index_pair)
 pair[i] += 1u << ++n;

It's not obvious whether this is better than the index loop, but you might prefer it.

A typo

You appear to have misspelt std::prev_permutation in the while condition.

---

Modified code

Without changing the algorithm, I have simplified to just

#include <algorithm>
#include <iostream>
#include <vector>
int main()
{
 std::vector<int> index_pair = { 2, 2, 1, 1, 0 };
 do {
 std::size_t pair[3] = {};
 for (std::size_t i = 0u; i < index_pair.size(); ++i)
 pair[index_pair[i]] += 1u << (i+1);
 if (pair[1] > pair[2]) {
 for (auto index: index_pair) {
 std::cout << index;
 }
 std::cout << "\n";
 }
 } while (std::prev_permutation(index_pair.begin(), index_pair.end()));
}

• paraxod: Thank you for a lot of useful remarks and corrections. P.S. it was really a typo with 'prev_permutation' but it compiles without warnings or errors. I use '-std=c++1y'.
• Toby Speight: It compiled cleanly for me, with GCC 7.2 and -std=c++17. I'm not sure whether argument-dependent lookup finds the function, or whether it somehow makes its way into the global namespace (and I would appreciate clarification here!). I'm constantly writing size_t without its std:: (and did so several times writing my version), possibly because I also write some C from time to time.