[Math] Finding next permutation of a number.

combinatorics

I need to code some problem and I need help permutating the numbers.
The problem is:

Given a permutation of the numbers $1,2,3,\ldots,n$ e.g. $n=5$ and permutation is $43251$. I need to find the next permutation whch in this case is $43512$ which is the smallest number formed by permuting the given numbers larger than the given number.
For example permutation set of $1,2,3$ is $123\to132\to213\to231\to312\to321$.

I know total permutations are $n!$. I need to manipulate the given number, the easiest way but dangerous too is keep adding 1 to the number until it becomes a permutation of the given no. eg $123\to124\to125\ldots131\to132$ but when n is large it may take lot of time.

Another method I thought is creating an ordered set of permutation of given number and then looking uup the next number but I am unsure how to create that list, cause if there was a definite algorithm to create an algorithm i would have directly used that for e.g. $f(n,j)=\text{j$^{th}$ permutation of n numbers}$ such that $f(3,2)=132$.

Last thing I thought was to exchange the last two digits if second last digit is less than the last one. but could not generalize this for other places(hundreds, thousands, etc.)

Is there such an algorithm or the number can be manipulated to the next permutation.

Best Answer

The algorithm to find the next permutation is not too hard. Suppose we want the permutation that follows $P$. We'll write $P[n]$ to mean the $n$th element of $P$. For example, if $P$ is $dceab$ then $P[3]$ is $e$ and $P[5]$ is $b$. (I've used used $a,b,c,d,e$ as synonyms for $1,2,3,4,5$ so that it's clear which numbers are indices and which are elements being permuted.)

  1. Find the rightmost position, $k$, at which $P[k] < P[k+1]$. If there is no such $k$, then halt; $P$ is the last permutation.
  2. Find the index $j$ to the right of $k$ (that is, $j>k$) for which $P[j]$ is as small as possible, but still bigger than $P[k]$. (Such $j$ must exist since $P[k+1] > P[k]$.)
  3. Swap $P[j]$ with $P[k]$.
  4. Sort the elements to the right of position $k$ into ascending order.

Example 1: Take $P=dcbea$. First we find $k=3$, because position $3$ is the rightmost position that contains a value less than the next position ($P[3] = b < e = P[4]$).

Then we find $j$ to the right of position $3$ for which $P[j]>P[k]$ but as small as possible. That is $j=4$, which is the $e$.

Then we swap the $b$ and the $e$, obtaining $dceba$, and then we sort the items in positions $k+1$ though the end, that's the $b$ and the $a$, into ascending order, so $dceab$.

Example 2: Take $P=eabgfdc$. Then we find $k=3$, because position $3$ is the rightmost position that contains a value less than the value in the next position. (Here position $3$ contains $b$, and the next position $4$ contains $g$.) Then we find $j=7$, which is the position to the right of position $3$ that contains the smallest value still greater than $P[k]$; it contains $P[7]=c$ which is greater than $P[3]=b$. We swap positions $3$ and $7$, obtaining $eacgfdb$, and then sort positions $4$ through $7$ into ascending order, obtaining $eacbdfg$.

Example 3: Take $P=ecgbfda$. Then we find $k=4$, because position $4$ is the rightmost position that contains a value less than the value in the next position. (Here position $4$ contains $b$, and the next position $5$ contains $f$.) Then we find $j=6$, which is the position to the right of position $4$ that contains the smallest value still greater than $P[k]$; it contains $P[6]=d$ which is greater than $P[4]=b$. We swap positions $4$ and $6$, obtaining $ecgdfba$, and then sort positions $5$ through $7$ into ascending order, obtaining $ecgdabf$.

Related Question