[java]再帰による多重ループ

javaで多重ループ処理を再帰によって実装する。
先日、ABC165C Many Requirementsを解いた際に多重ループ処理が必要になり、実装するのに苦労したため、まとめることにした。

多重ループ処理

組み合わせの全列挙を行う際、多重ループが必要となる。
具体的に言うと、M個のモノからN個のモノを取り出す場合の全列挙の方法は、N重for文によって表せる。
以下は重複を許してM個のモノから3個のモノを取り出す場合の組み合わせの全列挙である。

for(int i = 1; i <= M; i++){
  for(int j = i; j <= M; j++){
    for(int k = j; k <= M; k++){
      System.out.println(i + " " + j + " " + k);
      //[1 1 1]から[M M M]までが出力される
    }
  }  
}

重複を許さない場合は、j=i+1とすればよい。
このように、Nがわかっている場合はN個のfor文を書くことによって実装が可能である。
一方、Nがわかっていない場合はこのような書き方はできない。
そこで、再起処理を行う。

再帰による処理

先にコードを記し、後から解説する。
重複を許す場合を想定している。

static int N, M;
static List<Integer> A = new ArrayList<>();	
static void dfs(List<Integer> A) {
  if(A.size() == N+1) {
    //Aは先頭要素が1、2つ目以降が求めたいi,j,k...となっている
    System.out.println(A.toString());
    //N=3のとき、[1 1 1 1]から[1 M M M]までが出力される
    return;
  }
  int x = A.get(A.size()-1);
  //重複を許さない場合はint x = A.get(A.size()-1)+1
  for(int i = x; i <= M; i++){
    A.add(i);
    dfs(A);
    A.remove(A.size()-1);
  }
}
	
public static void main(String[] args) {
  A.add(1);
  dfs(A);
}

前述のi,j,k...がリストAに格納されるようになっている。
ただし、末尾の要素を取得する際にA.size()-1を参照しているため、Null Pointer Exceptionを回避するためにリストAの最初に1を入力し、大きさN+1のリストとしている。
再帰の流れは以下のようになる。

1. Aの大きさがN+1なら、Aは求めたいリストになっているため、それを用いて諸々の処理を行う
    それ以外の場合は以下の処理を行う
2. 末尾の要素を取得し、xとする
3. xがMになるまで以下のループを繰り返す
    3.1 末尾にxを加え、1に戻る(再帰処理を行う)
    3.2 末尾を消去し、xに1を加える

N=3・M=3のときの具体的な手順を説明する。

1. A = [1]
2. x = 1、A = [1, 1] 手順1に戻る(dfs(A))
3. x = 1、A ＝ [1, 1, 1]　手順1に戻る(dfs(A))
4. x = 1、A = [1, 1, 1, 1]　手順1に戻る(dfs(A))
5. サイズがN+1になったので、A = [1, 1, 1, 1]を用いて処理を行う　3.のdfs終了後の状態に戻る
6. 末尾を消去し、A = [1, 1, 1]となる。　x = 2となる
7. x = 2、A = [1, 1, 1, 2]　手順1に戻る(dfs(A))
8. サイズがN+1になったので、A = [1, 1, 1, 2]を用いて処理を行う　6.のdfs終了後の状態に戻る
   というように、再起的な処理で順番にAに格納されていく。

計算量

重複を許さない場合は、当然のことながらmCn通りである。
重複を許す場合は、M-1個のボールとN個の仕切りを並び替える場合の数に等しく、m+n-1Cn通りある。
後者の計算量は、N=10・M=10のとき、92738通りである。
組み合わせの計算は「N choose M」でgoogle検索をすると求められる。

参考

ABC165 解説放送