---
title: next_permutation
url: https://www.grahambrooks.com/post/2013-08-03-next_permutation/
date: 2013-08-03T00:00:00+00:00
author: Graham Brooks
tags:
- C++
---

# next_permutation

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:

```cpp
    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.

```cpp
	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

```cpp
abc
acb
bac
bca
cab
cba
```