Partial permutations

Question

I have the following recursive function for outputting partial combinations:

void comb(string sofar, string rest, int n) {

    string substring;

    if (n == 0)
        cout << sofar << endl;
    else {
        for (size_t i = 0; i < rest.length(); i++) {
            substring = rest.substr(i + 1, rest.length());
            comb(sofar + rest[i], substring, n - 1);
        }
    }
}

called like so:

comb("", "abcde", 3);

By partial combinations, I mean that it uses n choices and r elements (rather than n choices, n elements).

However, I would like to take the order of elements into account (i.e. permutations). I can find many algorithms for full permutations, but not partial.

Answer 1

You can do this with the standard library:

// Requires: sequence from begin to end is sorted
//           middle is between begin and end
template<typename Bidi, typename Functor>
void for_each_permuted_combination(Bidi begin,
                                   Bidi middle,
                                   Bidi end,
                                   Functor func) {
  do {
    func(begin, middle);
    std::reverse(middle, end);
  } while (std::next_permutation(begin, end));
}

This relies on the fact that next_permutation generates permutations in lexicographic order. So if the tail of the sequence is sorted, reversing the tail and then asking for the next permutation of the entire sequence moves the head to the next permutation of a subset, and leaves the tail once again sorted for the next iteration.

In case it's not obvious, the functor is called with a pair of iterators representing the range of the permuted combination.

Answer 2

It's time for a performance reality check here. If you are only interested in visiting the permutation of 5 things 3 at a time, stop reading now, as the number of visitations is so small that it doesn't matter much (unless perhaps you are doing this a billion times).

But if you need to visit more things, and more things at a time, performance can really start to matter. For example what about visiting the string of 26: "abcdefghijklmnopqrstuvwxyz", six items at a time? With permutations, costs grow very quickly...

For performance testing it is best to comment out the output to the terminal as that tends to be a very slow operation which swamps everything else.

This answer (the currently accepted one) looks like this:

#include <chrono>
#include <iostream>
#include <string>

using std::string;
using std::cout;

void comb(string sofar, string rest, int n)
{
    // std::cout << "comb('" << sofar << "', '" << rest << "', " << n << ")\n";
    string substring;

    if (n == 0)
        ; //cout << sofar << '\n';
    else {
        for (size_t i = 0; i < rest.length(); i++) {
            substring = rest.substr(0, i) + rest.substr(i + 1, rest.length());
            comb(sofar + rest[i], substring, n - 1);
        }
    }
}

int main()
{
    std::string s("abcdefghijklmnopqrstuvwxyz");
    auto t0 = std::chrono::steady_clock::now();
    comb("",s, 6);
    auto t1 = std::chrono::steady_clock::now();
    std::cout << std::chrono::duration<double>{t1-t0}.count() << '\n';
}

On my system (clang++ -std=c++14 test.cpp -O3) this outputs:

14.2002

This answer using std::next_permutation is significantly faster.

#include <algorithm>
#include <chrono>
#include <iostream>

// Requires: sequence from begin to end is sorted
//           middle is between begin and end
template<typename Bidi, typename Functor>
void for_each_permuted_combination(Bidi begin,
                                   Bidi middle,
                                   Bidi end,
                                   Functor func) {
  do {
    func(begin, middle);
    std::reverse(middle, end);
  } while (std::next_permutation(begin, end));
}

int
main()
{
    std::string s("abcdefghijklmnopqrstuvwxyz");
    auto t0 = std::chrono::steady_clock::now();
    for_each_permuted_combination(s.begin(), s.begin()+6, s.end(),
        [](auto first, auto last)
        {
//             for (; first != last; ++first)
//                 std::cout << *first;
//             std::cout << '\n';
        });
    auto t1 = std::chrono::steady_clock::now();
    std::cout << std::chrono::duration<double>{t1-t0}.count() << '\n';
}

which outputs:

8.39237

This is 69% faster! A lot of this speed increase can be attributed to the lack of allocation and deallocation that is implicit in the first algorithm.

However I would like to point you to an even faster algorithm.

The driver looks like:

#include "combinations"
#include <chrono>
#include <iostream>
#include <string>

int
main()
{
    std::string s("abcdefghijklmnopqrstuvwxyz");
    auto t0 = std::chrono::steady_clock::now();
    for_each_permutation(s.begin(), s.begin()+6, s.end(),
        [](auto first, auto last)
        {
//             for (; first != last; ++first)
//                 std::cout << *first;
//             std::cout << '\n';
            return false;
        });
    auto t1 = std::chrono::steady_clock::now();
    std::cout << std::chrono::duration<double>{t1-t0}.count() << '\n';
}

The output is:

0.2742

This is 30 times faster than the answer using std::next_permutation and 51 times faster than the currently accepted answer! And as n and r grow, the divergence of these performance numbers grows as well.

The linked library is free and open source. The implementation is at the link and can be copy/pasted out of it. I won't claim that it is simple. I only claim that its performance is compelling. The difference in performance is so dramatic that it can make the difference between making the problem solvable in a practical amount of time or not.

Answer 3

You want permutations, so you should capture characters before AND after i in substring:

substring = rest.substr(0, i) + rest.substr(i + 1, rest.length());

Complete program on coliru:

#include <iostream>
#include <string>

using std::string;
using std::cout;

void comb(string sofar, string rest, int n)
{
    // std::cout << "comb('" << sofar << "', '" << rest << "', " << n << ")\n";
    string substring;

    if (n == 0)
        cout << sofar << '\n';
    else {
        for (size_t i = 0; i < rest.length(); i++) {
            substring = rest.substr(0, i) + rest.substr(i + 1, rest.length());
            comb(sofar + rest[i], substring, n - 1);
        }
    }
}

int main()
{
    comb("", "abcde", 3);
}

Outputs (reformatted):

abc abd abe acb acd ace adb adc ade aeb aec aed
bac bad bae bca bcd bce bda bdc bde bea bec bed
cab cad cae cba cbd cbe cda cdb cde cea ceb ced
dab dac dae dba dbc dbe dca dcb dce dea deb dec
eab eac ead eba ebc ebd eca ecb ecd eda edb edc