# All combinations of two pairs of elements of an array

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

• 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/… – papagaga Jan 31 '18 at 9:58
• 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. – paraxod Jan 31 '18 at 10:58
• How do you get the pair (4,5) from the array (1,2,3,4)? Am I missing something, or is there a typo? – Toby Speight Jan 31 '18 at 15:38
• Good catch! Thank you for noticing. Edited. – paraxod Feb 1 '18 at 4:41

# 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()));
}

• 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'. – paraxod Feb 1 '18 at 4:50
• 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. – Toby Speight Feb 1 '18 at 8:44