Logique pour tester que 3 sur 4 sont vrais

Je veux retourner Truesi et seulement si 3 valeurs booléennes sur 4 sont vraies.

Le plus proche que j'ai obtenu est (x ^ y) ^ (a ^ b):

Que devrais-je faire?

Je suggère d'écrire le code d'une manière qui indique ce que vous voulez dire. Si vous voulez que 3 valeurs soient vraies, il me semble naturel que la valeur 3 apparaisse quelque part.

Par exemple, dans C++:

if ((int)a + (int)b + (int)c + (int)d == 3)
    ...

Ceci est bien défini dans C++: le standard (§4.7/4)indique que la conversion boolen intdonne les valeurs attendues 0 ou 1.

En Java et C #, vous pouvez utiliser la construction suivante:

if ((a?1:0) + (b?1:0) + (c?1:0) + (d?1:0) == 3)
    ...

# 1: Utilisation d'un branchement?: 3 ou 4 opérations

A ^ B ? C & D : ( C ^ D ) & A

# 2 sans branchement, 7 opérations

(A ^ B ^ C ^ D) & ((A & B) | (C & D))

À l'époque où j'utilisais pour tout profiler, j'ai trouvé que les solutions sans branchement étaient un fonctionnement un peu plus rapide car le processeur pouvait mieux prédire le chemin du code et exécuter plus d'opérations en tandem. Il y a cependant environ 50% de travail en moins dans la déclaration de branchement ici.

Si cela avait été Python, j'aurais écrit

if [a, b, c, d].count(True) == 3:

Ou

if [a, b, c, d].count(False) == 1:

Ou

if [a, b, c, d].count(False) == True:
# In Python True == 1 and False == 0

Ou

print [a, b, c, d].count(0) == 1

Ou

print [a, b, c, d].count(1) == 3

Ou

if a + b + c + d == 3:

Ou

if sum([a, b, c, d]) == 3:

Tout cela fonctionne, puisque les booléens sont des sous-classes d'entiers en Python.

if len(filter(bool, [a, b, c, d])) == 3:

Ou, inspiré par cette astuce soignée ,

data = iter([a, b, c, d])
if not all(data) and all(data):

Forme normale longue mais très simple (disjonctive):

 (~a & b & c & d) | (a & ~b & c & d) | (a & b & ~c & d) | (a & b & c & ~d)

Cela peut être simplifié mais cela demande plus de réflexion: P

Pas sûr que ce soit plus simple, mais peut-être.

((x xor y) and (a and b)) or ((x and y) and (a xor b))

Si vous souhaitez utiliser cette logique dans un langage de programmation, ma suggestion est

bool test(bool a, bool b, bool c, bool d){
    int n1 = a ? 1 : 0;
    int n2 = b ? 1 : 0;
    int n3 = c ? 1 : 0;
    int n4 = d ? 1 : 0;

    return n1 + n2 + n3 + n4 == 3;
}

Ou si vous le souhaitez, vous pouvez mettre tout cela sur une seule ligne:

return (a ? 1 : 0) + (b ? 1 : 0) + (C ? 1 : 0) + (d ? 1 : 0) == 3;

Vous pouvez également généraliser ce problème à n of m :

bool test(bool *values, int n, int m){
    int sum = 0;
    for(int i = 0; i < m; i += 1){
        sum += values[i] ? 1 : 0;
    }
    return sum == n;
}

Cette réponse dépend du système de représentation, mais si 0 est la seule valeur interprétée comme fausse, et not(false)renvoie toujours la même valeur numérique, alors not(a) + not(b) + not(c) + not(d) = not(0)devrait faire l'affaire.

Gardant à l'esprit que SO si pour des questions de programmation, plutôt que de simples problèmes logiques, la réponse dépend évidemment du choix d'un langage de programmation. Certaines langues prennent en charge des fonctionnalités qui ne sont pas communes à d'autres.

Par exemple, en C ++, vous pouvez tester vos conditions avec:

(a + b + c + d) == 3

Cela devrait être le moyen le plus rapide de vérifier les langues qui prennent en charge la conversion automatique (de bas niveau) des types booléens en types entiers. Mais encore une fois, il n'y a pas de réponse générale à ce problème.

Le mieux que je puisse faire est ((x ^ y) ^ (a ^ b)) && ((a || x) && (b || y))

((a xor b) xor (c xor d)) and ((a or b) and (c or d))

La première expression recherche 1 ou 3 truesur 4. La seconde élimine 0 ou 1 (et parfois 2) truesur 4.

Java 8, filtrez les fausses valeurs et comptez les valeurs vraies restantes:

public static long count(Boolean... values) {
    return Arrays.stream(values).filter(t -> t).count();
}

Ensuite, vous pouvez l'utiliser comme suit:

if (3 == count(a, b, c, d)) {
    System.out.println("There... are... THREE... lights!");
}

Se généralise facilement à la vérification ndes méléments.

Pour vérifier au moins nsur tous Booleansont vrais, (n doit être inférieur ou égal au nombre total de Boolean: p)

