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.
Please see my plain python solution at: http://codepad.org/cR4jr4Vp
Same algorithm as OP, obviously as it is correct.
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
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 . numToListDammit, I don’t get the job.
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.
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]
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 . numToListexample:
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; }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
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'; }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.)
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)bruteis the obvious, slow, brute force option; hopefullyfasterlives up to its name.Reblogged this on Inspiredweightloss.
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))))))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 onI 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?
It steps the vector so:
#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
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))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.
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;
}
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);
}
}
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;
}
}
#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";
}