0

面接の質問を勉強しています。

あと、組み合わせ機能が分からなくて困っています。

組み合わせ機能を構築したいと思います。

たとえば、入力が次の場合、[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])

ただし、この関数の作成を開始する方法がよくわかりません。

誰かアイデアや例を教えてください。

ありがとう

4

1 に答える 1

1

指摘されているように、組み合わせではなく順列を意味しているようです。

私の頭に浮かぶ最初のアプローチは再帰的なものです - しかし、それがどれほど効率的かはわかりません - おそらくあなたの面接の質問のために考慮する興味深い質問です!

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;
        }
     }
   }

}
于 2013-06-06T22:18:44.653 に答える