if (((a ? 1:0) + (b ? 1:0 ) + (c ? 1:0) + (d ? 1:0 )) >= n) {
    // do the rest
}

Edit : Après le commentaire de @ Cruncher

Pour vérifier 3 booleansur 4

if (((a ? 1:0) + (b ? 1:0 ) + (c ? 1:0) + (d ? 1:0 )) == 3) {
    // do the rest
}

Un autre :

((c & d) & (a ^ b)) | ((a & b) & (c ^ d))( Détails )

Voici un moyen de le résoudre en C # avec LINQ:

bool threeTrue = new[] { a, b, x, y }.Count(x => x) == 3;

C'est la fonction booléenne symétrique S₃(4). Une fonction booléenne symétrique est une fonction booléenne qui ne dépend que de la quantité d'entrées définie, mais ne dépend pas de quelles entrées elles sont. Knuth mentionne des fonctions de ce type dans la section 7.1.2 du volume 4 de The Art of Computer Programming.

S₃(4) peut être calculé avec 7 opérations comme suit:

(x && y && (a || b)) ^ ((x || y) && a && b)

Knuth montre que c'est optimal, ce qui signifie que vous ne pouvez pas le faire en moins de 7 opérations en utilisant les opérateurs normaux: &&, || , ^, <,et >.

Cependant, si vous souhaitez l'utiliser dans un langage qui utilise 1pour vrai et 0pour faux, vous pouvez également utiliser l'addition facilement:

x + y + a + b == 3

ce qui rend votre intention très claire.

(a && b && (c xor d)) || (c && d && (a xor b))

D'un point de vue purement logique, c'est ce que j'ai proposé.

Selon le principe du casier, si exactement 3 sont vrais, alors soit a et b sont vrais, soit c et d sont vrais. Ensuite, c'est juste une question de et de chacun de ces cas avec exactement l'un des 2 autres.

Table de vérité Wolfram

Si vous utilisez un outil de visualisation logique comme Karnaugh Maps, vous voyez que c'est un problème où vous ne pouvez pas éviter un terme logique complet si vous voulez l'écrire dans une ligne if (...). Lopina l'a déjà montré, il n'est pas possible de l'écrire plus simplement. Vous pouvez tenir compte un peu, mais cela restera difficile à lire pour vous ET pour la machine.

Les solutions de comptage ne sont pas mauvaises et elles montrent ce que vous recherchez vraiment. La manière dont vous comptez efficacement dépend de votre langage de programmation. Les solutions de tableaux avec Python ou LinQ sont agréables à regarder, mais attention, c'est LENT. Wolf's (a + b + x + y) == 3 fonctionnera bien et rapidement, mais seulement si votre langage équivaut à "vrai" avec 1. Si "vrai" est représenté par -1, vous devrez tester -3: )

Si votre langage utilise de vrais booléens, vous pouvez essayer de le programmer explicitement (j'utilise! = Comme test XOR):

if (a)
{
    if (b)
        return (x != y);    // a,b=true, so either x or y must be true
    else
        return (x && y);     // a=true, b=false, so x AND y must be true
}
else
{
    if (b)
        return (x && y);    // a=false, b=true, so x and y must be true
    else
        return false;       // a,b false, can't get 3 of 4
}

"x! = y" ne fonctionne que si x, y sont de type booléen. S'ils sont d'un autre type où 0 est faux et tout le reste est vrai, cela peut échouer. Ensuite, utilisez un XOR booléen, ou ((bool) x! = (Bool) y), ou écrivez "if (x) return (y == false) else return (y == true);", ce qui est un peu plus travailler pour l'ordinateur.

Si votre langage de programmation fournit l'opérateur ternaire?:, Vous pouvez le raccourcir en

if (a)
    return b ? (x != y) : (x && y);
else
    return b ? (x && y) : false;

qui garde un peu de lisibilité, ou le coupe agressivement pour

return a ? (b ? (x != y) : (x && y)) : (b ? (x && y) : false);

Ce code effectue exactement trois tests logiques (état de a, état de b, comparaison de x et y) et devrait être plus rapide que la plupart des autres réponses ici. Mais vous devez le commenter, sinon vous ne le comprendrez pas après 3 mois :)

Il y a beaucoup de bonnes réponses ici; voici une formulation alternative que personne d'autre n'a encore publiée:

 a ? (b ? (c ^ d) : (c && d)) : (b && c && d)

Similaire à la première réponse, mais pur Java:

int t(boolean b) {
    return (b) ? 1 : 0;
}

if (t(x) + t(y) + t(a) + t(b) == 3) return true;
return false;

Je préfère les compter comme des entiers car cela rend le code plus lisible.

En Python , pour voir combien d'éléments itérables sont True, utilisez sum(c'est assez simple):

Installer

import itertools

arrays = list(itertools.product(*[[True, False]]*4))

Test réel

for array in arrays:
    print(array, sum(array)==3)

Production

