順列取得 next_permutation java
javaにはnext_permutationが実装されていないので自前で実装する.
目的
今回やりたいことはの集合が与えられた時に順列を全列挙する
{ 1 , 2 , 3 , 4 }
上の集合に対して以下を出力する
( 1 , 2 , 3 , 4 ) ( 1 , 2 , 4 , 3 ) ( 1 , 3 , 2 , 4 ) ( 1 , 3 , 4 , 2 ) ( 1 , 4 , 2 , 3 ) ( 1 , 4 , 3 , 2 ) ( 2 , 1 , 3 , 4 ) ( 2 , 1 , 4 , 3 ) ( 2 , 3 , 1 , 4 ) ( 2 , 3 , 4 , 1 ) ( 2 , 4 , 1 , 3 ) ( 2 , 4 , 3 , 1 ) ( 3 , 1 , 2 , 4 ) ( 3 , 1 , 4 , 2 ) ( 3 , 2 , 1 , 4 ) ( 3 , 2 , 4 , 1 ) ( 3 , 4 , 1 , 2 ) ( 3 , 4 , 2 , 1 ) ( 4 , 1 , 2 , 3 ) ( 4 , 1 , 3 , 2 ) ( 4 , 2 , 1 , 3 ) ( 4 , 2 , 3 , 1 ) ( 4 , 3 , 1 , 2 ) ( 4 , 3 , 2 , 1 )
条件
- 全て列挙する
- 被ってはいけない
- 順番はよしなに(考えなくて良い)
実装方針
順列の並びを考えるときにはじめの文字から決定していき使ってない文字を後に追加していきます.
今までで使用した文字を記録しておくことと元の集合配列{ 1 , 2 , 3 , 4 }
は崩さないようにしなければならないことが重要になってきます.
具体的には新しく構成する配列を別に持っておきこの配列に追加していく操作をします.
class MainA { public final static int[] elements = { 1, 2, 3, 4 }; public static void main(String[] args) { int[] tmp = new int[4]; // 最終的に出力される配列 boolean[] used = new boolean[4]; // 使用したか判定用に使う permutation(elements, tmp, used, 0); } static void permutation(int[] elements, int[] tmp, boolean[] used, int index) { if (index == 4) { // 出力処理を行う ShowArray(tmp); return; } ///////////////////////// main部分//////////////////////////// for (int i = 0; i < 4; i++) { if (used[i]) continue; used[i] = true; tmp[index] = elements[i]; permutation(elements, tmp, used, index + 1); used[i] = false; } } // 出力関数 static void ShowArray(int[] array) { System.out.print("("); for (int i = 0; i < 4; i++) { System.out.print(" " + array[i] + " "); if (i != 3) { System.out.print(","); } } System.out.println(")"); } }