Логика для проверки того, что 3 из 4 истинны

Я хочу вернуть, Trueесли и только если 3 из 4 логических значений верны.

Самое близкое, что я получил, это (x ^ y) ^ (a ^ b):

Что я должен делать?

Я предлагаю написать код таким образом, чтобы указать, что вы имеете в виду. Если вы хотите, чтобы 3 значения были истинными, мне кажется естественным, что значение 3 где-то появляется.

Например, в C++:

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

Это хорошо определено в C++: standard (§4.7/4)указывает, что преобразование boolв intдает ожидаемые значения 0 или 1.

В Java и C # вы можете использовать следующую конструкцию:

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

# 1: Использование ветвления?: 3 или 4 операции

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

№ 2 без ветвления, 7 операций

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

Назад, когда я использовал для профилирования всего, я обнаружил, что решения без ветвления были намного более быстрыми операциями для работы, поскольку ЦП мог лучше предсказывать путь к коду и выполнять больше операций в тандеме. Тем не менее, в отчете о ветвлении работы примерно на 50% меньше.

Если бы это был Python, я бы написал

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

Или

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

Или

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

Или

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

Или

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

Или

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

Или

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

Все это работает, так как логические значения являются подклассами целых чисел в Python.

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

Или, вдохновленный этим аккуратным трюком ,

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

Длинная, но очень простая (дизъюнктивная) нормальная форма:

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

Это может быть упрощено, но это требует больше размышлений: P

Не уверен, что это проще, но возможно.

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

Если вы хотите использовать эту логику в языке программирования, я предлагаю

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;
}

Или, если хотите, вы можете поместить все это в одну строку:

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

Также вы можете обобщить эту проблему на 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;
}

Этот ответ зависит от системы представления, но если 0 - единственное значение, интерпретируемое как ложное, и not(false)всегда возвращает одно и то же числовое значение, то not(a) + not(b) + not(c) + not(d) = not(0)следует сделать свое дело.

Имея в виду, что SO, если для вопросов программирования, а не просто логических проблем, ответ, очевидно, зависит от выбора языка программирования. Некоторые языки поддерживают функции, которые не характерны для других.

Например, в C ++ вы можете проверить свои условия с помощью:

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

Это должен быть самый быстрый способ проверки языков, которые поддерживают автоматическое (низкоуровневое) преобразование из логических типов в целочисленные. Но опять же, нет общего ответа на эту проблему.

Лучшее, что я могу сделать, это ((x ^ y) ^ (a ^ b)) && ((a || x) && (b || y))

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

Первое выражение ищет 1 или 3 trueиз 4. Второе исключает 0 или 1 (а иногда и 2) trueиз 4.

Java 8, отфильтруйте ложные значения и посчитайте оставшиеся истинные значения:

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

Тогда вы можете использовать его следующим образом:

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

Легко обобщает для проверки n из mпунктов истинности.

Для проверки, по крайней мере n, из всех Booleanверных (n должно быть меньше или равно общему числу Boolean: p)

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

Изменить : после комментария @ Cruncher

Чтобы проверить 3 booleanиз 4

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

Другой :

((c & d) & (a ^ b)) | ((a & b) & (c ^ d))( Подробности )

Вот способ, которым вы можете решить это в C # с помощью LINQ:

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

Это симметричная булева функция S₃(4). Симметричная логическая функция - это логическая функция, которая зависит только от количества установленных входов, но не зависит от того, какими входами они являются. Кнут упоминает функции этого типа в разделе 7.1.2 тома 4 «Искусство компьютерного программирования».

S₃(4) можно вычислить с помощью 7 операций следующим образом:

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

Кнут показывает, что это оптимально, что означает, что вы не можете сделать это менее чем за 7 операций, используя обычные операторы: &&, || , ^, <,и >.

Однако, если вы хотите использовать это на языке, который использует 1для true и 0для false, вы также можете легко использовать сложение:

x + y + a + b == 3

что делает ваше намерение совершенно ясным.

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

С чисто логической точки зрения это то, что я придумал.

По принципу голубиной дыры, если точно 3 истинно, то либо a и b верны, либо c и d верны. Тогда нужно просто сопоставить каждый из этих случаев точно с одним из двух других.

