Funkcja większości jest funkcją logiczną, która pobiera trzy dane logiczne i zwraca najczęściej. Na przykład jeśli maj(x,y,z)jest funkcją większości i Toznacza prawdę, a Ffałsz, to:

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

To pytanie dotyczy pisania funkcji boolowskich jako kompozycji funkcji większościowych. Przykład 5-arylowej kompozycji funkcji większościowych to (x1,x2,x3,x4,x5) => maj(x1,x2,maj(x3,x4,x5)). Ta funkcja zwraca następujące dane wyjściowe dla tych przykładowych wektorów wejściowych:

(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

Zadanie

Napisz program, który wprowadza dodatnią liczbę całkowitą n oraz listę długości n wektorów boolean i wypisuje drzewo bramek większości, które zwraca wartość true dla wszystkich podanych wektorów, jeśli to możliwe. Funkcja może zwracać wartość true lub false w wektorach, które nie znajdują się na liście ograniczeń.

• Lista wektorów może być wprowadzana w dowolnym formacie. Jeśli wolisz, zamiast wprowadzania wektora, możesz wprowadzić listę prawdziwych pozycji w wektorze. Na przykład, [TTF,TFT,FTT]lub [[T,T,F],[T,F,T],[F,T,T]]lub [[1,2],[1,3],[2,3]](lista prawdziwych pozycji) są w porządku.

• Dane wyjściowe mogą być dowolnym poprawnym formatem drzewa. Na przykład,maj(maj(x1,x2,x3),x4,x5) działa. Prawdopodobnie będziesz chciał użyć pojedynczych liczb jako stand-ins dla zmiennych, jak w [[1,2,3],4,5]. Na przykład polerowanie wsteczne 123m45mjest również w porządku.

• Jeśli żadna funkcja nie działa, twój program powinien wygenerować błąd lub wygenerować wartość falsey.

• Jeśli działa wiele funkcji, Twój program może zwrócić dowolną z nich. Funkcja nie musi być uproszczona. Na przykład maj(x1,x1,x2)lubx1 są równoważne.

Punktacja

To jest kod golfowy: wygrywa najkrótsze rozwiązanie w bajtach.

Przypadki testowe:

Zauważ, że istnieje wiele możliwych danych wyjściowych dla każdego z tych przypadków, dlatego powinieneś napisać skrypt sprawdzający, który konwertuje dane wyjściowe na funkcję i sprawdź, czy funkcja zwraca wartość true dla każdego z określonych wektorów wejściowych.

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]]]]]

JavaScript (ES6), 260 bajtów

Pobiera dane wejściowe jako tablicę tablic booleanów. Zwraca drzewo bramek 1-indeksowanej większości lub zgłasza błąd rekurencji ^(1), jeśli nie ma rozwiązania.

Główna funkcja f () rekurencyjnie próbuje znaleźć rozwiązanie, wywołując solver F () i zwiększając maksymalny poziom zagnieżdżenia m przy każdej iteracji.

_{(1) po długim czasie i przy założeniu nieskończonej pamięci}

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)

Próbny

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)

test = a => console.log(JSON.stringify(f(a.split(',').map(s => [...s].map(c => c == 'T')))))

test('TFF')
test('TTF,TFT')
test('TTF,TFT,FTT')
test('TTTF,TTFT,TFTT,FTTT')
test('TTTFF,FTTFT,TFFFT')
test('TTTFFF,FTFTTF,TFFTFT')
test('TTTFF,TTFTF,TTFFT,TFTTF,TFTFT,TFFTT,FTTTF,FTTFT,FTFTT,FFTTT')

Przykład

Poniżej znajduje się tabela sprawdzania poprawności rozwiązania znalezionego dla ostatniego przypadku testowego wersji demonstracyjnej.

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

Mathematica, 121 bajtów

Anonimowa funkcja, która bierze swój drugi argument jako listę list prawdziwych pozycji w wektorze wartości logicznych.

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

Sformatowane nieco ładniej:

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

$\def\maj{\mathrm{maj}}\def\T{\mathrm{True}}\def\F{\mathrm{False}}$ Jeśli jest mniej niż trzy zmienne, przecinaj wektory ograniczenia, aby sprawdzić, czy we wszystkich ograniczeniach występuje wspólna „prawda”. Jeśli istnieje, to funkcja stała (x_1, x_2) -> x_i działa, w przeciwnym razie jest to niemożliwe (i zgłasza błąd, próbując pobrać pierwszy element z pustej listy).

W przeciwnym razie zastąp $f_1=f(x_1,x_1,x_2,x_3,\ldots,x_{n-1})$ , $f_2=f(x_1,x_2,x_2,x_3,\ldots,x_{n-1})$ oraz $f_3=f(x_1,x_2,x_1,x_3,\ldots,x_{n-1}))$ , rozwiąż rekurencyjnie każdy z nich, a następnie ustaw$f=\maj(f_1(x_1,x_3,x_4,\ldots,x_n), f_2(x_1,x_2,x_4,\ldots,x_n),f_2(x_2,x_3,x_4,\ldots,x_n))$ .

Wyjaśnienie:

Jest to algorytm rekurencyjny, który ogranicza problem znalezienia rozwiązania problemu zmiennej $n$ do znalezienia trzech rozwiązań problemów zmiennej $n-1$ . Kluczem obserwacja sprawia, że tej pracy jest to, że dla $f$ jedna z funkcji szukamy mamy: $f(x_1,\ldots,x_n)=\maj(f(x_1,x_1,x_3,x_4,\ldots,x_n),f(x_1,x_2,x_2,\ldots),f(x_3,x_2,x_3,\ldots))$

W pierwszej pozycji wymieniliśmy $x_2$ o$x_1$ , w drugim położeniu$x_3$ z$x_2$ , w trzeciej pozycji$x_1$ z$x_3$ .

Gdy poznasz tę tożsamość, algorytm jest jasny: gdy istnieją dwie lub mniej zmiennych, problem jest trywialny. W przeciwnym razie rekurencyjnie rozwiąż trzy problemy reprezentowania $f(x_1,x_1,x_3,x_4,\ldots,x_n)$ , $f(x_1,x_2,x_2,x_4,\ldots,x_n)$ i $f(x_3,x_2,x_3,x_4,\ldots,x_n))$i weź większość z nich.

Dlaczego to prawda? Cóż, funkcja większości spełnia dwie właściwości:

1. Jest „komplementarny”. To znaczy, jeśli $!x$ jest negacja $x$ , a $\maj(!x,!y,!z)=!\maj(x,y,z)$ . W konsekwencji każda funkcja, którą możemy zbudować z funkcji większości, jest komplementarna.

2. Jest monotoniczny. To znaczy, $\maj(x,y,\F)\leq \maj(x,y,\T)$ . Ogólnie rzecz biorąc, jeśli powiemy, że $\F\leq \T$ i powiedzmy $(x_1,\ldots,x_n)\leq (y_1,\ldots, y_n)$ jeśli$x_i\leq y_i$ dla wszystkich$i$ , to mówię, że funkcja$f$ jest monotoniczna jeśli$(x_1,\ldots x_n)\leq(y_1,\ldots, y_n)$ implikuje$f(x_1,\ldots x_n)\leq f(y_1,\ldots, y_n)$. Skład funkcji monotonicznych jest monotoniczny, więc każda funkcja, którą możemy zbudować z funkcji większości, jest monotoniczna.

Okazuje się, że uzupełniające się funkcje monotoniczne są dokładnie klasą funkcji, które można zbudować z bram większości.

$f$$f(x_1,\ldots,x_n)=\maj(f(x_1,x_1,x_3,x_4,\ldots,x_n),f(x_1,x_2,x_2,x_4,\ldots,x_n),f(x_3,x_2,x_3,x_4,\ldots,x_n))$

Let's set $f_1(x_1,x_2,x_3,\ldots,x_n)=f(x_1,x_1,x_3,x_4,\ldots,x_n)$, $f_2(x_1,\ldots,x_n)=f(x_1,x_2,x_2,x_4,\ldots,x_n)$ and $f_3(x_1,\ldots,x_n)=f(x_3,x_2,x_3,x_4,\ldots,x_n)$. To show that $f=\maj(f_1,f_2,f_3)$, we need to show that for any input, at least two of $f_1$, $f_2$, and $f_3$ are equal to $f$. We divide up into cases based on the values of $x_1$, $x_2$ and $x_3$. If $x_1=x_2=x_3$ then $f_1=f_2=f_3=f$.

Suppose not all of $x_1$, $x_2$, and $x_3$ are the same. By permuting the variables of $f$, we can assume that $x_1=x_2$ and $x_3$ is different and because $f$ is complementary, it suffices to deal with the case $x_1=x_2=\F$ and $x_3=\T$. In this case, $(x_1,x_1,x_3)=(\F,\F,\T)=(x_1,x_2,x_3)$, $(x_1,x_2,x_2)=(\F,\F,\F)\leq (x_1,x_2,x_3)$ and $(x_3,x_2,x_3)=(\T, \F, \T) \geq (x_1,x_2,x_3)$. By monotonicity we deduce that $f_2\leq f_1=f\leq f_3$. If $f=\F$ then $f_2\leq \F$ implies $f_2=\F=f$ and if $f=\T$ then $f_3\geq \T$ implies $f_3=\T$. Thus, at least two of $f_1$, $f_2$, and $f_3$ are equal to $f$ in all cases so $f=\maj(f_1,f_2,f_3)$.