全排列-字典序法求递增的下一个排列

问题

描述

求指定字符串下一个字典序（值）递增的排列

思路

1. 从后往前找第一对递增的相邻的递增字符，前一个称为“替换字符”，其下标称做“替换点”；
2. 在替换字符后面的字符串中找一个字典序比替换字符大的最小字符，将其称为“被替换字符”；
3. 将字符串中的“替换字符”与“被替换字符”调换位置；
4. 将替换点后的字符串顺序逆序；
5. 得下一个（字典序递增）的字符串排列；

Code

public class arrange_diction {
    static String fun(String s) {
        int i,t = 0,k;
        char x,y,z;
        String w="";
        for(i=s.length()-1;i>0;i--) {
            if(s.charAt(i)>s.charAt(i-1)) {
                t=i-1;
                break;
            }
        }
       
        z=s.charAt(i);
        k=i;
        for(i++;i<s.length();i++) { 
            if(s.charAt(i)>s.charAt(t)&&s.charAt(i)<z) { 
                k=i; 
            } 
        } 
        x=s.charAt(t);
        y=s.charAt(k); 
        for(i=s.length()-1;i>t;i--) {
            if(i==k) {
                w=w+x;
            }else {
               w=w+s.charAt(i); 
            }
        }
        s=s.substring(0,i)+y+w;
        return s;
    }
    public static void main(String[] args) {
        Scanner as=new Scanner(System.in);
        String s;
        int x,y,i,j,n;
        while(as.hasNext()) {
            s=as.nextLine();
            n=as.nextInt();
            String t=as.nextLine();
            for(i=0;i<n;i++) {
                s=fun(s);
            }
            System.out.println(s);
        }
    }
}

解析

• String fun(String s)函数是返回字典序递增的字符串s的下一个字符串的排列；