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

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には[0,1,2,3,…,N-1]のN!通りの並べ替えが格納されます。
(なので、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>>に格納していくことで$(N!)^m$通りの全探索に役立てられるなど応用が効きやすくなります。

組み合わせの全探索(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]$$
という感じで全パターン列挙できると思います。これが4桁の6進数に似ていると感じる人もいるのではないでしょうか。
実際に各桁から1引いて[,]で区切るのを止めてみると、
$$0000,0001,...,2155,2200,5554,5555$$
となります。
よって4桁の6進数を考えれば、全通り列挙できるのがお分かりいただけると思います。

これをコーディングで表すと次のようになります。
実行してみると分かりやすいと思います。

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("");
        }
	}

}

実際に実行してみると次のようになります。

　　　　　　⁝

このように全列挙できます。
(ただし、出力の際には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>型に変換したもの
　　　　　　　　　　　　　 ⁝
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>>に格納していくことで$N^mZ^y$通りの全探索に役立てられるなど応用が効きやすくなります。

以上です。

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

順列の全探索(N!通り)

組み合わせの全探索(N^m通り)

参考文献