java - 如何在java中构建组合功能？

Question

我正在研究面试问题。

而且，我很难理解组合功能。

我想构建组合功能。

例如，如果输入是[1,2,3] 那么我必须生成[1,2,3] , [1, 3, 2 ] , [2, 1 ,3 ] , [ 2, 3, 1] , [ 3, 1, 2 ] , [ 3, 2 ,1]

但是，它不应该接受长度小于输入值的情况。（例如，[1]，[3,2]）

并且，输入中的元素数量是可变的 ( [1,2,3,4], [1,2,3,4,5 ,6])

但是，我不确定如何开始构建此功能。

有人可以给出一些想法或例子吗？

谢谢

Answer 1

正如已经指出的那样，您似乎是指permutation而不是combination。

进入我脑海的第一种方法是递归方法——但我不确定它的效率如何——这可能是一个有趣的问题，可以为你的面试问题考虑！

public class Permutations {

   // testing
   public static void main(String[] args){        
    permutations(new int[]{1,2,3});    
   }

   public static void permutations(int[] array){
     boolean[] chosen = new boolean[array.length];
     int[] output = new int[array.length];
     permutation_inner(array,chosen,output,0);
   }
   public static void permutation_inner(int[] array, boolean[] chosen, 
                                        int[] output, int depth){
     if(depth==array.length){
       System.out.println(java.util.Arrays.toString(output));
       return;
     }
     for(int i=0;i<array.length;i++){
        if(!chosen[i]){
           chosen[i]=true;
           output[depth]=array[i];
           permutation_inner(array,chosen,output,depth+1);
           chosen[i]=false;
        }
     }
   }

}