(True, True, True, True) False
(True, True, True, False) True
(True, True, False, True) True
(True, True, False, False) False
(True, False, True, True) True
(True, False, True, False) False
(True, False, False, True) False
(True, False, False, False) False
(False, True, True, True) True
(False, True, True, False) False
(False, True, False, True) False
(False, True, False, False) False
(False, False, True, True) False
(False, False, True, False) False
(False, False, False, True) False
(False, False, False, False) False

Si vous recherchez la solution sur papier (sans programmation), alors les algorithmes K-maps et Quine-McCluskey sont ce que vous recherchez, ils vous aident à minimiser votre fonction booléenne.

Dans votre cas, le résultat est

y = (x̄3 ^ x2 ^ x1 ^ x0) ∨ (x3 ^ x̄2 ^ x1 ^ x0) ∨ (x3 ^ x2 ^ x̄1 ^ x0) ∨ (x3 ^ x2 ^ x1 ^ x̄0)

Si vous voulez faire cela par programme, une quantité non fixe de variables et un "seuil" personnalisé, alors simplement itérer à travers une liste de valeurs booléennes et compter les occurrences de "vrai" est assez simple et direct.

Je veux retourner vrai si et seulement si 3 valeurs booléennes sur 4 sont vraies.

Étant donné les 4 valeurs booléennes, a, b, x, y, cette tâche se traduit par l'instruction C suivante:

return (a+b+x+y) == 3;

((a^b)^(x^y))&((a|b)&(x|y))

est ce que vous voulez. En gros, j'ai pris votre code et ajouté la vérification si en fait 3 sont vrais et non 3 sont faux.

Une question de programmation sans réponse impliquant la récursivité? Inconcevable!

Il y a assez de réponses "exactement 3 sur 4 vrais", mais voici une version généralisée (Java) pour "exactement m sur n vrais" (sinon la récursion n'en vaut pas vraiment la peine) simplement parce que vous pouvez:

public static boolean containsTrues(boolean[] someBooleans,
    int anIndex, int truesExpected, int truesFoundSoFar) {
  if (anIndex >= someBooleans.length) {
    return truesExpected == truesFoundSoFar; // reached end
  }
  int falsesExpected = someBooleans.length - truesExpected;
  boolean currentBoolean = someBooleans[anIndex];
  int truesFound = truesFoundSoFar + (currentBoolean ? 1 : 0);
  if (truesFound > truesExpected) {
    return false;
  }
  if (anIndex - truesFound > falsesExpected) {
    return false; // too many falses
  }
  return containsTrues(someBooleans, anIndex + 1, truesExpected,
      truesFound);
}

Cela pourrait être appelé avec quelque chose comme:

 boolean[] booleans = { true, false, true, true, false, true, true, false };
 containsTrues(booleans, 0, 5, 0);

qui devrait retourner true(car 5 des 8 valeurs étaient vraies, comme prévu). Pas tout à fait satisfait des mots "vrai" et "faux", mais je ne peux pas penser à un meilleur nom pour le moment .... Notez que la récursion s'arrête quand trop true ou trop de falsevaleurs ont été trouvées.

Puisque la lisibilité est un gros problème, vous pouvez utiliser un appel de fonction descriptive (encapsulant l'une des implémentations suggérées). Si ce calcul doit être effectué à plusieurs endroits, un appel de fonction est le meilleur moyen de réutiliser et indique exactement ce que vous faites.

bool exactly_three_true_from(bool cond1, bool cond2, bool cond3, bool cond4)
{
    //...
}

En PHP, en le rendant plus dynamique (juste au cas où vous changeriez le nombre de conditions, etc.):

$min = 6;
$total = 10;

// create our boolean array values
$arr = array_map(function($a){return mt_rand(0,1)>0;},range(1,$total));

// the 'check'
$arrbools = array_map(function($a){return (int)$a;},$arr);
$conditionMet = array_sum($arrbools)>=$min;

echo $conditionMet ? "Passed" : "Failed";

(((a AND b) OR (x AND y)) AND ((a XOR b) OR (x XOR y)))

Bien que je puisse montrer que c'est une bonne solution, la réponse de Sam Hocevar est facile à la fois à écrire et à comprendre plus tard. Dans mon livre, ça fait mieux.

Voici un code c # que je viens d'écrire parce que vous m'avez inspiré:

Il prend n'importe quelle quantité d'arguments et vous dira si n d'entre eux sont vrais.

    static bool boolTester(int n, params bool[] values)
    {
        int sum = 0;           

        for (int i = 0; i < values.Length; i++)
        {
            if (values[i] == true)
            {
                sum += 1;
            }                
        }
        if( sum == n)
        {
            return true;
        }            
        return false;                
    }

et vous l'appelez comme ça:

        bool a = true;
        bool b = true;
        bool c = true;
        bool d = false;            

        bool test = false;
        test = boolTester(3, a, b, c, d);

Vous pouvez donc désormais tester 7/9 ou 15/100 comme vous le souhaitez.