Calculate possible merge order permutations

gistfile1.cpp

#include <iostream>
#include <vector>

using namespace std;

template <typename T>
void print_vector(vector<T> &A, size_t counter)
{
    cout << "" << counter << ") ";

    for (T i = 0; i < A.size(); i++)
            cout << (i > 0 ? (i == 1 ? " merge with " : ", then with ") : "") << A[i];

    cout << "." << endl;
}

template <typename T>
void show_merge_order_permutations(vector<T> &A)
{
    sort(begin(A), end(A));

    size_t counter = 1;
    do {
        // At the start it doesn't matter if you start with A -> B or B -> A, you're merging the same set.
        // I use less than comparison to filter out the duplicates at the beginning.. (This is 50%)
        while (A[0] < A[1]) {
            if (!next_permutation(begin(A), end(A)))
                return;
        }

        // Pretty print
        print_vector(A, counter++);
    }
    while (next_permutation(begin(A), end(A)));
}

int main (int argc, char *argv[])
{
    vector<int> A{1, 2, 3, 4};

    show_merge_order_permutations(A);

    /*
     * Outputs:
     * 1) 2 merge with 1, then with 3, then with 4.
     * 2) 2 merge with 1, then with 4, then with 3.
     * 3) 3 merge with 1, then with 2, then with 4.
     * 4) 3 merge with 1, then with 4, then with 2.
     * 5) 3 merge with 2, then with 1, then with 4.
     * 6) 3 merge with 2, then with 4, then with 1.
     * 7) 4 merge with 1, then with 2, then with 3.
     * 8) 4 merge with 1, then with 3, then with 2.
     * 9) 4 merge with 2, then with 1, then with 3.
     * 10) 4 merge with 2, then with 3, then with 1.
     * 11) 4 merge with 3, then with 1, then with 2.
     * 12) 4 merge with 3, then with 2, then with 1.
     */

    vector<char> B{'P', 'Q', 'R'};

    show_merge_order_permutations(B);

    /**
     * Outputs:
     * 1) Q merge with P, then with R.
     * 2) R merge with P, then with Q.
     * 3) R merge with Q, then with P.
     */
}