配列の配列からすべての順列を生成する方法。

11/07/2018

この例では、数値の配列のすべての順列を生成します。 処理は、最初の数のすべての順列を生成し、それを配列の残りの数の処理と組み合わせることによって、再帰的に実行されます。 リストに1つの要素だけが含まれている場合は、何もしません。

次のJavaファイルを作成します。

import java.util.ArrayList;

public class InterviewPermutations {

    public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> a) {
	// 入力検証
	if( a == null )
	    throw new IllegalArgumentException( "入力はnullにできません" );
	        
	ArrayList<ArrayList<Integer>> toReturn = new ArrayList<ArrayList<Integer>>();

	if( a.size() == 1 ){
	    toReturn.add( new ArrayList<Integer>(a) );
	    return toReturn;
	}
	
	// すべての要素をループします。 
	for( int i = 0 ; i < a.size(); i++ ){
	    int current = a.get( i );
	    ArrayList<Integer> tmp = new ArrayList<Integer>(a);
	    tmp.remove( i );

	   // サブセットを使用して再帰的に呼び出します 
	   ArrayList<ArrayList<Integer>> res = permute(tmp);
	       
	   // 返されたサブリストから結果を作成する
	   for( int j = 0 ; j < res.size() ; j++ ){
	       ArrayList<Integer> toAdd = new ArrayList<Integer>();
	       toAdd.add( current );
	       toAdd.addAll( res.get( j ) );
	       
	       toReturn.add( toAdd );
	   }
	}
	   
	// 結果を返す
	return toReturn;
    }
    
    public static void main(String[] argv) throws Exception {
	InterviewPermutations t = new InterviewPermutations();

	ArrayList<Integer> a = new ArrayList<Integer>();
	a.add( 1 );
	a.add( 2 );
	a.add( 3 );
	
	
	System.out.println( "開始配列：" );
	System.out.println( a );

	
	ArrayList<ArrayList<Integer>> res = t.permute(a);
	
	System.out.println( "結果：" );
	for(ArrayList<Integer> c : res ){
	    System.out.println( c );
	}

    }

}

出力は次のようになります。

開始配列：
[1, 2, 3]
結果：
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

この例は3つの要素を含んでおり、順列の数は3です！ または3 * 2 * 1または6。

参考文献：

java io

最近のコメント