Liczba głosów , którą nazwiemy B , to liczba sposobów na uporządkowanie liczb od 1 do B (B + 1) / 2 w trójkąt, tak aby każdy rząd i kolumna były w dowolnej kolejności. Pierwsze cztery numery głosowania to:

a(0) = 1
a(1) = 1
a(2) = 1
a(3) = 2

a(3)wynosi 2, co oznacza, że ​​istnieją 2 sposoby ułożenia liczb od 1 do 3(3+1)/2 = 6w takim trójkącie:

1          1
2 3    or  2 4
4 5 6      3 5 6

Aby uzyskać więcej informacji, zobacz wpis sekwencji OEIS .

Twoim wyzwaniem, biorąc pod uwagę trójkąt do głosowania, jest sprawdzenie jego poprawności. Jeśli spełnia warunki trójkąta do głosowania (liczba wierszy i kolumn rośnie), należy wypisać, ile innych sposobów (wyłączając ten na wejściu), można poprawnie ustawić trójkąt. Jeśli trójkąt wejściowy jest niepoprawnie skonstruowany, nie powinieneś nic generować.

Końcowe znaki nowej linii są dozwolone.

Wejście

Trójkąt liczb, który może, ale nie musi, być ważnym trójkątem do głosowania. Na przykład:

1
2 3
4 5 6

1
10 5 
9 8 2
7 6 4 3

1
3 2

9
2 11
14 3 5
12 8 1 7
15 13 10 4 6

1
2 3
4 5 6
7 8 9 10
11 12 13 14 15
16 17 18 19 20 21

Wynik

Jeśli dane wejściowe to prawidłowy trójkąt do głosowania, pozostała liczba sposobów na ułożenie tych samych liczb w ważnym trójkącie do głosowania. Jeśli dane wejściowe nie są prawidłowym trójkątem do głosowania, nic. Na przykład powyższe dane wejściowe generują te dane wyjściowe ( <nothing>jest symbolem zastępczym dla rzeczywistej pustej produkcji):

1                     # the same as a(3)-1

<nothing>

<nothing>

<nothing>

33591                 # the same as a(6)-1

Punktacja

To jest golf golfowy : jak zwykle wygrywa najmniej bajtów. Tiebreaker jest najwcześniej opublikowany.

Galaretka , 20 bajtów

;Zµ⁼Ṣ€
ẋÇFŒ!ṁ€⁸ÇÐfL’

W przypadku prawidłowych trójkątów głosowania czas działania i użycie pamięci wynoszą co najmniej O (n!) , Gdzie n jest liczbą wpisów w trójkącie. Nieprawidłowe są rozpoznawane przez awarię, a więc nic nie drukują.

Wypróbuj online!

Testowe uruchomienie

Lokalnie udało mi się sprawdzić, czy a (4) jest obliczone poprawnie.

$ time jelly eun ';Zµ⁼Ṣ€¶ẋÇFŒ!ṁ€⁸ÇÐfL’' '[1],[2,3],[4,5,6],[7,8,9,10]'
11

real    6m9.829s
user    6m7.930s
sys     0m2.579s

Jak to działa

;Zµ⁼Ṣ€         Helper link. Argument: T (triangular array)

 Z             Zip/transpose T.
;              Concatenate the original and the transposed copy.
  µ            Begin a new monadic chain, with the previous result (R) as argument.
    Ṣ€         Sort each array in R.
   ⁼           Test for equality with R.
               This returns 1 if T is a ballot triangle, 0 if not.

ẋÇFŒ!ṁ€⁸ÇÐfL’  Main link. Argument: A (triangular array)

 Ç             Call the helper link with argument A.
ẋ              Repeat A that many times.
               This yields an empty array if A is not a ballot triangle.
  F            Flatten the result.
   Œ!          Generate all permutations of the digits of A.
     ṁ€⁸       Mold each permutation like A, i.e., give it triangular form.
               This crashes if permutation array is empty.
        ÇÐf    Filter; keep permutations for which the helper link returns 1.
           L’  Compute the length and decrement it.

Brachylog , 44 bajty

{:{o?}a,?z:2a},?ly+yb:3flw
p~c.:laBtybB,.:1&

Wypróbuj online!

Działa to w czasie podwójnie wykładniczym, więc w przypadku prawdziwych przypadków testowych trzeba by mi uwierzyć, że teoretycznie daje poprawny wynik, dla trójkątów o długości większej lub równej 3.

Nadal możesz testować przypadki testowe falsey, które powinny zakończyć się dość szybko.

JavaScript (ES6), 143 bajty

a=>a.some((b,i)=>b.some((c,j)=>c<b[j-1]||i&&c<a[i-1][j]))?'':(f=n=>n<2||n*f(n-1),g=(n,m=f(n*n+n>>1))=>n<2?m:g(--n,m*f(n)/f(n+n+1)),g(a.length))

Przeszukuje trójkąt w celu znalezienia nieprawidłowego wpisu, a następnie używa rekursywnego sformułowania formuły w OEIS do obliczenia wyniku.