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.

24 Responses to “Next Greater Permutation Of Digits”

Kwiatki said
February 28, 2012 at 3:49 PM
Please see my plain python solution at: http://codepad.org/cR4jr4Vp
Same algorithm as OP, obviously as it is correct.
DGel said
February 28, 2012 at 4:33 PM
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

DGel said

February 28, 2012 at 5:01 PM

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

programmingpraxis said
February 28, 2012 at 6:30 PM
Dammit, I don’t get the job.
Elvis Montero said
February 28, 2012 at 7:33 PM
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.
Mike said
February 28, 2012 at 8:45 PM
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]

nz said

February 28, 2012 at 9:43 PM

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]

Tomasz Kwiatkowski said

February 28, 2012 at 10:42 PM

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;
}

ardnew said
February 29, 2012 at 4:46 AM
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

nz said

February 29, 2012 at 5:51 AM

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';

}

Jussi Piitulainen said
February 29, 2012 at 7:26 AM
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.)

Graham said

February 29, 2012 at 4:50 PM

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.

sweetopiagirl said
March 1, 2012 at 4:13 AM
Reblogged this on Inspiredweightloss.

Axio said

March 1, 2012 at 8:07 AM

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))))))

Jussi Piitulainen said

March 1, 2012 at 9:22 AM

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)

Simon said
March 1, 2012 at 8:11 PM
#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
yy said
March 5, 2012 at 2:14 AM
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. :-)
adeepak said
March 11, 2012 at 1:38 AM
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))
```
Jussi Piitulainen said
March 11, 2012 at 5:02 PM
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.
adeepak said
March 12, 2012 at 1:35 AM
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.
Brikesh said
March 14, 2012 at 3:08 PM
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;
}
Vatsa said
March 22, 2012 at 6:37 AM
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);
}
}
Anand Vijapur said
May 18, 2012 at 11:48 AM
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;
}

}
trilok sharma said
March 17, 2013 at 3:28 PM
#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";
}

Programming Praxis