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

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