next_permutation

03 Aug 2013 C++, next_permutation, stl

Working on a small program recently I found a quirk in next_permutation. The prorgam read a sequence of characters from the command line and then tried to find words by testing each permuation. For a sequence of 3 characters there are 6 permutations.

Most of the online examples look something like this:

    vector<int> set {'a', 'b', 'c'};
    
    do {
        for (auto x : set)
            cout << (char)x;
        cout << endl;
    } while (next_permutation(set.begin(), set.end()));

Which produces:

abc
acb
bac
bca
cab
cba

No surprises but when I cam to process input like ‘bac’ the number of permutations found were far too small.

bac
bca
cab
qcba

The problem is that the next_permutation modifies or mutates the vector so it needs to have a state to know when it has completed. That state is the vector itself. next_permutation returns false when all the elements are in increasing order.

To work with arbitrary input the sequence first needs to be sorted.

	set = {'b', 'a', 'c'};
    
    sort(set.begin(), set.end());
    
    do {
        for (auto x : set)
            cout << (char)x;
        cout << endl;
    } while (next_permutation(set.begin(), set.end()));

which now produces the right result

abc
acb
bac
bca
cab
cba

Linkedin

Graham Brooks Photo

This is a personal weblog. The opinions expressed here represent my own and not those of my employer (ThoughtWorks).

My thoughts and opinions change over time as I learn. This weblog is intended to provide a semi-permanent record of these thoughts and is for informational purposes only.

comments powered by Disqus