## Next Permutation

Friday, March 2, 2012

Yesterday, I noticed a programming challenge to find the “next greater permutation of digits” for a given number:

Given a number, find the next higher number that uses the same set of digits. For instance, given the number 38276, the next higher number that uses the digits 2 3 6 7 8 is 38627.

While reading the comments, I noticed that some of the C++ solutions
used the
std::next_permutation
function that returns the “lexicographically next greater permutation of
elements”. Noticing that the
math.combinatorics
vocabulary lacks a `next-permutation`

word, I thought it would be nice
to contribute one to the Factor standard
library.

### std::next_permutation()

It’s a useful place to start to get an overview and example of how the algorithm works. The C++ version is pretty dense and looks like this:

```
template<typename Iter
bool next_permutation(Iter first, Iter last)
{
if (first == last)
return false;
Iter i = first;
++i;
if (i == last)
return false;
i = last;
--i;
for(;;)
{
Iter ii = i;
--i;
if (*i < *ii)
{
Iter j = last;
while (!(*i < *--j))
{}
std::iter_swap(i, j);
std::reverse(ii, last);
return true;
}
if (i == first)
{
std::reverse(first, last);
return false;
}
}
}
```

### Example!

Walking through an example of the algorithm is particularly helpful to understand it:

As an example consider finding the next permutation of:

8342666411The longest monotonically decreasing tail is 666411, and the corresponding head is 8342.

8342 666411666411 is, by definition, reverse-ordered, and cannot be increased by permuting its elements. To find the next permutation, we must increase the head; a matter of finding the smallest tail element larger than the head’s final 2.

8342 666411Walking back from the end of tail, the first element greater than 2 is 4.

8342 666411Swap the 2 and the 4

8344 666211Since head has increased, we now have a greater permutation. To reduce to the next permutation, we reverse tail, putting it into increasing order.

8344 112666Join the head and tail back together. The permutation one greater than 8342666411 is 8344112666.

### Implementation

We can use the steps in the example above to help organize our code. First, we find the “cut point” which is the index to the left of the longest monotonic tail:

```
: cut-point ( seq -- n )
[ last ] keep [ [ > ] keep swap ] find-last drop nip ;
```

Next, we want to find the smallest element larger than the element at the “cut point” (searching from the end of the sequence):

```
: greater-from-last ( n seq -- i )
[ nip ] [ nth ] 2bi [ > ] curry find-last drop ;
```

We then need a way to reverse the tail of a sequence (the `!`

denotes
that this modifies the sequence in-place):

```
: reverse-tail! ( n seq -- seq )
[ swap 1 + tail-slice reverse! drop ] keep ;
```

Putting this together gives us a word that looks a bit like our example. I have decided that in the case where the sequence reaches its lexicographic greatest order, we reverse it to its smallest ordering. This allows it to cycle through all possible permutations no matter where you start.

```
: (next-permutation) ( seq -- seq )
dup cut-point [
swap [ greater-from-last ] 2keep
[ exchange ] [ reverse-tail! nip ] 3bi
] [ reverse! ] if* ;
```

We wrap this with a simple check to make sure the sequence is not empty. Arguably, we could instead check if the length is greater than 1 since a single element sequence has only possible permutation.

```
: next-permutation ( seq -- seq )
dup [ ] [ drop (next-permutation) ] if-empty ;
```

### Testing

Factor makes it easy to do unit tests. Here are some of the ones I’ve used to test this code:

```
{ "" } [ "" next-permutation ] unit-test
{ "1" } [ "1" next-permutation ] unit-test
{ "21" } [ "12" next-permutation ] unit-test
{ "8344112666" } [ "8342666411" next-permutation ] unit-test
{ "ABC" "ACB" "BAC" "BCA" "CAB" "CBA" "ABC" }
[ "ABC" 6 [ dup >string next-permutation ] times ] unit-test
```

This is available in the latest development branch of Factor.

### Bonus

Solving the original programming challenge is as easy as:

```
IN: scratchpad 38276 number>string next-permutation string>number .
38627
```