用于排列数字列表的 Java 代码

Question

我编写了一个程序来查找给定项目列表的所有可能排列。这恰恰意味着我的程序打印了 r=0 到 n 的所有可能的 P(n,r) 值

代码如下:

包 com.algorithm;

导入 java.util.ArrayList；
导入 java.util.Calendar；
导入 java.util.Collection；
导入 java.util.HashSet；
导入java.util.List；
导入java.util.Set；

公共(public)类排列
    
      {
     
 public static void main(String args[]) {
     
 Permutations
     
       obj = new Permutations
      
       ();
       
 集合<整数> input = new ArrayList<整数>();
       
 输入.add(1);
       
 输入.add(2);
       
 输入.add(3);
       

       
 集合
       
        > output = obj.permute(input);
        
 诠释 k = 0;
        
 设置<列表<整数>> pnr = null;
        
 对于 (int i = 0; i <= input.size(); i++) {
        
 pnr = new HashSet
        
         >();
         
 for(List
         
           整数:输出){
          
 pnr.add(integers.subList(i, integers.size()));
          
 }
          
 k = input.size()- i;
          
 System.out.println("P("+input.size()+","+k+") :"+
          
 "计数 ("+pnr.size()+") :- "+pnr);
          
 }
          
 }
          
 public Collection
          
           > permute(Collection
           
             输入) {
            
 集合
            
             > output = new ArrayList
             
              >();
              
 如果(输入。isEmpty()){
              
 output.add(new ArrayList
              
               ());
               
 返回输出；
               
 }
               
 List
               
                 list = new ArrayList
                
                 (输入);
                 
 T head = list.get(0);
                 
 List
                 
                   rest = list.subList(1, list.size());
                  
 for (List
                  
                    permutations : permute(rest)) {
                   
 List
                   
                    > subLists = new ArrayList
                    
                     >();
                     
 对于 (int i = 0; i <= permutations.size(); i++) {
                     
 List
                     
                       subList = new ArrayList
                      
                       ();
                       
 subList.addAll(排列)；
                       
 subList.add(i, head);
                       
 subLists.add(subList);
                       
 }
                       
 output.addAll(subLists);
                       
 }
                       
 返回输出；
                       
 }
                       
}
                       

                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    

输出

P(3,3) : Count (6) :- [[1, 2, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2], [2, 1, 3], [1, 3, 2]]
P(3,2) : Count (6) :- [[3, 1], [2, 1], [3, 2], [1, 3], [2, 3], [1, 2]]
P(3,1) : Count (3) :- [[3], [1], [2]]
P(3,0) : Count (1) :- [[]]

我的问题是，当我增加输入列表中的数字时。运行时间增加，在输入列表中的 11 个数字之后，程序几乎停止运行。需要大约 2 GB 内存才能运行。

我在一台有 8GB RAM 和 i5 处理器的机器上运行它，所以速度和空间不是问题。

如果有人能帮助我编写更高效的代码，我将不胜感激。

Answer 1

如果你不存储它——如果你只是迭代它——然后考虑使用 Heap 的算法(http://www.cut-the-knot.org/do_you_know/AllPerm.shtml 上的#3)——或者，为了让你的生活更轻松，使用 Guava 的 Collections2.permutations，它不会'实际上构建了整个排列列表——它动态地遍历它们。 (披露:我为 Guava 做出了贡献。)