チェックボックスが20個あるアプリで、すべての組み合わせを試せるか #Java

アプリの設定の中などにチェックボックス、または、ON/OFFの値だけを持つトグルボタンが、
20個ある場合を想定します。

こんな感じです(例では、３つしかありませんが)。

チェックボックス

ON/OFFなどの2値のトグルボタン

組み合わせを考えてみる。

一般的なチェックボックスであれば、
各チェックボックスは、
「チェックされている」、「チェックされていない」の２つの状態しか持たないので、
n個のチェックボックスがあれば、その組み合わせの総数は、
2のn乗($2^n$)になります。

20個あるなら、2の20乗($2^{20}$)なので、
1,048,576通りになって、百万通り以上の組み合わせがあります。

相当に根性がないと、すべての組み合わせを、手動で試すのは無理そうです。
現在、Amazonには50万人以上の従業員がいるらしいので、
全員が協力してくれるならいけそうな気もしますが、
管理する手間考えると、ほぼ不可能でしょう。
(ソーシャルなテストですべてが網羅できるように、うまく誘導させる手法は、
相当数のユーザを確保できていれば不可能ではないかもしれません。)

別の視点で組み合わせを考えてみる。

単純に、『「チェックされている」、「チェックされていない」』がn個だから、
2のn乗とみることもできますが、
別の見方もできます。

n個のチェックボックスがあった場合は、

n個のうち0個がチェックされている
n個のうち1個がチェックされている
n個のうち2個がチェックされている
...
n個のうちn-1個がチェックされている
n個のうちn個がチェックされている

のような感じです。
これらを全部足し合わせても、同じ組み合わせの数が求まるはずです。

(n個のうち0個がチェックされている組み合わせの数) +
(n個のうち1個がチェックされている組み合わせの数) +
(n個のうち2個がチェックされている組み合わせの数) +
... +
(n個のうちn-1個がチェックされている組み合わせの数) +
(n個のうちn個がチェックされている組み合わせの数)

を計算してみます。

n個からk個選ぶ組み合わせは、以下のような記号で表す場合があります。

\dbinom{n}{k}

組み合わせという意味においては、
人によっては、以下の方が馴染みがあるかもしれません。

{}_n C_k

よって、n個から、0, 1, 2, 3, ..., n個選んだそれぞれの組み合わせの数を足し合わせればいいので、
こんな感じになります。

\dbinom{n}{0} + \dbinom{n}{1} + \dbinom{n}{2} + \cdots + \dbinom{n}{n - 1} + \dbinom{n}{n} = \sum_{k=0}^{n}\dbinom{n}{k}

見る人によっては、すぐに見覚えがある形に見えるかもしれません。
2項定理に含まれるパターンに見えます。

(x + y)^{n} = \sum_{k=0}^{n}\dbinom{n}{k}x^{k}y^{n-k}

$x = 1, y = 1$を代入すると、まさに欲しかったものになります。

(1 + 1)^{n} = \sum_{k=0}^{n}\dbinom{n}{k}1^{k}1^{n-k}\\
2^{n} = \sum_{k=0}^{n}\dbinom{n}{k}

これで、結局は、2のn乗($2^n$)と同じであることがわかりました。

すべての組み合わせを書き出してみる。

『「チェックされている」、「チェックされていない」』の2つの状態なのであれば、
2進数の各ビットをフラグと見立てて、0か1かを、チェックしてない、してるなどに対応させれば、
簡単に書き出せそうです。

非常に大きな組み合わせを手動で試すのは現実的ではありませんが、
自動化した単体テストなどに組み込んで、組み合わせを網羅させることは可能かもしれません。
(意味のある組み合わせであることが前提です。
互いに何も影響しあわない、チェックボックスであれば、テストが必要かは検討が必要。)

A, B, C, ..., R, S, Tまでの20個のチェックボックスがあって、
チェック状態の組み合わせをすべて列挙すると、例えば、以下のようになると思います。
かなりハードコードしているのでカッコ悪いですが、
記事にする場合は、分かりやすさ重視で、
あえて、ハードコードかつ、アホな実装をするようにしています。

C#で書くとこんな感じです。

var buttons = "ABCDEFGHIJKLMNOPQRST".ToCharArray();

var combination = new StringBuilder(20);

// 単純に整数値をforで回して、各ビットが立っているか調べるだけ
for(int flags = 0; flags < 1048576; flags++)
{
    for(int bit = 0; bit < 20; bit++)
    {
        // 各ビットが立っていれば、チェックされているとみなす
        if( (flags & (0x01 << bit)) != 0)
        {
            combination.Append(buttons[bit]);
        }
    }

    Console.WriteLine(combination.ToString());
    combination.Clear();
}

あえて、Javaでも書く必要はないと思いますが、Javaでもほぼ同じようにできます。

char[] buttons = "ABCDEFGHIJKLMNOPQRST".toCharArray();

StringBuilder combination = new StringBuilder(20);

// 単純に整数値をforで回して、各ビットが立っているか調べるだけ
for(int flags = 0; flags < 1048576; flags++)
{
    for(int bit = 0; bit < 20; bit++)
    {
        // 各ビットが立っていれば、チェックされているとみなす
        if( (flags & (0x01 << bit)) != 0)
        {
            combination.append(buttons[bit]);
        }
    }

    System.out.println(combination.toString());
    combination.setLength(0);
}

(おまけ) n個からk個選ぶ組み合わせの数

n個からk個選んで順番に並べるなら、
$$n \times (n - 1) \times (n - 2) \times \cdots \times (n - k + 1)$$
のようになるはずです。

例えば、5個から3個選んで順番に並べるパターンは、
まずは、5個の選び方があって、残りの4個の選び方があって、さらに残りの3個の選び方がある感じなので、
$5 \times 4 \times 3 = 60$ 通りの選んで並べる方法がありそうです。

選んで順番に並べる必要はなくて、単に、選び方の総数であれば、
上記から、並び方を考慮した分を除外すればよいので、
$k!$ (kの階乗)で割れば良さそうです。

よって、n個からk個選ぶ組み合わせの数的には、
$$\frac{n \times (n - 1) \times (n - 2) \times \cdots \times (n - k + 1)}{k!}$$
になりそうです。

このままだと、"$\cdots$"とか出てきてカッコ悪いので、
階乗だけで表現できるように試みます。

上で出てきた、
$n \times (n - 1) \times (n - 2) \times \cdots \times (n - k + 1)$と、$n!$をよく見くらべて、違いを見てみます。
$n \times (n - 1) \times (n - 2) \times \cdots \times (n - k + 1) \times (n - k) \times (n - k - 1) \times (n - k - 2) \times \cdots \times 2 \times 1$
が、$n!$です。

これは、
$$n \times (n - 1) \times (n - 2) \times \cdots \times (n - k + 1) \times (n - k)!$$
になっていそうです。

ということは、
$n \times (n - 1) \times (n - 2) \times \cdots \times (n - k + 1)$は、
$$\frac{n!}{(n - k)!}$$
と表せそうです。

というわけで、
n個からk個選ぶ組み合わせの数を階乗だけで表せば、
$$\frac{n!}{k!(n - k)!}$$
となります。

よって、

\dbinom{n}{k} = \frac{n!}{k!(n - k)!}\\
{}_n C_k = \frac{n!}{k!(n - k)!}

のような感じです。