Logika untuk menguji bahwa 3 dari 4 Benar

Saya ingin kembali Truejika dan hanya jika 3 dari 4 nilai boolean benar.

Yang paling dekat yang saya dapatkan adalah (x ^ y) ^ (a ^ b):

Apa yang harus saya lakukan?

Saya sarankan menulis kode dengan cara yang menunjukkan apa yang Anda maksud. Jika Anda ingin 3 nilai menjadi benar, tampaknya wajar bagi saya bahwa nilai 3 muncul di suatu tempat.

Misalnya, di C++:

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

Ini didefinisikan dengan baik dalam C++: yang standard (§4.7/4)menunjukkan bahwa konversi booluntuk intmemberikan nilai yang diharapkan 0 atau 1.

Di Java dan C #, Anda dapat menggunakan konstruk berikut:

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

# 1: Menggunakan operasi percabangan?: 3 atau 4

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

# 2 Tanpa Cabang, 7 operasi

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

Kembali ketika saya gunakan untuk profil segalanya, saya menemukan solusi non-cabang agak lebih cepat operasi-untuk-operasi karena CPU dapat memprediksi jalur kode yang lebih baik, dan menjalankan lebih banyak operasi secara bersamaan. Ada sekitar 50% lebih sedikit pekerjaan dalam pernyataan percabangan di sini.

Jika ini Python, saya akan menulis

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

Atau

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

Atau

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

Atau

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

Atau

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

Atau

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

Atau

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

Semua ini bekerja, karena Boolean adalah subclass dari integer dengan Python.

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

Atau, terinspirasi oleh trik yang rapi ini ,

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

Bentuk normal yang panjang tapi sangat sederhana, (disjuntive):

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

Ini mungkin disederhanakan tetapi itu membutuhkan lebih banyak pemikiran: P

Tidak yakin itu lebih sederhana, tapi mungkin.

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

Jika Anda ingin menggunakan logika ini dalam bahasa pemrograman, saran saya adalah

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

Atau jika Anda mau, Anda bisa meletakkan semua ini dalam satu baris:

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

Anda juga dapat menggeneralisasi masalah ini ke 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;
}

Jawaban ini tergantung pada sistem representasi, tetapi jika 0 adalah satu-satunya nilai yang ditafsirkan sebagai salah, dan not(false)selalu mengembalikan nilai numerik yang sama, maka not(a) + not(b) + not(c) + not(d) = not(0)harus melakukan trik.

Perlu diingat bahwa SO jika untuk pertanyaan pemrograman, bukan hanya masalah logis, jawabannya jelas tergantung pada pilihan bahasa pemrograman. Beberapa bahasa mendukung fitur yang tidak biasa bagi orang lain.

Misalnya, dalam C ++ Anda dapat menguji kondisi Anda dengan:

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

Ini harus menjadi cara tercepat untuk melakukan pemeriksaan dalam bahasa yang mendukung konversi otomatis (level rendah) dari tipe boolean ke integer. Tetapi sekali lagi, tidak ada jawaban umum untuk masalah itu.

Yang terbaik yang bisa saya lakukan adalah ((x ^ y) ^ (a ^ b)) && ((a || x) && (b || y))

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

Ekspresi pertama mencari 1 atau 3 truedari 4. Yang kedua menghilangkan 0 atau 1 (dan kadang-kadang 2) truedari 4.

Java 8, memfilter nilai palsu, dan menghitung nilai sebenarnya yang tersisa:

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

Maka Anda dapat menggunakannya sebagai berikut:

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

Mudah generalizes untuk memeriksa ndari mitem menjadi benar.

Untuk memeriksa setidaknya nsemua Booleanitu benar, (n harus kurang dari atau sama dengan jumlah total Boolean: p)

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

Sunting : Setelah komentar @ Cruncher

Untuk memeriksa 3 booleandari 4

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

Yang lainnya :

((c & d) & (a ^ b)) | ((a & b) & (c ^ d))( Detail )

Inilah cara Anda bisa menyelesaikannya dalam C # dengan LINQ:

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

Itu adalah fungsi Boolean simetris S₃(4). Fungsi Boolean simetris adalah fungsi boolean yang hanya bergantung pada jumlah input yang ditetapkan, tetapi tidak bergantung pada input mana yang mereka inputkan. Knuth menyebutkan fungsi jenis ini di bagian 7.1.2 di Volume 4 dari The Art of Computer Programming.

S₃(4) dapat dihitung dengan 7 operasi sebagai berikut:

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

Knuth menunjukkan bahwa ini optimal, artinya Anda tidak dapat melakukan ini dalam kurang dari 7 operasi menggunakan operator normal: &&, || , ^, <,dan >.

Namun jika Anda ingin menggunakan ini dalam bahasa yang menggunakan 1benar dan 0salah, Anda juga dapat menggunakan tambahan dengan mudah:

x + y + a + b == 3

yang membuat niat Anda cukup jelas.

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

Dari sudut pandang logika murni inilah yang saya temukan.

Dengan prinsip lubang merpati, jika tepat 3 benar, maka a dan b benar, atau c dan d benar. Maka itu hanya masalah anding masing-masing kasus dengan tepat satu dari yang lain 2.

Tabel kebenaran Wolfram

