[JAVA] Can I try all combinations with an app that has 20 checkboxes?

Checkboxes in the settings of the app, or toggle buttons with only ON / OFF values Suppose there are 20.

It looks like this (although there are only three in the example).

Checkbox

Binary toggle button such as ON / OFF

Consider the combination.

If it is a general check box Each checkbox is Since it has only two states, "checked" and "unchecked", If there are n checkboxes, the total number of combinations is It is 2 to the nth power ($ 2 ^ n $).

If there are 20, it is 2 to the 20th power ($ 2 ^ {20} $), so There are more than a million combinations, with 1,048,576 combinations.

Without a great deal of guts, it seems impossible to try all combinations manually. Currently, Amazon seems to have more than 500,000 employees, so I think it would be nice if everyone could cooperate, Considering the trouble of managing it, it will be almost impossible. (Social testing is a good way to guide you so that everything is covered. It may not be impossible if you can secure a considerable number of users. )

Consider the combination from a different perspective.

Simply because there are n "" checked "and" unchecked "" You can think of it as 2 to the nth power, You can look at it differently.

If there are n checkboxes,

0 out of n are checked
1 out of n is checked
2 out of n are checked
...
n-1 out of n are checked
n out of n are checked

It feels like. If you add them all together, you should get the same number of combinations.

(Number of combinations where 0 out of n are checked) +
(Number of combinations where 1 out of n is checked) +
(Number of combinations where 2 out of n are checked) +
... +
(n out of n-Number of combinations where one is checked) +
(Number of combinations where n out of n are checked)

Let's calculate.

The combination of n to k selections may be represented by the following symbols.

\dbinom{n}{k}

In the sense of combination Depending on the person, the following may be more familiar.

{}_n C_k

Therefore, from n, 0, 1, 2, 3, ..., n must be added together for each combination. I feel like this.

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

Depending on the viewer, it may immediately look familiar. It looks like a pattern included in the binomial theorem.

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

Substituting $ x = 1, y = 1 $ is exactly what you want.

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

This turns out to be the same as 2 to the nth power ($ 2 ^ n $).

Try to write out all the combinations.

If there are two states, "checked" and "unchecked", If each bit of the binary number is regarded as a flag and 0 or 1 is not checked, it corresponds to It seems easy to write out.

It's not practical to try very large combinations manually, It may be possible to cover the combinations by incorporating them into automated unit tests. (It is assumed that it is a meaningful combination. If it is a checkbox that does not affect each other, it is necessary to consider whether testing is necessary. )

There are 20 checkboxes up to A, B, C, ..., R, S, T, For example, if you list all the combinations of checked states, it will be as follows. It's pretty hard code so it's not cool, When writing an article, focus on clarity I dare to implement it hard code and stupid.

It looks like this when written in C #.

var buttons = "ABCDEFGHIJKLMNOPQRST".ToCharArray();

var combination = new StringBuilder(20);

//Simply turn the integer value with for to see if each bit is set
for(int flags = 0; flags < 1048576; flags++)
{
    for(int bit = 0; bit < 20; bit++)
    {
        //If each bit is set, it is considered to be checked.
        if( (flags & (0x01 << bit)) != 0)
        {
            combination.Append(buttons[bit]);
        }
    }

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

I don't think it's necessary to write in Java, but you can do almost the same in Java.

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

StringBuilder combination = new StringBuilder(20);

//Simply turn the integer value with for to see if each bit is set
for(int flags = 0; flags < 1048576; flags++)
{
    for(int bit = 0; bit < 20; bit++)
    {
        //If each bit is set, it is considered to be checked.
        if( (flags & (0x01 << bit)) != 0)
        {
            combination.append(buttons[bit]);
        }
    }

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

(Bonus) Number of combinations to choose from n to k

If you select k from n and arrange them in order, $n \times (n - 1) \times (n - 2) \times \cdots \times (n - k + 1)$ It should look like this.

For example, a pattern that selects 5 to 3 and arranges them in order is First of all, there are 5 ways to choose, the remaining 4 ways to choose, and then the remaining 3 ways to choose. $ 5 \ times 4 \ times 3 = 60 $ There seems to be a way to choose and arrange them.

You don't have to pick and order them, just the total number of choices From the above, it is sufficient to exclude the part considering the arrangement, so Divide by $ k! $ (Factial of k).

Therefore, in terms of the number of combinations to select k from n, $\frac{n \times (n - 1) \times (n - 2) \times \cdots \times (n - k + 1)}{k!}$ It seems to be.

At this rate, "$ \ cdots $" will appear and it's not cool, so I will try to express it only by factorial.

Came out above, Take a closer look at $ n \ times (n --1) \ times (n --2) \ times \ cdots \ times (n --k + 1) $ and $ n! $ To see the difference. 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 Is $ n! $.

this is, $n \times (n - 1) \times (n - 2) \times \cdots \times (n - k + 1) \times (n - k)!$ It seems to be.

That means $ n \ times (n --1) \ times (n --2) \ times \ cdots \ times (n --k + 1) $ is $\frac{n!}{(n - k)!}$ It seems that it can be expressed as.

so, If the number of combinations to select k from n is expressed only by factorial, $\frac{n!}{k!(n - k)!}$ It will be.

Therefore,

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

It feels like.