Javaでの順列(N!通り)、組み合わせ(N^m通り)の全探索を応用しやすくしてみた

JavaでのAtCorderやTOPSICで役立つ全探索について自分なりに使いやすくしてみました！

順列の全探索(N!通り)
-
順列の全探索のコードについては
https://maku77.github.io/java/numstr/permutation.html
を参考にしました。
1つ1つの並べ替えを```ArrayList<Integer>```型に格納してそれを```ArrayList<ArrayList<Integer>>```に格納します。
コードは次のものです。
```main.java
import java.util.ArrayList;
public class Chu8_1 {
    private static ArrayList<ArrayList<Integer>> permutation(int[] seed) {
        ArrayList<ArrayList<Integer>> array =new ArrayList<ArrayList<Integer>>();
        int[] perm = new int[seed.length];
        boolean[] used = new boolean[seed.length];
        buildPerm(seed, perm, used, 0,array);
        return array;
    }
    private static void buildPerm(int[] seed, int[] perm, boolean[] used, int index,ArrayList<ArrayList<Integer>> array) {
        if (index == seed.length) {
            procPerm(perm,array);
            return;
        }
        for (int i = 0; i < seed.length; i++) {
            if (used[i])
                continue;
            perm[index] = seed[i];
            used[i] = true;
            buildPerm(seed, perm, used, index + 1,array);
            used[i] = false;
        }
    }
    private static void procPerm(int[] perm,ArrayList<ArrayList<Integer>> array) {
        ArrayList<Integer> k=new ArrayList<>(perm.length);
        for(int i=0;i<perm.length;i++) {
            k.add(perm[i]);
        }
        array.add(k);
    }
    public static void main(String[] args) throws Exception {
        //今回は[1,2,3]の並べ替えで試します。
        ArrayList<ArrayList<Integer>> array2 = permutation(new int[] {1,2,3});
        for(int i=0;i<array2.size();i++) {
            for(int k=0;k<array2.get(i).size();k++) {
                System.out.print(array2.get(i).get(k)+" ");
            }
            System.out.println("");
        }
    }
}
```
```ArrayList<ArrayList<Integer>>```型の変数```array2```には<font color="Red">[0,1,2,3,…,N-1]のN!通りの並べ替え</font>が格納されます。
(なので、```array.size()```は$N!$と同じ値になり、```array2.get(i).size()```は$N$と同じ値になります。）

今回の[1,2,3]のときでいうと、
```array2.get(0)```は[1,2,3]を```ArrayList<Integer>```型に変換したもの
```array2.get(1)```は[1,3,2]を```ArrayList<Integer>```型に変換したもの
```array2.get(2)```は[2,1,3]を```ArrayList<Integer>```型に変換したもの
```array2.get(3)```は[2,3,1]を```ArrayList<Integer>```型に変換したもの
```array2.get(4)```は[3,1,2]を```ArrayList<Integer>```型に変換したもの
```array2.get(5)```は[3,2,1]を```ArrayList<Integer>```型に変換したもの
となっています。
(```ArrayList```に```ArrayList```が入っていてややこしいですが、例えば```array.get(3)```について考えると
```array.get(3).get(0)=2, array.get(0).get(1)=3, array.get(0).get(2)=1```となっています。)

このように```ArrayList<ArrayList<Integer>>```に格納していくことで<font color="Red">$(N!)^m$</font>通りの全探索に役立てられるなど応用が効きやすくなります。

組み合わせの全探索(N^m通り)
-
例えば、サイコロを4個転がすときの全パターンが知りたいとき、どのような考え方をするでしょうか?
$$[1,1,1,1],[1,1,1,2],...,[3,2,6,6],[3,3,1,1],...,[6,6,6,5],[6,6,6,6]$$
という感じで全パターン列挙できると思います。これが<font color="Blue">4桁の6進数に似ていると感じる人もいるのではないでしょうか。</font>
実際に各桁から1引いて[,]で区切るのを止めてみると、
$$0000,0001,...,2155,2200,5554,5555$$
となります。
よって4桁の6進数を考えれば、全通り列挙できるのがお分かりいただけると思います。

これをコーディングで表すと次のようになります。
<font color="LightSlateGray">実行してみると分かりやすいと思います。</font>
```Main.java
import java.util.ArrayList;

public class Main {
	
	private  static ArrayList<ArrayList<Integer>> combination(int N ,int m){
		ArrayList<ArrayList<Integer>> array =new ArrayList<ArrayList<Integer>>();
		//N^mまでの10進数をm進数に変換したい
		int n =(int) Math.pow(m, N);
		for(int i=0;i<n;i++) {
			ArrayList<Integer> k =new ArrayList<Integer>();
			//N-1桁までのm進数を0を上の桁に入れることでN桁にそろえる
			String c = String.format("%0"+Integer.toString(N,10)+"d", Long.parseLong(Integer.toString(i,m)));
			//char[]型に変換する
			char[] d =c.toCharArray();
			for(int l=0;l<d.length;l++) {
				//1桁ずつArrayList<Integer>型の変数kに格納
				int u =Character.getNumericValue(d[l]);
				k.add(u);
			}
			//ArrayList<ArrayList<Integer>>型のarrayにN桁のm進数を1桁ずつ格納した変数kを格納
			array.add(k);
		}
		return array;
	}

	public static void main(String[] args) {
        //サイコロの目の数が6だから6進法を考える(m=6)
		int m=6;
        //今回はサイコロ4個だからN=4
		int N=4;
		ArrayList<ArrayList<Integer>> array2 = combination(N,m);

		for(int i=0;i<array2.size();i++) {
            for(int k=0;k<array2.get(i).size();k++) {
                 //サイコロなので1から目が出ることに注意して1を足す。
                 System.out.print(array2.get(i).get(k)+1+" ");
            }
             //kのときが回し終われば改行
            System.out.println("");
        }
	}

}
```
実際に実行してみると次のようになります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2725869/a92b93da-aadd-2887-549a-b38bde1889d8.png)
　　　　　　⁝
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2725869/a43a458b-0856-d443-b190-0a00b84989f6.png)
このように全列挙できます。
(ただし、出力の際には1～6で表したいため、出力の際各桁1を足してます。)

今回使ったcombinationメソッドについても、
```ArrayList<ArrayList<Integer>> array2 = combination(6,4)```として、
```array2.get(0)```は[0,0,0,0]を```ArrayList<Integer>```型に変換したもの
```array2.get(1)```は[0,0,0,1]を```ArrayList<Integer>```型に変換したもの
```array2.get(2)```は[0,0,0,2]を```ArrayList<Integer>```型に変換したもの
 　　　　　　　　　　　　　&nbsp;&nbsp;&nbsp;⁝
```array2.get(6^4-3)```は[5,5,5,3]を```ArrayList<Integer>```型に変換したもの
```array2.get(6^4-2)```は[5,5,5,4]を```ArrayList<Integer>```型に変換したもの
```array2.get(6^4-1)```は[5,5,5,5]を```ArrayList<Integer>```型に変換したもの
という風に格納されています。

よって、例えば```array2.get(6^4-3)```すなわち、```array2.get(1293)```については、
```array2.get(1293).get(0)=5,array2.get(1293).get(1)=5,array2.get(1293).get(2)=5,array2.get(1293).get(3)=3```という感じです。

これについても、```ArrayList<ArrayList<Integer>>```に格納していくことで<font color="Red">$N^mZ^y$</font>通りの全探索に役立てられるなど応用が効きやすくなります。


以上です。

参考文献
-
https://maku77.github.io/java/numstr/permutation.html