Jika Anda menggunakan alat visualisasi logika seperti Karnaugh Maps, Anda melihat bahwa ini adalah masalah di mana Anda tidak dapat menghindari istilah logika penuh sesak jika Anda ingin menulisnya dalam satu baris if (...). Lopina sudah menunjukkannya, tidak mungkin untuk menulisnya dengan lebih sederhana. Anda dapat sedikit faktor, tetapi akan tetap sulit dibaca untuk Anda DAN untuk mesin.

Menghitung solusi tidak buruk dan mereka menunjukkan apa yang benar-benar Anda cari. Cara Anda menghitung secara efisien tergantung pada bahasa pemrograman Anda. Solusi array dengan Python oder LinQ bagus untuk dilihat, tetapi berhati-hatilah, ini PERLAHAN. Wolf's (a + b + x + y) == 3 akan bekerja dengan baik dan cepat, tetapi hanya jika bahasa Anda menyamakan "true" dengan 1. Jika "true" diwakili oleh -1, Anda harus menguji -3: )

Jika bahasa Anda menggunakan boolean sejati, Anda dapat mencoba memprogramnya secara eksplisit (saya menggunakan! = Sebagai tes 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" hanya berfungsi jika x, y adalah tipe boolean. Jika mereka adalah tipe lain di mana 0 salah dan yang lainnya benar, ini bisa gagal. Kemudian gunakan boolean XOR, atau ((bool) x! = (Bool) y), atau tulis "jika (x) kembali (y == salah) lain kembali (y == benar);", yang sedikit lebih bekerja untuk komputer.

Jika bahasa pemrograman Anda menyediakan operator ternary?:, Anda dapat mempersingkatnya menjadi

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

yang membuat sedikit mudah dibaca, atau memotongnya secara agresif

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

Kode ini melakukan persis tiga tes logika (keadaan a, keadaan b, perbandingan x dan y) dan harus lebih cepat daripada sebagian besar jawaban lain di sini. Tapi Anda perlu berkomentar, atau Anda tidak akan memahaminya setelah 3 bulan :)

Ada banyak jawaban bagus di sini; berikut adalah formulasi alternatif yang belum diposting oleh orang lain:

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

Mirip dengan jawaban pertama, tetapi Java murni:

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

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

Saya lebih suka menghitungnya sebagai bilangan bulat karena membuat kode lebih mudah dibaca.

Dalam Python , untuk melihat berapa banyak dari elemen yang dapat diubah Benar, gunakan sum(cukup mudah):

Mempersiapkan

import itertools

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

Tes Aktual

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

Keluaran

(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

Jika Anda mencari solusi on-the-paper (non-pemrograman), maka K-maps dan algoritma Quine-McCluskey adalah yang Anda cari, mereka membantu Anda memperkecil fungsi boolean Anda.

Dalam kasus Anda, hasilnya adalah

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

Jika Anda ingin melakukan ini secara program, jumlah variabel yang tidak tetap dan "ambang" kustom, maka cukup iterasi melalui daftar nilai boolean dan menghitung kejadian "benar" cukup sederhana dan mudah.

Saya ingin mengembalikan true jika dan hanya jika 3 dari 4 nilai boolean benar.

Dengan 4 nilai boolean, a, b, x, y, tugas ini diterjemahkan ke dalam pernyataan C berikut:

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

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

adalah apa yang kamu inginkan. Pada dasarnya saya mengambil kode Anda dan menambahkan memeriksa apakah 3 benar dan 3 tidak salah.

Pertanyaan pemrograman tanpa jawaban yang melibatkan rekursi? Tak terbayangkan!

Ada cukup jawaban "tepat 3 dari 4 tanda", tetapi inilah versi umum (Java) untuk "persisnya keluar dari tanda" (jika rekursi tidak benar-benar layak) hanya karena Anda dapat:

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

Ini bisa disebut dengan sesuatu seperti:

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

yang harus dikembalikan true(karena 5 dari 8 nilai benar, seperti yang diharapkan). Tidak cukup senang dengan kata-kata "trues" dan "falses", tetapi tidak dapat memikirkan nama yang lebih baik sekarang .... Perhatikan bahwa rekursi berhenti ketika terlalu banyak true atau terlalu banyak falsenilai telah ditemukan.

Karena keterbacaan adalah masalah besar, Anda bisa menggunakan panggilan fungsi deskriptif (membungkus salah satu implementasi yang disarankan). Jika perhitungan ini perlu dilakukan di banyak tempat, pemanggilan fungsi adalah cara terbaik untuk mencapai penggunaan kembali, dan memperjelas apa yang Anda lakukan.

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

Di PHP, buatlah lebih dinamis (kalau-kalau Anda mengubah sejumlah kondisi, dll.):

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

Sementara saya bisa menunjukkan bahwa ini adalah solusi yang baik, jawaban Sam Hocevar mudah untuk ditulis dan dipahami kemudian. Dalam buku saya itu membuatnya lebih baik.

Berikut adalah beberapa kode c # yang baru saja saya tulis karena Anda telah menginspirasi saya:

Dibutuhkan sejumlah argumen dan akan memberi tahu Anda jika tidak ada yang benar.

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

dan Anda menyebutnya seperti itu:

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

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

Jadi sekarang Anda dapat menguji 7/9 atau 15/100 seperti yang Anda mau.