I didn't know anything about the brute force algorithm when answering this question, so I approached it from another angle. I decided to search the entire range of possible solutions that this number could possibly be rearranged into, starting from the number_given+1 up to the max number available (999 for a 3 digit number, 9999 for 4 digits, etc.). I did this kind of like finding a palindrome with words, by sorting the numbers of each solution and comparing it to the sorted number given as the parameter. I then simply returned the first solution in the array of solutions, as this would be the next possible value.

下面是我的Ruby代码:

def PermutationStep(num)

    a = []
    (num.to_s.length).times { a.push("9") }
    max_num = a.join('').to_i
    verify = num.to_s.split('').sort
    matches = ((num+1)..max_num).select {|n| n.to_s.split('').sort == verify }

    if matches.length < 1
      return -1
    else
      matches[0]
    end
end

只是使用python的另一个解决方案:

def PermutationStep(num):
    if sorted(list(str(num)), reverse=True) == list(str(num)):
        return -1
    ls = list(str(num))
    n = 0
    inx = 0
    for ind, i in enumerate(ls[::-1]):
        if i < n:
            n = i
            inx = -(ind + 1)
            break
        n = i
    ls[inx], ls[inx + 1] = ls[inx + 1], ls[inx]

    nl = ls[inx::-1][::-1]
    ln = sorted(ls[inx+1:])
    return ''.join(nl) + ''.join(ln)

print PermutationStep(23514)

输出:

23541

#include<bits/stdc++.h>
using namespace std;
int main() 
{
    int i,j,k,min,len,diff,z,u=0,f=0,flag=0;
    char temp[100],a[100]`enter code here`,n;
    min=9999;
    //cout<<"Enter the number\n";
    cin>>a;
    len=strlen(a);
    for(i=0;i<len;i++)
    {
        if(a[i]<a[i+1]){flag=1;break;}
    }
    if(flag==0){cout<<a<<endl;}
    else
    {
        for(i=len-1;i>=0;i--)if(((int)a[i-1])<((int)a[i]))break;
        for(k=0;k<i-1;k++)cout<<a[k];
        for(j=i;j<len;j++)
        {
            if(((int)a[j]-48)-((int)a[i-1]-48)>0)
            {
                diff=((int)a[j]-48)-((int)a[i-1]-48);
                if(diff<min){n=a[j];min=diff;}
            }
        }
        cout<<n;
        for(z=i-1;z<len;z++)
        {
            temp[u]=a[z];
            u++;
        }
        temp[u]='\0';
        sort(temp,temp+strlen(temp));
        for(z=0;z<strlen(temp);z++){if(temp[z]==n&&f==0){f=1;continue;}cout<<temp[z];}
    }
    return 0;
}

在Java中，这个算法比这个算法更简洁

   public static int permutate2(int number){
        String[] numArray = String.valueOf(number).split("");

        for(int i = numArray.length - 1; i > 0; i--){
            int current = Integer.valueOf(numArray[i]);
            int previous = Integer.valueOf(numArray[i - 1]);

            if(previous < current){
                String[] rest = String.valueOf(number).substring(i, numArray.length).split("");
                Arrays.sort(rest);

                String picker = rest[0];
                int pickerIndex = 0;
                for(int n = 0; n < rest.length ; n++){
                    if(Integer.valueOf(rest[n]) > previous){
                        picker = rest[n];
                        pickerIndex = n;
                        break;
                    }
                }
                numArray[i - 1] = picker;
                rest[pickerIndex] = String.valueOf(previous);
                Arrays.sort(rest);

                String newNumber = "";
                for(int z = 0; z <= i - 1; z++){
                    newNumber += numArray[z];
                }
                for(String z : rest){
                    newNumber += z;
                }

                return Integer.valueOf(newNumber);
            }
        }

        return number;
   }

PHP实现

时间复杂度O(n)

$n = "9875";
$n_size = strlen($n);
for($i = $n_size-1; $i > 0; $i-- ) {
     if($n[$i] > $n[$i-1]){
     $temp = $n[$i];
     $n[$i] = $n[$i-1];
     $n[$i-1] = $temp;
     break;
     }
    
}

if($i == 0){
    echo "Next Greater value no possible";
}else{
    echo $n;
}

public static void findNext(long number){

        /* convert long to string builder */    

        StringBuilder s = new StringBuilder();
        s.append(number);
        int N = s.length();
        int index=-1,pivot=-1;

/* from tens position find the number (called pivot) less than the number in right */ 

        for(int i=N-2;i>=0;i--){

             int a = s.charAt(i)-'0';
             int b = s.charAt(i+1)-'0';

             if(a<b){
                pivot = a;
                index =i;
                break;
            }
        }

      /* if no such pivot then no solution */   

        if(pivot==-1) System.out.println(" No such number ")

        else{   

     /* find the minimum highest number to the right higher than the pivot */

            int nextHighest=Integer.MAX_VALUE, swapIndex=-1;

            for(int i=index+1;i<N;i++){

            int a = s.charAt(i)-'0';

            if(a>pivot && a<nextHighest){
                    nextHighest = a;
                    swapIndex=i;
                }
            }


     /* swap the pivot and next highest number */

            s.replace(index,index+1,""+nextHighest);
            s.replace(swapIndex,swapIndex+1,""+pivot);

/* sort everything to right of pivot and replace the sorted answer to right of pivot */

            char [] sort = s.substring(index+1).toCharArray();
            Arrays.sort(sort);

            s.replace(index+1,N,String.copyValueOf(sort));

            System.out.println("next highest number is "+s);
        }

    }