Таблица правды Вольфрама

Если вы используете инструмент логической визуализации, такой как Karnaugh Maps, вы увидите, что это проблема, когда вы не можете избежать полноценного логического термина, если хотите записать его в одну строку if (...). Лопина это уже показала, проще не написать. Вы можете выделить немного, но это будет трудно читать для вас и для машины.

Подсчет решений не плох, и они показывают, что вы действительно после. Эффективность подсчета зависит от вашего языка программирования. Решения для массива с Python или LinQ приятно смотреть, но будьте осторожны, это МЕДЛЕННО. Wolf's (a + b + x + y) == 3 будет работать хорошо и быстро, но только если ваш язык приравнивает «true» к 1. Если «true» представлен -1, вам придется проверить на -3: )

Если ваш язык использует истинные логические значения, вы можете попытаться запрограммировать его явно (я использую! = В качестве теста 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» работает, только если x, y имеют логический тип. Если это какой-то другой тип, где 0 - false, а все остальное - true, это может не сработать. Затем используйте логическое XOR, или ((bool) x! = (Bool) y), или напишите «if (x) return (y == false) else return (y == true);», что немного больше работать за компьютером.

Если в вашем языке программирования есть оператор ternary? :, вы можете сократить его до

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

который сохраняет читабельность или агрессивно

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

Этот код выполняет ровно три логических теста (состояние a, состояние b, сравнение x и y) и должен быть быстрее, чем большинство других ответов здесь. Но вы должны это прокомментировать, иначе вы не поймете это через 3 месяца :)

Здесь много хороших ответов; Вот альтернативная формулировка, которую еще никто не опубликовал:

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

Похож на первый ответ, но на чистой Java:

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

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

Я предпочитаю считать их целыми числами, потому что это делает код более читабельным.

В Python , чтобы увидеть, сколько из итерируемых элементов является True, используйте sum(это довольно просто):

Настроить

import itertools

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

Актуальный тест

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

Вывод

(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

Если вы ищете решение на бумаге (без программирования), тогда вам нужны алгоритмы K-maps и Quine-McCluskey, которые помогут вам минимизировать вашу булеву функцию.

В вашем случае результат

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

Если вы хотите сделать это программно, с нефиксированным количеством переменных и пользовательским «порогом», то просто выполнить итерацию по списку логических значений и подсчет вхождений «true» довольно просто и просто.

Я хочу вернуть истину, если и только если 3 из 4 логических значений истинны.

Учитывая 4 логических значения, a, b, x, y, эта задача преобразуется в следующий оператор C:

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

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

это то, что вы хотите. По сути, я взял ваш код и добавил, что на самом деле 3 - правда, а 3 - нет.

Вопрос программирования без ответа, включающего рекурсию? Немыслимо!

Существует достаточно «точно 3 из 4 истин» ответов, но вот обобщенная (Java) версия для «точно m из n истин» (в противном случае рекурсия на самом деле не стоит) только потому, что вы можете:

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);
}

Это может быть вызвано что-то вроде:

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

который должен вернуть true(потому что 5 из 8 значений были истинными, как и ожидалось). Не совсем доволен словами «истина» и «ложь», но сейчас не могу придумать лучшего имени ... Обратите внимание, что рекурсия прекращается, когда найдено слишком много true или слишком много falseзначений.

Поскольку удобочитаемость очень важна, вы можете использовать вызов описательной функции (обертывание любой из предложенных реализаций). Если этот расчет необходимо выполнить в нескольких местах, вызов функции является наилучшим способом повторного использования и дает четкое представление о том, что вы делаете.

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

В PHP, чтобы сделать его более динамичным (на случай, если вы измените количество условий и т. Д.):

$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)))

Хотя я мог показать, что это хорошее решение, ответ Сэма Хочевара легко написать и понять позже. В моей книге это лучше.

Вот код C #, который я только что написал, потому что вы меня вдохновили:

Он принимает любое количество аргументов и сообщит вам, являются ли n из них истинными.

    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;                
    }

и вы называете это так:

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

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

Теперь вы можете тестировать 7/9 или 15/100, как хотите.