字典序排列（借助于TreeSet实现）

ゝ一世哀愁。 2022-07-25 21:26 171阅读 0赞

> 给出一个字符串S（可能又重复的字符），按照字典序从小到大，输出S包括的字符组成的所有排列。例如：S = “1312”，  
> 输出为：  
> 1123  
> 1132  
> 1213  
> 1231  
> 1312  
> 1321  
> 2113  
> 2131  
> 2311  
> 3112  
> 3121  
> 3211  
> Input  
> 输入一个字符串S（S的长度 <= 9，且只包括0 - 9的阿拉伯数字）  
> Output  
> 输出S所包含的字符组成的所有排列  
> Input示例  
> 1312  
> Output示例  
> 1123  
> 1132  
> 1213  
> 1231  
> 1312  
> 1321  
> 2113  
> 2131  
> 2311  
> 3112  
> 3121  
> 3211

note：这道题java语言实现要求3000ms。常用的求全排列的方法有两种，一种是基于递归的Permutation，另外一种则是使用搜索进行枚举。这道题使用搜索亲测超时，可是递归的进行排列得到的又无法保证是字典序。这种情况下，在第一种方法的基础上又引入了一个TreeSet（我之前因为没有用过，所以觉得很amazed！）  
因为题目要求输出的全排列是没有重复元素的，而这刚好符合了Set的集合要求，另外TreeSet内部会自动进行排序，所以最终一个foreach输出就行了。

import java.util.Arrays;
    import java.util.Scanner;
    import java.util.Set;
    import java.util.TreeSet;
    
    
    public class Main {
    
        public static Set<String> res = new TreeSet<String>();
        public static char[] digits;
    
        public static void swap(int x,int y){
            char t = digits[x];
            digits[x] = digits[y];
            digits[y] = t;
        }
    
        public static void perm(int s,int e){
            if(s==e-1){
                res.add(new String(digits));
            }
            for(int i=s;i<e;i++){
                swap(s,i);
                perm(s+1, e);
                swap(s,i);
            }
        }
        public static void main(String[] args){
            // TODO Auto-generated method stub
            Scanner in = new Scanner(System.in);
            while(in.hasNext()){
                String S = in.next();
                res.clear();
                long t1 = System.currentTimeMillis();
                digits = S.toCharArray();
                Arrays.sort(digits);
                perm(0,S.length());
                for(String x:res) System.out.println(x);
                long t2 = System.currentTimeMillis();
                //System.out.println("Time cost:"+(t2-t1));
            }
            //in.close();
        }
    
    }

ps:以前遇到这样的求“按字典序求全排列的“都是用搜索做的，而这道题通过TreeSet的辅助，可以更加高效的实现。