Yes, there is a "next permutation" algorithm, and it's quite simple too. The C++ standard template library (STL) even has a function called next_permutation
.
The algorithm actually finds the next permutation -- the lexicographically next one. The idea is this: suppose you are given a sequence, say "32541". What is the next permutation?
If you think about it, you'll see that it is "34125". And your thoughts were probably something this: In "32541",
- there is no way to keep the "32" fixed and find a later permutation in the "541" part, because that permutation is already the last one for 5,4, and 1 -- it is sorted in decreasing order.
- So you'll have to change the "2" to something bigger -- in fact, to the smallest number bigger than it in the "541" part, namely 4.
- Now, once you've decided that the permutation will start as "34", the rest of the numbers should be in increasing order, so the answer is "34125".
The algorithm is to implement precisely that line of reasoning:
- Find the longest "tail" that is ordered in decreasing order. (The "541" part.)
- Change the number just before the tail (the "2") to the smallest number bigger than it in the tail (the 4).
- Sort the tail in increasing order.
You can do (1.) efficiently by starting at the end and going backwards as long as the previous element is not smaller than the current element. You can do (2.) by just swapping the "4" with the '2", so you'll have "34521". Once you do this, you can avoid using a sorting algorithm for (3.), because the tail was, and is still (think about this), sorted in decreasing order, so it only needs to be reversed.
The C++ code does precisely this (look at the source in /usr/include/c++/4.0.0/bits/stl_algo.h
on your system, or see this article); it should be simple to translate it to your language: [Read "BidirectionalIterator" as "pointer", if you're unfamiliar with C++ iterators. The code returns false
if there is no next permutation, i.e. we are already in decreasing order.]
template <class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first,
BidirectionalIterator last) {
if (first == last) return false;
BidirectionalIterator i = first;
++i;
if (i == last) return false;
i = last;
--i;
for(;;) {
BidirectionalIterator ii = i--;
if (*i <*ii) {
BidirectionalIterator j = last;
while (!(*i <*--j));
iter_swap(i, j);
reverse(ii, last);
return true;
}
if (i == first) {
reverse(first, last);
return false;
}
}
}
It might seem that it can take O(n) time per permutation, but if you think about it more carefully, you can prove that it takes O(n!) time for all permutations in total, so only O(1) -- constant time -- per permutation.
The good thing is that the algorithm works even when you have a sequence with repeated elements: with, say, "232254421", it would find the tail as "54421", swap the "2" and "4" (so "232454221"), reverse the rest, giving "232412245", which is the next permutation.
Here is a simple solution to compute the nth permutation of a string:
function string_nth_permutation(str, n) {
var len = str.length, i, f, res;
for (f = i = 1; i <= len; i++)
f *= i;
if (n >= 0 && n < f) {
for (res = ""; len > 0; len--) {
f /= len;
i = Math.floor(n / f);
n %= f;
res += str.charAt(i);
str = str.substring(0, i) + str.substring(i + 1);
}
}
return res;
}
The algorithm follows these simple steps:
- first compute
f = len!
, there are factorial(len)
total permutations of a set of len
different elements.
- as the first element, divide the permutation number by
(len-1)!
and chose the element at the resulting offset. There are (len-1)!
different permutations that have any given element as their first element.
- remove the chosen element from the set and use the remainder of the division as the permutation number to keep going.
- perform these steps with the rest of the set, whose length is reduced by one.
This algorithm is very simple and has interesting properties:
- It computes the n-th permutation directly.
- If the set is ordered, the permutations are generated in lexicographical order.
- It works even if set elements cannot be compared to one another, such as objects, arrays, functions...
- Permutation number
0
is the set in the order given.
- Permutation number
factorial(a.length)-1
is the last one: the set a
in reverse order.
- Permutations outside this range are returned as undefined.
It can easily be converted to handle a set stored as an array:
function array_nth_permutation(a, n) {
var b = a.slice(); // copy of the set
var len = a.length; // length of the set
var res; // return value, undefined
var i, f;
// compute f = factorial(len)
for (f = i = 1; i <= len; i++)
f *= i;
// if the permutation number is within range
if (n >= 0 && n < f) {
// start with the empty set, loop for len elements
for (res = []; len > 0; len--) {
// determine the next element:
// there are f/len subsets for each possible element,
f /= len;
// a simple division gives the leading element index
i = Math.floor(n / f);
// alternately: i = (n - n % f) / f;
res.push(b.splice(i, 1)[0]);
// reduce n for the remaining subset:
// compute the remainder of the above division
n %= f;
// extract the i-th element from b and push it at the end of res
}
}
// return the permutated set or undefined if n is out of range
return res;
}
clarification:
f
is first computed as factorial(len)
.
- For each step,
f
is divided by len
, giving exacty the previous factorial.
n
divided by this new value of f
gives the slot number among the len
slots that have the same initial element. Javascript does not have integral division, we could use (n / f) ... 0)
to convert the result of the division to its integral part but it introduces a limitation to sets of 12 elements. Math.floor(n / f)
allows for sets of up to 18 elements. We could also use (n - n % f) / f
, probably more efficient too.
n
must be reduced to the permutation number within this slot, that is the remainder of the division n / f
.
We could use i
differently in the second loop, storing the division remainder, avoiding Math.floor()
and the extra %
operator. Here is an alternative for this loop that may be even less readable:
// start with the empty set, loop for len elements
for (res = []; len > 0; len--) {
i = n % (f /= len);
res.push(b.splice((n - i) / f, 1)[0]);
n = i;
}
Best Answer
As stated by RickyBobby, when considering the lexicographical order of permutations, you should use the factorial decomposition at your advantage.
From a practical point of view, this is how I see it:
(n-1)!
,(n-2)!
, and so on.i
-th quotient should be a number between0
andn-i-1
inclusive, wherei
goes from0
ton-1
.The following C code should give you an idea of how this works (
n
is the number of entries, andi
is the index of the permutation):For example,
ithPermutation(10, 3628799)
prints, as expected, the last permutation of ten elements: