## Next Greater Permutation Of Digits

### February 28, 2012

The basic algorithm is simple enough. Consider the input number 135798642. First split the number into two halves, with the second half containing the maximal set of digits in descending order: 1357 98642. Now find the smallest digit in the second half that is greater than the last digit of the first half, and swap them; in our case the last digit of the first half is 7, the next greater digit in the second half is 8, and the swap is 1358 97642. Reverse the back half and put the two halves back together to get the result: 1358 24679.

Once you have the basic algorithm, writing code is still tricky because there are a lot of edge cases to consider. Here’s my solution, for which I know no incorrect results, but I’m not convinced that it is correct. First we split the front off the rest of the number:

```(define (split-front ds)   (let loop ((fs (cdr ds)) (bs (list (car ds))))     (cond ((null? fs) (values fs bs))           ((< (car fs) (car bs)) (values fs bs))           (else (loop (cdr fs) (cons (car fs) bs))))))```

This is called with the digits of the original number in reverse order, so the result of `(split-front (reverse (digits 135798642)))` is the two lists `(7 5 3 1)` and `(9 8 6 4 2)`; note that the front half of the number is in reverse order. Next we split and reassemble the back half of the number:

```(define (split-back bs s)   (let loop ((bs bs) (rs (list)))     (if (< (car bs) s)         (loop (cdr bs) (cons (car bs) rs))         (values (append (cdr bs) (list s) rs)                 (car bs)))))```

Again we reverse the digits before calling the function, so the result of `(split-back '(2 4 6 8 9) 7)` is the list `(9 7 6 4 2)` and the digit `8`. The calling function splits and packs the digits of the input, does the necessary reversals, and keeps track of the processing:

```(define (next-perm n)   (call-with-values     (lambda () (split-front (reverse (digits n))))     (lambda (fs bs)       (if (null? fs) #f ; no solution         (call-with-values           (lambda () (split-back (reverse bs) (car fs)))           (lambda (bs s) (undigits (append             (reverse (cdr fs)) (list s) (reverse bs)))))))))```

Here are some examples:

```> (next-perm 38276) 38627 > (next-perm 135798642) 135824679```

We used digits and undigits from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/ljirZyCY.

Pages: 1 2

### 24 Responses to “Next Greater Permutation Of Digits”

1. Kwiatki said

Same algorithm as OP, obviously as it is correct.

2. DGel said

I’m pretty sure there’s an error in OP’s solution:
(next-perm 2643) returns 3264 instead of 3246, which would be the smaller next permutation.

Tried my hand at a Haskell solution, but it doesn’t handle all edge cases yet.. will continue later

3. DGel said

whelp, this seems to work, but probably doesn’t. Suggestions for improving it are welcome:

```module Main where
import Data.List

split b = foldl' whileIncr ([],[]) (reverse b) where
whileIncr ([],[]) z = ([],[z])
whileIncr ([],x) z
| (head x) <= z = ([], z:x)
| otherwise = ([z],x)
whileIncr (y,x) z = (z:y,x)

merge ([],b) = b
merge (a,b) = (init a) ++ (swap (last a) sl [] (reverse b)) where
sl = (findSmall (last a) b)
swap a sl b (x:xs)
| sl == x = (sl : b) ++ [a] ++ xs
| otherwise = swap a sl (b ++ [x]) xs

findSmall a xs = foldl' (smallestLarger a) 10 xs where
smallestLarger a x y
| y > a = min x y
| otherwise = x

numToList a = [read [x] :: Integer | x <- show a]
listToNum :: [Integer] -> Integer
listToNum = read . concatMap show

nextPermutation :: Integer -> Integer
nextPermutation = listToNum . merge . split . numToList
```
4. programmingpraxis said

Dammit, I don’t get the job.

5. Here’s some idiomatic Ruby code that does the job:

```def next_greater_permutation(n)
greater_perms = []
n.to_s.chars.to_a.permutation do |perm|
n_perm = perm.join.to_i
if (n_perm > n) then
greater_perms.push n_perm
end
end

greater_perms.sort!
return greater_perms.fetch(0)
end

puts next_greater_permutation(38276)
```

Here’s the gist of the algorithm:

1 – Find all the permutations which are strictly greater than the input.
2 – Store those numbers in a list for easy retrieval.
3 – Sort the aforementioned list, and return the element in its first position.

6. Mike said

Here are two Python solutions.

This one uses brute force. It generates the permutations of the digits in lexicographical order and returns the first permutation that is larger than the argument.

```import itertools as it

def next_permutation(n):
s = tuple(str(n))
for x in it.dropwhile(lambda p: p <= s, it.permutations(sorted(s))):
return int(''.join(x))

```

This function analyzes the digits of the number to identify which two digits to swap.

```def next_permutation(n):
s = list(str(n))

for j in range(len(s)-2,-1,-1):
if s[j] < s[j+1]:
k = s.index(min(d for d in s[j+1:] if d > s[j]))

s = s[:j] + s[k:k+1] + sorted(s[j:k] + s[k+1:])

return int(''.join(s))

```

s[:j] is the leading digits which do not change
s[j+1:] is the tail, which is a sequence of decreasing digits at the end of the number
s[j] is the digit to be swapped into the tail
s[k] is the smallest digit in the tail that is > s[j]

7. nz said

Another Haskell solution, I’ve reused DGels number conversion functions.

nextPerm is the generic list permuting function (nextPerm :: Ord a => [a] -> [a]), and nextPermutedNum is the actual solution.

```next zs [] = reverse zs
next zs (y:ys) = if head zs<=y then next (y:zs) ys
else swp zs
where
swp [z] = y:z:ys
swp (z:zz:zs) = if zz>y then  z:swp (zz:zs)
else  y:zz:zs++z:ys

nextPerm [] = []
nextPerm ys = reverse \$ next [x] xs
where x:xs = reverse ys

numToList a = [read [x] :: Integer | x <- show a]

listToNum :: [Integer] -> Integer
listToNum = read . concatMap show

nextPermutedNum :: Integer -> Integer
nextPermutedNum = listToNum . nextPerm . numToList```

example:

```*Main> take 10 \$ iterate nextPermutedNum 135798642
[135798642,135824679,135824697,135824769,135824796,135824967,135824976,135826479,135826497,135826749]
```
8. And now C++, mostly low level apart from string and swap.

```#include <iostream>
#include <string>
#include <algorithm>

bool make_next_perm(std::string& p)
{
int n = p.length(), i = n - 1, j = i, k = i;
while (i && p[i - 1] > p[i]) --i;
if (!i) return false;
while (p[j] <= p[i - 1]) --j;
std::swap(p[i - 1], p[j]);
while (i < k) std::swap(p[i++], p[k--]);
return true;
}

int main()
{
std::string s("12345");

do {
std::cout << s << '\n';
} while(make_next_perm(s));

return 0;
}
```
9. ardnew said

I’ve used the same algorithm as Tomasz in a few other posts on this site.

I believe the algorithm was discovered as early as 1812! Seems to be most often credited to a couple of German authors named Fischer and Krause. Unfortunately, I can’t find much information regarding the original literature.

If anyone has any further information, I would love to read it

10. nz said

Using the C++ standard library this is much simpler:

```#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
main(){
string s("12643");
next_permutation(s.begin(),s.end());
cout<<s<<'\n';

}
```
11. Jussi Piitulainen said

Wikipedia (Permutation, Generation in lexicographic order) says: “The method goes back to Narayana Pandita [sic] in 14th century India, and has been frequently rediscovered ever since.”
(sourced to Knuth’s TAoCP 4 fascicle 2, Generating all tuples and permutations, which I have but not at hand now).

(The Wikipedia article on the credited mathematician is about Narayana Pandit (1340–1400). “Pandita” looks like a typo.)

12. Graham said

My 2 cents in Haskell, since I’m trying to brush up on (read: learn) it.

```import Data.List (permutations, sort)

digits :: Integer -> [Integer]
digits = reverse . digs where
digs 0 = []
digs n = n `rem` 10 : digs (n `quot` 10)

undigits :: [Integer] -> Integer
undigits = sum . zipWith (*) (iterate (*10) 1) . reverse

brute :: Integer -> Integer
brute n = head . dropWhile (<= n) . map undigits . sort . permutations . digits \$ n

faster :: Integer -> Integer
faster = undigits . reverse . f . reverse . digits where
f [x] = [x]
f (x:y:zs) | x > y     = y : x : zs
| otherwise = y : (f \$ x:zs)
```

`brute` is the obvious, slow, brute force option; hopefully `faster` lives up to its name.

13. sweetopiagirl said

Reblogged this on Inspiredweightloss.

14. Axio said

I guess it’s mega overkill, but it does the job :)
Recursive, *non-bruteforce* algorithm.
If the recursive call returns a different list, there’s been reordering, so just cons current head to returned value.
Otherwise, find next element to replace current head, cons it to the sorted rest of the list from which the next element has been removed.

```;; next greater permutation of digits
;; 1234 -> 1243 -> 1324 -> 1342 -> 1423 -> 1432 -> 2134 ->
;; 2143 -> 2314 -> 2341 -> 2413 -> 2431 -> 3124 -> 3142 ->
;; 3214 -> 3241 -> 3412 -> 3421 -> 4123 -> 4132 -> 4213 ->
;; 4231 -> 4312 -> 4321

(define (ngpd n)
(digits->number
(foo (digits n))))

(define (sorted? l)
(or (null? l)
(fold-left (lambda (r e) (and (number? r) (>= r e) e)) (car l) l)))

(define (just-above x l)
(let loop ((y +inf.0) (l l))
(if (null? l)
y
(if (and (> (car l) x)
(< (car l) y))
(loop (car l) (cdr l))
(loop y (cdr l))))))

(define (remove-once x l)
(if (null? l)
l
(if (= x (car l))
(cdr l)
(cons (car l) (remove-once x (cdr l))))))

(define (insert x l)
(if (null? l)
(list x)
(if (<= x (car l))
(cons x l)
(cons (car l) (insert x (cdr l)))))  )

(define (foo l)
(if (sorted? l)
l
(let ((sub (foo (cdr l))))
(if (eq? sub (cdr l))
(let* ((new-head (just-above (car l) l))
(rest (quick-sort-by < (remove-once new-head sub))))
(cons new-head (insert (car l) rest)))
(cons (car l) sub)))))

;; List'em all!
(define (test n)
(let loop ((last-seen n))
(let ((next (ngpd last-seen)))
(if (eq? last-seen next)
`(,last-seen)
(cons last-seen (loop next))))))
```
15. Jussi Piitulainen said

Scheme to advance a vector to the lexicographically next permutation, or index out of bounds if there is no such:

```(define (next! vec les)
(define m (- (vector-length vec) 1)) (define (v k) (vector-ref vec k))
(define (! j k)
(let ((t (v j))) (vector-set! vec j (v k)) (vector-set! vec k t)))
(do ((j m (- j 1)))
((les (v (- j 1)) (v j))        ;found vj (at j-1)
(do ((k m (- k 1)))
((les (v (- j 1)) (v k))   ;found vk
(! (- j 1) k)             ;swap vj and vk
(do ((j j (+ j 1)) (k m (- k 1)))
((<= k j))
(! j k)))))))           ;reverse from j on
```

I knew I would make msitakes, so I tested it. (I had made an off-by-one, and got a comparison the wrong way around, and even called a procedure with a wrong number of arguments :( Hire me?

```(define (test p n)
(display p) (newline)
(do ((n n (- n 1))) ((= n 0)) (next! p <) (display p) (newline)))
```

It steps the vector so:

```> (test (vector 3 4 5 1 1) 4)
#(3 4 5 1 1)
#(3 5 1 1 4)
#(3 5 1 4 1)
#(3 5 4 1 1)
#(4 1 1 3 5)
```
16. Simon said

#include
#include
#include
using namespace std;

bool myfunction(int m,int n) {
return (m>n);
}

int main() {
int num = 1, i, j, size, * num_array, temp;
while (num != 0) {
cin >> num;
temp = num;
for (i = 1; temp != 0; i++) {
temp /= 10;
}
size = i-1;
num_array = new int[size];
for (i = 0; num != 0; i++) {
num_array[i] = num%10; // array reversed
num /= 10;
}
for (j = 0; j < i; j++) {
temp = num_array[j];
for (int k = j+1; k < i; k++){
if (num_array[k] < temp) {
i = j; // store j in i
j = k-1; // break second loops, store k in j (note i changed)
}
}
}
// extreme case: i = j = k
if (i == j) {
cout << "no solution";
return 0;
}
// put i-th entry to temp, sort 0-th to j-th entries except i-th entry and put into i-th to (j-1)-th entry
// finally put temp to j-th entry
temp = num_array[i];
num_array[i] = INT_MIN;
vector myvector (num_array, num_array + size);
vector::iterator it;
sort(myvector.begin(), myvector.begin() + j + 1, myfunction);
myvector[j] = temp;
num = 0;
temp = 1;
for (i = 0; i < size; i++) {
num += temp*myvector[i];
temp *= 10;
}
cout << num << endl;
}
return 0;
}

within integer range the code should be ok

17. yy said

FWIW, your algorithm is exactly the same as Algorithm L in Knuth’s The Art of Computer Programming, vol 4, section 7.2.1.2. Your explanation of the basic algorithm is much more intuitive and more clear than Knuth’s, though. :-)

If the digits in the number appear in the reverse sorted arrangement (654321), it is the highest number possible with a permutation of those digits. In this case we cannot do anything for the given problem.
If not, we analyze the given number from the last digit onwards, and identify the 2 successive digits which decrease. (34 in 653421)

At this point we splice the digits in two parts and sort the second half (653421 becomes 653 and 124).

We then pick the offending digit which is the point of splice (3 in this case) and swap it with the next highest digit in the second half (654 and 123). Concatenate the digits and you have the number.

Welcome any suggestions. Python implementation below.

```def get_next_digit(num):
if(num == "".join(sorted(str(num), reverse=True))):
return None

digits = list(num)
for x in xrange(len(digits) - 1, 0, -1):
if digits[x] > digits[x - 1]:
break;
else:
assert(False)
sub_digits = sorted(digits[x:])

for y in xrange(0, len(sub_digits)):
if sub_digits[y] > digits[x - 1]:
sub_digits[y], digits[x - 1] = digits[x - 1], sub_digits[y]
break
else:
assert(False)
return "".join((digits[:x] + sub_digits))

```
19. Jussi Piitulainen said

adeepak, sorting is overkill. If the first loop hits the break, it found the right digits[x – 1], else the digits were in decreasing order, so return None at that point. The second loop should find the rightmost digits[y] that satisfies the condition; one is guaranteed to exist to the right of digits[x – 1] because digits[x] is one.

Swap digits[x – 1] with digits[y] and the tail after[x – 1] will be in decreasing order, so all the sort does is reverse it. It does reverse it, of course, but it is heavier machinery than is needed.

Jussi,

Thanks for your comment and pointing the overkill. I agree sorting will not be needed as the digit order is implied for the second half. Incorporating your suggestion, the solution becomes more optimal.

21. Brikesh said

Here is a C# solution. Initially I though of the brute fore, generating all permutation, then sorting them to get the next number. That would be painfull. The way I implemented is
this: I liked other approach as suggested by some one, to simply use the digits in the original number and generate a another sequence till you get the next bigger one.
Algorithm
1. Input the n didgit number An
2. Flag = false
3. While Flag = false
An = An +1
Flag = Compare(An, An+1)
4. Return An

1. Compare( A, B)
2. Flag = true
3. for j <–0 to j <– B.Length – 1
If A contains B[j]
else
Flag = false
4. Return Flag

Code:

private static int _getNextNumber(int input)
{
bool found = false;
Stopwatch watch = new Stopwatch();
watch.Start();
char[] digits = input.ToString().ToArray();
while (!found)
{
++input;
found = _compare(input, digits);
}
watch.Stop();
Console.WriteLine("Execution time :- " + watch.Elapsed);
return input;
}

private static bool _compare(int input, char[] digits)
{
bool result = true;
char[] inputArray = input.ToString().ToArray();
if (inputArray.Length != digits.Length)
result = false;
if (result)
{
for (int count = 0; count c == inputArray[count]);
int outputDigitInput = inputArray.Count(c => c == inputArray[count]);
if (repitedDigitInput != outputDigitInput)
{
result = false;
break;
}
}
}
}
return result;
}

22. Vatsa said

Here’s a solution in php.
Logic is as follows:
– start with the rightmost digit (say, n) and see if there’s any digit to its left that is lesser (say, i)
– if there is then swap n and i
– after swapping, sort the digits to the right of n

eg. 123451
– Rightmost digit, 1, is the least – so the next rightmost digit is 5
– 5 is greater than 4, swap to get 123541
– next sort the numbers to the right of 5 (4,1) to get the final number – 123514

You can make this function recursive so that it prints all the permutations possible.

function fn(\$n)
{
static \$count=0;
\$len = strlen(\$n);
\$index = \$len-1;
\$found = false;
while (\$index > 0 && !\$found)
{
for(\$i=\$index-1;\$i>=0&&!\$found;\$i–)
{
if(\$n[\$index] > \$n[\$i])
{
\$temp = \$n[\$index]; \$n[\$index] = \$n[\$i]; \$n[\$i] = \$temp;
\$found = true;
}
if(\$found)
{
for(\$j=\$i+1;\$j<\$len-1;\$j++)
for(\$k=\$j+1;\$k\$n[\$k])
{
\$temp = \$n[\$j]; \$n[\$j] = \$n[\$k]; \$n[\$k] = \$temp;
}
}
}
}
\$index–;
}
if (\$found)
{
\$count++;
echo ” \$count: “.\$n;
fn(\$n);
}
}

23. Anand Vijapur said

An algorithm is here:

Loop digits i = (n-2) to 0
Find to the right of i, smallest digit greater than i
if found, 1) swap i with the digit found 2) sort digits after i 3) RETURN permutation formed
End loop
If no swap, greatest number is reached; there is no Next Greater Permutation Of Digits

A simple Java program:

public class NextGreaterPermutationOfDigits {

/**
* @param args
*/
public static void main(String[] args) {
// test nos
//String num = “38276”;
String num = “8756”;
//String num = “382765”;
//String num = “385765”;

// for larger numbers, sorting each time can be a performance hit
// create sequence for look up
char[] sequence = sort(num.toCharArray());

System.out.println(num);
String newNum;
for (int i = 0; i = 0; i–) {
leastGreaterDigitIdx = -1;
for (int j = i + 1; j chars[i] &&
(leastGreaterDigitIdx chars[j])) {
leastGreaterDigitIdx = j;
}
}
if (leastGreaterDigitIdx > i) {
// swap i with leastGreaterIdx
temp = chars[i];
chars[i] = chars[leastGreaterDigitIdx];
chars[leastGreaterDigitIdx] = temp;

// sort digits after i

// digits to be sorted
char[] toBeSorted = new char[chars.length – 1 – i];
int toBeSortedIdx = 0;
for (int k = i + 1; k < chars.length; k++) {
toBeSorted[toBeSortedIdx++] = chars[k];
}

// look up sequence for sorting
int idx = i + 1;
for (int x = 0; x < sequence.length; x++) {
for (int k = 0; k there is no Next Greater Permutation Of Digits
return num;
}

private static char[] sort(char[] chars) {
char[] result = chars.clone();
char temp;
for (int k = 0; k < result.length; k++) {
for (int j = 0; j result[j + 1]) {
temp = result[j];
result[j] = result[j + 1];
result[j + 1] = temp;
}
}
}
return result;
}

}

24. trilok sharma said

#include
#include
#include
#include
using namespace std;

int compare (const void * a, const void * b)
{
return ( *(const char *)a > *(const char *)b);
}

int myfunc(char *num)
{
int i,length;

for(i=0;num[i];i++);

length=i;

int prev=num[length-1];

for(i=length-2;i>=0;i–)
{ if(prev>num[i])
break;
prev=num[i];
}

if(i==-1)
return -1;

int pos=i;
int min_pos=length-1;

for(i=length-1;i>pos;i–)
{ if(num[i]>num;

if(myfunc(num)==0)
cout<<num;
else
cout<<"sorry";
}