[JAVA] Puis-je essayer toutes les combinaisons avec une application comportant 20 cases à cocher?

Il y a une case à cocher dans les paramètres de l'application, ou un bouton bascule qui n'a que la valeur ON / OFF. Supposons qu'il y en ait 20.

Cela ressemble à ceci (bien qu'il n'y en ait que trois dans l'exemple).

Case à cocher

Bouton à bascule binaire tel que ON / OFF

Considérez la combinaison.

S'il s'agit d'une case à cocher générale Chaque case à cocher est Puisqu'il ne comporte que deux états, "coché" et "non coché", S'il y a n cases à cocher, le nombre total de combinaisons est Il est de 2 à la nième puissance (2 $ ^ n $).

S'il y en a 20, c'est 2 à la 20e puissance (2 $ ^ {20} $), donc Il existe plus d'un million de combinaisons, avec 1 048 576 combinaisons.

Sans beaucoup de courage, il semble impossible d'essayer toutes les combinaisons manuellement. Actuellement, Amazon semble avoir plus de 500000 employés, donc Je pense que ce serait bien si tout le monde pouvait coopérer, Compte tenu de la difficulté de le gérer, ce sera presque impossible. (Les tests sociaux sont un bon moyen de vous guider afin que tout soit couvert. Cela peut ne pas être impossible si vous pouvez sécuriser un nombre considérable d'utilisateurs. )

Considérez la combinaison sous un angle différent.

Simplement parce qu'il y a n "" coché "et" décoché "" Vous pouvez le considérer comme 2 à la nième puissance, Vous pouvez voir les choses différemment.

S'il y a n cases à cocher,

0 sur n sont vérifiés
1 sur n est vérifié
2 sur n sont cochés
...
n-1 sur n sont vérifiés
n sur n sont vérifiés

C'est comme ressentir. Si vous les ajoutez tous ensemble, vous devriez obtenir le même nombre de combinaisons.

(Nombre de combinaisons où 0 sur n est vérifié) +
(Nombre de combinaisons où 1 sur n est vérifié) +
(Nombre de combinaisons où 2 sur n sont vérifiées) +
... +
(n sur n-Nombre de combinaisons où une est cochée) +
(Nombre de combinaisons où n sur n est vérifié)

Calculons.

La combinaison de n à k sélections peut être représentée par les symboles suivants.

\dbinom{n}{k}

Au sens de combinaison Selon la personne, ce qui suit peut être plus familier.

{}_n C_k

Par conséquent, à partir de n, 0, 1, 2, 3, ..., n doit être additionné pour chaque combinaison. Je me sens comme cela.

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

Selon le spectateur, il peut immédiatement sembler familier. Cela ressemble à un modèle inclus dans le théorème binaire.

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

Remplacer $ x = 1, y = 1 $ est exactement ce que vous voulez.

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

Maintenant, à la fin, il s'avère être le même que 2 à la nième puissance ($ 2 ^ n $).

Essayez d'écrire toutes les combinaisons.

S'il y a deux états, "coché" et "non coché", Si vous considérez chaque bit du nombre binaire comme un drapeau et que vous le faites correspondre à 0 ou 1, il n'est pas vérifié, etc. Cela semble facile à écrire.

Il n'est pas pratique d'essayer de très grandes combinaisons manuellement, Il peut être possible de couvrir la combinaison en l'incorporant dans un test unitaire automatisé ou similaire. (On suppose qu'il s'agit d'une combinaison significative. S'il s'agit d'une case à cocher qui ne s'applique pas, il est nécessaire de déterminer si des tests sont nécessaires. )

Il y a 20 cases à cocher jusqu'à A, B, C, ..., R, S, T, Si vous listez toutes les combinaisons d'états cochés, par exemple, ce sera comme suit. C'est un code assez dur donc ce n'est pas cool, Lors de la rédaction d'un article, mettez l'accent sur la clarté J'ose faire un code dur et une implémentation stupide.

Il ressemble à ceci lorsqu'il est écrit en C #.

var buttons = "ABCDEFGHIJKLMNOPQRST".ToCharArray();

var combination = new StringBuilder(20);

//Tournez simplement la valeur entière avec for pour voir si chaque bit est défini
for(int flags = 0; flags < 1048576; flags++)
{
    for(int bit = 0; bit < 20; bit++)
    {
        //Si chaque bit est activé, il est considéré comme vérifié
        if( (flags & (0x01 << bit)) != 0)
        {
            combination.Append(buttons[bit]);
        }
    }

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

Je ne pense pas qu'il soit nécessaire d'écrire en Java, mais vous pouvez faire presque la même chose en Java.

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

StringBuilder combination = new StringBuilder(20);

//Tournez simplement la valeur entière avec for pour voir si chaque bit est défini
for(int flags = 0; flags < 1048576; flags++)
{
    for(int bit = 0; bit < 20; bit++)
    {
        //Si chaque bit est activé, il est considéré comme vérifié
        if( (flags & (0x01 << bit)) != 0)
        {
            combination.append(buttons[bit]);
        }
    }

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

(Bonus) Nombre de combinaisons à choisir de n à k

Si vous sélectionnez k parmi n et les organisez dans l'ordre $n \times (n - 1) \times (n - 2) \times \cdots \times (n - k + 1)$ Ça devrait ressembler à ça.

Par exemple, un motif qui sélectionne 5 à 3 et les organise dans l'ordre est Tout d'abord, il y a 5 façons de choisir, les 4 autres façons de choisir, puis les 3 autres façons de choisir. $ 5 \ times 4 \ times 3 = 60 $ Il semble y avoir un moyen de les sélectionner et de les organiser.

Vous n'avez pas à les cueillir et les commander, juste le nombre total de choix De ce qui précède, il suffit d'exclure la partie considérant l'arrangement, donc Il semble bon de diviser par $ k! $ (La puissance de k).

Par conséquent, en termes de nombre de combinaisons pour sélectionner k parmi n, $\frac{n \times (n - 1) \times (n - 2) \times \cdots \times (n - k + 1)}{k!}$ Il semble que.

À ce rythme, "$ \ cdots $" apparaîtra et ce n'est pas cool, donc J'essaierai de l'exprimer uniquement par plancher.

Sorti au-dessus, Comparez $ n \ times (n --1) \ times (n --2) \ times \ cdots \ times (n --k + 1) $ et $ n! $ Pour voir la différence. 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 Soit $ n! $.

c'est, $n \times (n - 1) \times (n - 2) \times \cdots \times (n - k + 1) \times (n - k)!$ Il semble que.

Cela signifie $ n \ times (n --1) \ times (n --2) \ times \ cdots \ times (n --k + 1) $ est $\frac{n!}{(n - k)!}$ Il semble que cela puisse être exprimé comme.

alors, Si le nombre de combinaisons pour sélectionner k parmi n est exprimé uniquement par le plancher, $\frac{n!}{k!(n - k)!}$ Ce sera.

Donc,

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

C'est comme ressentir.