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.

About these ads

Pages: 1 2

24 Responses to “Next Greater Permutation Of Digits”

  1. Kwiatki said

    Please see my plain python solution at: http://codepad.org/cR4jr4Vp
    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. :-)

  18. adeepak said

    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.

  20. adeepak said

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 615 other followers

%d bloggers like this: