Gerrymandering mit Logic Gates

16

Die Majoritätsfunktion ist eine boolesche Funktion, die drei boolesche Eingaben verwendet und die am häufigsten verwendete zurückgibt. Wenn zum Beispiel maj(x,y,z)die Mehrheitsfunktion ist und Twahr und Ffalsch bedeutet, dann:

maj(T,T,T) = T
maj(T,T,F) = T
maj(T,F,F) = F
maj(F,F,F) = F

Diese Frage betrifft das Schreiben von Booleschen Funktionen als Kompositionen von Mehrheitsfunktionen. Ein Beispiel für eine fünfstellige Zusammensetzung von Mehrheitsfunktionen ist (x1,x2,x3,x4,x5) => maj(x1,x2,maj(x3,x4,x5)). Diese Funktion gibt die folgende Ausgabe für diese Beispieleingabevektoren zurück:

(T,T,F,F,F) => maj(T,T,maj(F,F,F)) = maj(T,T,F) = T
(T,F,T,T,F) => maj(T,F,maj(T,T,F)) = maj(T,F,T) = T
(T,F,T,F,F) => maj(T,F,maj(T,F,F)) = maj(T,F,F) = F
(F,F,F,T,T) => maj(F,F,maj(F,T,T)) = maj(F,F,T) = F

Aufgabe

Schreiben Sie ein Programm, das eine positive ganze Zahl n und eine Liste mit Vektoren der Länge n von Booleschen Werten eingibt und einen Baum von Mehrheitsgattern ausgibt, der nach Möglichkeit für alle gegebenen Vektoren true zurückgibt. Die Funktion kann für Vektoren, die nicht in der Liste der Einschränkungen enthalten sind, entweder true oder false zurückgeben.

  • Die Liste der Vektoren kann in einem beliebigen Format eingegeben werden. Wenn Sie möchten, können Sie anstelle des Vektors die Liste der wahren Positionen im Vektor eingeben. Also zum Beispiel, [TTF,TFT,FTT]oder [[T,T,F],[T,F,T],[F,T,T]]oder [[1,2],[1,3],[2,3]](Liste der wahren Positionen) sind alle in Ordnung.

  • Die Ausgabe kann in einem beliebigen gültigen Baumformat erfolgen. Zum Beispiel maj(maj(x1,x2,x3),x4,x5)funktioniert. Sie werden wahrscheinlich einzelne Zahlen als Stellvertreter für Variablen verwenden wollen, wie in [[1,2,3],4,5]. Reverse Polish 123m45mist zum Beispiel auch in Ordnung.

  • Wenn keine Funktion funktioniert, sollte Ihr Programm einen Fehler erzeugen oder einen falschen Wert ausgeben.

  • Wenn mehrere Funktionen funktionieren, kann Ihr Programm jede dieser Funktionen zurückgeben. Die Funktion muss nicht vereinfacht werden. Zum Beispiel maj(x1,x1,x2)oder x1sind gleichwertig.

Wertung

Das ist Codegolf: Kürzeste Lösung in Bytes gewinnt.

Testfälle:

Beachten Sie, dass es für jeden dieser Fälle viele mögliche Ausgaben gibt. Schreiben Sie daher ein Überprüfungsskript, das Ihre Ausgabe in eine Funktion konvertiert, und überprüfen Sie, ob Ihre Funktion für jeden der angegebenen Eingabevektoren true zurückgibt.

Input: 3, [TFF]
Output: 1 or [1,1,2] or [1,[1,2,2],[1,1,3]] or other equivalent

Input: 3, [TFF,FTF]
Output: Falsey or error (it's not possible)

Input: 3, [TTF,TFT]
Output: [1,2,3] or 1 or other equivalent

Input: 3, [TTF,TFT,FTT]
Output: [1,2,3] or [1,3,2] or other equivalent

Input: 4, [TTFF,TFTF,FFTT]
Output: Falsey or error

Input: 4, [TTTF,TTFT,TFTT,FTTT]
Output: [1, 2, 3] or [2,3,4], or many other options

Input: 5, [TTTFF,FTTFT,TFFFT]
Output: [1,[1,[1,2,5],[2,4,5]],3] or many other options 

Input: 6, [TTTFFF,FTFTTF,TFFTFT]
Output: [1, 2, 4] or [1, [1, 2, 4], [2, 3, 4]] or others

Input: 5, [TTTFF,TTFTF,TTFFT,TFTTF,TFTFT,TFFTT,FTTTF,FTTFT,FTFTT,FFTTT]
Output: [[1, [1, 3, 5], 4], [1, 2, [2, 4, 5]], [2, 3, [3, 4, 5]]] or others

Input: 7, [TTTTFFF,TTTFTFF,TTTFFTF,TTTFFFT,TTFTTFF,TTFTFTF,TTFTFFT,TTFFTTF,TTFFTFT,TTFFFTT,TFTTTFF,TFTTFTF,TFTTFFT,TFTFTTF,TFTFTFT,TFTFFTT,TFFTTTF,TFFTTFT,TFFTFTT,TFFFTTT,FTTTTFF,FTTTFTF,FTTTFFT,FTTFTTF,FTTFTFT,FTTFFTT,FTFTTTF,FTFTTFT,FTFTFTT,FTFFTTT,FFTTTTF,FFTTTFT,FFTTFTT,FFTFTTT,FFFTTTT]
Output: [[[1, [1, [1, 4, 7], 6], 5], [1, [1, 3, [3, 6, 7]], [3, 5, [5, 6, 7]]], [3, 4, [4, [4, 5, 7], 6]]], [[1, [1, [1, 4, 7], 6], 5], [1, 2, [2, [2, 5, 7], 6]], [2, [2, 4, [4, 6, 7]], [4, 5, [5, 6, 7]]]], [[2, [2, [2, 4, 7], 6], 5], [2, 3, [3, [3, 5, 7], 6]], [3, [3, 4, [4, 6, 7]], [4, 5, [5, 6, 7]]]]]
Kapuze
quelle
Die fünfstellige Zusammensetzung der Mehrheitsfunktionen ist (x1, x2, x3, x4, x5) => maj (x1, x2, maj (x3, x4, x5)) "wie? Was sollte die Antwort sein, wenn x1 = x2 = F; x3 = x4 = x5 = T; ?
TSH
Ich werde eine Wahrheitstabelle hinzufügen.
Hood
1
Was bedeutet eine Ausgabe von 1?
Mhmd
2
Vorgeschlagener Titel: Gerrymandering with logic gates
Robert Fraser
1
@trichoplax Nein, die Ausgabe aller verbleibenden Vektoren kann beliebig sein. Ich werde aktualisieren, um dies explizit zu machen.
Hood

Antworten:

2

JavaScript (ES6), 260 Byte

Nimmt Eingaben als Array von Arrays von Booleschen Werten. Gibt einen Baum von 1-indizierten Mehrheitsgattern zurück oder löst einen Rekursionsfehler (1) aus, wenn keine Lösung vorhanden ist.

Die Hauptfunktion f () versucht rekursiv, eine Lösung zu finden, indem sie den Löser F () aufruft und die maximale Verschachtelungsebene m bei jeder Iteration erhöht .

(1) Nach einer langen Zeit und unter der Annahme unendlichen Gedächtnisses

f=(a,m)=>(F=(a,d,I=a[i=0].map(_=>++i),g=(a,b)=>b[1]?b.reduce((s,i)=>s+g(a,i),0)>1:a[b-1])=>I.find(i=>a.every(a=>g(a,i)))||d&&(I.reduce((a,x)=>[...a,...a.map(y=>[...y,x])],[[]]).some(b=>r=b.length==3&&F(a.map(a=>[...a,g(a,b)]),d-1,[...I,b]))&&r))(a,m)||f(a,-~m)

Demo

Beispiel

Unten finden Sie eine Validierungstabelle der Lösung, die für den letzten Testfall der Demo gefunden wurde.

12345 | [5,[1,2,4],[3,4,[1,2,3]]]
------+-------------------------------------------------------------
TTTFF | [F,[T,T,F],[T,F,[T,T,T]]] --> [F,T,[T,F,T]] -> [F,T,T] --> T
TTFTF | [F,[T,T,T],[F,T,[T,T,F]]] --> [F,T,[F,T,T]] -> [F,T,T] --> T
TTFFT | [T,[T,T,F],[F,F,[T,T,F]]] --> [T,T,[F,F,T]] -> [T,T,F] --> T
TFTTF | [F,[T,F,T],[T,T,[T,F,T]]] --> [F,T,[T,T,T]] -> [F,T,T] --> T
TFTFT | [T,[T,F,F],[T,F,[T,F,T]]] --> [T,F,[T,F,T]] -> [T,F,T] --> T
TFFTT | [T,[T,F,T],[F,T,[T,F,F]]] --> [T,T,[F,T,F]] -> [T,T,F] --> T
FTTTF | [F,[F,T,T],[T,T,[F,T,T]]] --> [F,T,[T,T,T]] -> [F,T,T] --> T
FTTFT | [T,[F,T,F],[T,F,[F,T,T]]] --> [T,F,[T,F,T]] -> [T,F,T] --> T
FTFTT | [T,[F,T,T],[F,T,[F,T,F]]] --> [T,T,[F,T,F]] -> [T,T,F] --> T
FFTTT | [T,[F,F,T],[T,T,[F,F,T]]] --> [T,F,[T,T,F]] -> [T,F,T] --> T
Arnauld
quelle
Es gibt eine effiziente Lösung, die hoffentlich jemand findet. In der Zwischenzeit schätze ich, dass Brute Force funktioniert ...
Hood
1

Mathematica, 121 Bytes

Eine anonyme Funktion, deren zweites Argument eine Liste der Listen der wahren Positionen im Vektor der Booleschen Werte ist.

f[n_][s_]:=If[n<3,(Intersection@@s)[[1]],{#/. 2->1,#2/.{2->1,3->2},#3}&@@(1+f[n-1]/@(s-1/.{{0->1},{1->2,0->1},{0->2}}))]

Etwas schöner formatiert:

f[n_][s_] := If[n < 3, (Intersection @@s)[[1]],
   {# /. 2 -> 1, #2 /. {2 -> 1, 3 -> 2}, #3} & @@ 
    (1 + f[n - 1] /@ (s - 1 /. {{0 -> 1}, {1 -> 2, 0 -> 1}, {0 -> 2}}))]

Wenn weniger als drei Variablen vorhanden sind, schneiden Sie die Beschränkungsvektoren, um festzustellen, ob in allen Beschränkungen ein gemeinsames "Wahr" vorhanden ist. Wenn es eine gibt, funktioniert die Konstantenfunktion (x_1, x_2) -> x_i. Andernfalls ist dies nicht möglich (und es wird ein Fehler ausgegeben, wenn versucht wird, das erste Element einer leeren Liste zu übernehmen).

Andernfalls wird f1=f(x1,x1,x2,x3,,xn1) , f2=f(x1,x2,x2,x3,,xn1) und f3=f(x1,x2,x1,x3,,xn1)) , löse jedes von diesen rekursiv und setze dannf=maj(f1(x1,x3,x4,,xn),f2(x1,x2,x4,,xn),f2(x2,x3,x4,,xn)) .

Erläuterung:

Dies ist ein rekursiver Algorithmus, der das Problem der Lösung eines Problems mit n Variablen auf die Suche nach drei Lösungen für Probleme mit n1 Variablen reduziert . Die Schlüsselbeobachtung, die diese Arbeit ausmacht, ist, dass für f eine der Funktionen, die wir suchen, Folgendes gilt: f(x1,,xn)=maj(f(x1,x1,x3,x4,,xn),f(x1,x2,x2,),f(x3,x2,x3,))

x2x1x3x2x1x3

f(x1,x1,x3,x4,,xn)f(x1,x2,x2,x4,,xn)f(x3,x2,x3,x4,,xn))

Warum ist das so? Nun, die Majoritätsfunktion erfüllt zwei Eigenschaften:

  1. !xxmaj(!x,!y,!z)=!maj(x,y,z)

  2. maj(x,y,False)maj(x,y,True)FalseTrue(x1,,xn)(y1,,yn)xiyiif(x1,xn)(y1,,yn)f(x1,xn)f(y1,,yn). Die Zusammensetzung der monotonen Funktionen ist monoton, so dass jede Funktion, die wir aus der Mehrheitsfunktion aufbauen können, monoton ist.

Es stellt sich heraus, dass komplementäre monotone Funktionen genau die Klasse von Funktionen sind, die aus Mehrheitsgattern aufgebaut werden können.

ff(x1,,xn)=maj(f(x1,x1,x3,x4,,xn),f(x1,x2,x2,x4,,xn),f(x3,x2,x3,x4,,xn))

f1(x1,x2,x3,,xn)=f(x1,x1,x3,x4,,xn)f2(x1,,xn)=f(x1,x2,x2,x4,,xn)f3(x1,,xn)=f(x3,x2,x3,x4,,xn)f=maj(f1,f2,f3)f1f2f3fx1x2x3x1=x2=x3f1=f2=f3=f

x1x2x3fx1=x2 and x3 is different and because f is complementary, it suffices to deal with the case x1=x2=False and x3=True. In this case, (x1,x1,x3)=(False,False,True)=(x1,x2,x3), (x1,x2,x2)=(False,False,False)(x1,x2,x3) and (x3,x2,x3)=(True,False,True)(x1,x2,x3). By monotonicity we deduce that f2f1=ff3. If f=False then f2False implies f2=False=f and if f=True then f3True implies f3=True. Thus, at least two of f1, f2, and f3 are equal to f in all cases so f=maj(f1,f2,f3).

Hood
quelle