多重ループによる場合の数

ここで、講義例を披露しよう。

ここでは、一般的な問題を考える。あらゆる問題は、すべての場合から条件を満たす場合（すなわち解）を探索することによって解くことができる。場合の数には、重複順列、順列、重複組合せ、組合せなどの種類がある。これらをプログラムで表現することができれば、すべての場合を列挙することができるようになる。
例えば、4から3とる重複順列は以下のように表すことができる。

void main() {
    int a, b, c;

    for(a=1; a<=4; a=a+1) {
        for(b=1; b<=4; b=b+1) {
            for(c=1; c<=4; c=c+1) {
                printf("%d %d %d\n", a, b, c);
            }
        }
    }
}

実行結果は以下のようになる。

1 1 1
1 1 2
…
4 4 3
4 4 4

行数にして4^3=64通りである。
一般にnからrとる重複順列 は1からnまでのループのr重ループとなる。場合の数はn^rである。
順列とは、重複順列から重複を省いたものである。例えば、4から3とる順列は以下のように表すことができる。

void main() {
    int a, b, c;

    for(a=1; a<=4; a=a+1) {
        for(b=1; b<=4; b=b+1) {
            if (a == b) continue;
            for(c=1; c<=4; c=c+1) {
                if (a == c || b == c) continue;
                printf("%d %d %d\n", a, b, c);
            }
        }
    }
}

ここで、8行目はaと重複するbを省いている。10行目はa、bと重複するcを省いている。内側のループほど省くためのチェックが多くなる。チェックする項目が多くなると||演算子を使うよりif文を並べたほうがわかりやすい。
実行結果は以下のようになる。

1 2 3
1 2 4
…
4 3 1
4 3 2

行数にして4!/(4-3)!=24通りである。
順列では、1 2 3と3 2 1を区別するが、組合せでは区別しない。同じ要素に対して並びを区別しない数え方が組合せである。区別しないということは一つに決まっていると考えても良い。そこで、昇順の並び順を選ぶ。昇順とは、小さいほうから大きいほうへ並べることである。つまり、a≦b≦cが成り立つ。これはb(c)のループがa(b)から始まると考えても良い。
組合せにも要素の重複を許す重複組合せと重複を許さない組合せがある。最初にプログラムが簡単な重複組合せの例を示す。
例えば、4から3とる重複組合せは以下のように表すことができる。

void main() {
    int a, b, c;

    for(a=1; a<=4; a=a+1) {
        for(b=a; b<=4; b=b+1) {
            for(c=b; c<=4; c=c+1) {
                printf("%d %d %d\n", a, b, c);
            }
        }
    }
}

重複順列のプログラムと比べて7行目と8行目のfor文の初期値が異なる。
実行結果は以下の通りである。

1 1 1
1 1 2
1 1 3
…
4 4 4

組合せは順列と同様に重複を排除すればよい。例えば、4から3とる組合せ は以下のように表すことができる。

void main() {
    int a, b, c;

    for(a=1; a<=4; a=a+1) {
        for(b=a+1; b<=4; b=b+1) {
            for(c=b+1; c<=4; c=c+1) {
                printf("%d %d %d\n", a, b, c);
            }
        }
    }
}

bとaは等しくならないので、bはa+1から始めればよい。cとbも同様である。
実行結果は以下の通りである。

1 2 3
1 2 4
1 3 4
2 3 4