Golf a bijection \ $\mathbb{N}^n\to\mathbb{N}\$
Twoim zadaniem jest napisanie programu, który implementuje bijection \$\mathbb{N}^n\to\mathbb{N}\$dla \$n \ge 1\$. Twój program powinien zająć \$n\$liczby naturalne jako dane wejściowe, w dowolnej akceptowalnej metodzie (w tym biorąc je jako pojedyncze, \$n\$ lista elementów / tablica) i wyprowadzić unikalną liczbę naturalną dla wszystkich możliwych danych wejściowych.
Mówiąc prościej, bijekcja \$\mathbb{N}^n\to\mathbb{N}\$ znaczy:
- Weź \$n\$ liczby naturalne jako dane wejściowe
- Zmapuj te \$n\$ liczby naturalne na pojedynczą liczbę naturalną
- Dla każdego możliwego wejścia wyjście jest niepowtarzalne
- Dla każdego możliwego wyjścia istnieje wejście, które da to wyjście
Na przykład funkcja parowania Cantora \$\pi : \mathbb{N}^2\to\mathbb{N}\$ jest bijekcją, która przyjmuje dwie liczby naturalne i odwzorowuje każdą parę na unikalną liczbę naturalną.
Możesz zaimplementować dowolną funkcję bijektywną, o ile zostanie udowodnione, że jest ona bijektywna dla wszystkich możliwych danych wejściowych. Prosimy o dołączenie tego dowodu (bezpośrednio lub poprzez łącze) do odpowiedzi. To jest code-golf, więc wygrywa najkrótszy kod w bajtach.
Możesz zdecydować, czy chcesz użyć \$\mathbb{N} = \{1, 2, 3, \dots\}\$lub \$\mathbb{N} = \{0, 1, 2, \dots\}\$, o ile jest to spójne dla wszystkich \$n\$.
Odpowiedzi
APL (Dyalog Unicode) , 13 10 bajtów
(⊢+1⊥∘⍳+)/
Wypróbuj online!
Podobnie jak w przypadku innych odpowiedzi, ponieważ parowanie Cantora jest bijektywne, kompozycja \$n-1\$ Pary Cantor są również bijektywne.
( )/ ⍝ reduce the input with following function
+ ⍝ left argument + right argument
⍳ ⍝ the first left+right positive integers
1⊥ ⍝ convert those from base 1 (sum)
⊢+ ⍝ + right argument
J , 8 bajtów
,@|:&.#:
Wypróbuj online! (wyświetla macierz 10x10 dla f (A, B) i kilka kolejnych liczb dla n = 3.)
Zasadniczo wykorzystuje początkowy pomysł Neila, przeplatając bity poprzez ich równomierne rozłożenie (więc dla n = 3, maska bitowa wyjścia to … 1 2 3 1 2 3 1 2 3.). Ale zamiast przesuwania bitów, możemy skorzystać z kształtów: Konwersja każdego numeru do podstawy 2 i list pad z zerami, fe #: 2 3 8jest
0 0 1 0
0 0 1 1
1 0 0 0
Transponuj macierz za pomocą |::
0 0 1
0 0 0
1 1 0
0 1 0
I „deshape” za pomocą ,, czyli połącz wiersze w listę: 0 0 1 0 0 0 1 1 0 0 1 0i zamień ją z powrotem z podstawy 2 &.#:na liczbę: 562.
Galaretka , 6 bajtów
Prawdopodobnie caird's 6 byter ...
+RS+ʋ/
Wypróbuj online!
W jaki sposób?
Implementuje wielokrotne zastosowanie funkcji parowania Cantora.
Pojedyncza aplikacja to \$f(a,b)=\frac{1}{2}(a+b)(a+b+1)+b\$
Ale pamiętaj, że \$\frac{1}{2}(a+b)(a+b+1)=\sum_{i=1}^{a+b}i\$
Więc \$f(a,b)=b+\sum_{i=1}^{a+b}i\$
+RS+ʋ/ - Link: list of non-negative integers
/ - reduce by:
ʋ - last four links as a dyad - f(a,b)
+ - add -> a+b
R - range -> [1,2,3,...,a+b]
S - sum -> (a+b)(a+b+1)/2
+ - add (b) -> b+(a+b)(a+b+1)/2
Python 2 , 38 bajtów
f=lambda a,*l:l and(a-~a<<f(*l))-1or a
Wypróbuj online!
Przyjmuje dane wejściowe jak f(1,2,3).
Wykorzystuje funkcję parowania \$p(a,b)=(2a+1)2^b\$. Używamy przesunięcia bitowego, <<baby skrócić *2**bi piszemy, a-~aaby zaoszczędzić bajt 2*a+1.
41 bajtów
lambda l:reduce(lambda a,b:(a-~a<<b)-1,l)
Wypróbuj online!
Węgiel drzewny , 21 18 bajtów
Ｗ⊖Ｌθ⊞θ⊖×⊕⊗⊟θＸ²⊟θＩθ
Wypróbuj online! Teraz używa funkcji parowania @ xnor. Poprzednia 21-bajtowa odpowiedź:
Ｗ⊖Ｌθ⊞θΣＥ²×⊕κ↨↨⊟貦⁴Ｉθ
Wypróbuj online! Link prowadzi do pełnej wersji kodu. Wyjaśnienie:
Ｗ⊖Ｌθ
Powtarzaj, aż pozostanie tylko jeden element (tj. Zmniejsz w prawo) ...
⊞θΣＥ²×⊕κ↨↨⊟貦⁴
Zamień ostatnie dwa elementy na podstawę 2, a następnie z powrotem z podstawy 4, podwoj jeden z nich i weź sumę, wypychając wynik z powrotem na listę. Jest to równoważne przeplataniu ich bitów. Używam tego bijekcji zamiast funkcji parowania Cantora, ponieważ wymaga ona odczytania każdej wartości tylko raz, dzięki czemu jest bardziej golfowa w Charcoal.
Ｉθ
Podaj wynik końcowy.
Haskell , 27 bajtów
foldr1(\a b->2^a*(2*b+1)-1)
Wypróbuj online!
Używa innego typu bijekcji niż funkcja parowania Cantora. Każdą dodatnią liczbę całkowitą można jednoznacznie podzielić na potęgę 2 razy liczbę nieparzystą, czyli \$2^a(2b+1)\$dla nieujemnych liczb całkowitych \$a,b\$. Odejmowanie 1 oznacza, że otrzymujemy wszystkie nieujemne liczby całkowite, w tym 0.
Oto tabela bijekcji dla \$a,b\$ od 0 do 6:
0 2 4 6 8 10 12 ...
1 5 9 13 17 21 25
3 11 19 27 35 43 51
7 23 39 55 71 87 103
15 47 79 111 143 175 207
31 95 159 223 287 351 415
63 191 319 447 575 703 831
... ...
Galaretka , 7 bajtów
+‘c2+µ/
Wypróbuj online!
0 to liczba naturalna.
Implementuje parowanie Cantora i redukuje listę.
(Najwyraźniej jest 6-bajtowe rozwiązanie, więc jestem smutny)
Parowanie Cantora jest bijektywne (nie jestem pewien dowodu, ale myślę, że jest to dobrze znane), więc ponieważ kompozycje bijektywne są bijektywne, jest to bijektywne. W skrajnym przypadku, gdy n = 1, to jest tożsamość, więc nadal jest bijektywna.
Przynajmniej tak myślę, że to działa. Daj mi znać, jeśli znajdziesz niezamapowaną wartość lub kolizję.
JavaScript (ES6), 33 bajty
Parowanie Cantora w tablicy wejściowej a[].
a=>a.reduce((x,y)=>y-(x+=y)*~x/2)
Wypróbuj online!
05AB1E , 10 9 bajtów
Å«+LOy+}н
Wypróbuj online lub zweryfikuj wszystkie przypadki testowe .
Port odpowiedzi APL @ovs , więc nie zapomnij go zagłosować!
-1 bajt dzięki @ovs .
Alternatywa 9 bajtów :
ćsvy+LOy+
Wypróbuj online lub sprawdź więcej przypadków testowych .
Wyjaśnienie:
Å« # Cumulative right-reduce by (unfortunately keeping all intermediate steps):
+ # Add them together: a+b
L # Pop and push a list in the range [a+b]
O # Sum this list
y+ # Add a to it
}н # After the reduce-by, pop the list and leave just the first item
# (after which it is output implicitly as result)
ć # Extract head of the (implicit) input-list; pushing the remainder-list
# and first item separated to the stack
s # Swap so the remainder-list is at the top
v # Loop over each integer `y` in this list:
y+ # Add the current integer `y` to the top value
L # Pop and push a list in the range [1,n]
O # Sum this list
y+ # And add `y` to it
# (after the loop, the integer is output implicitly as result)
Haskell, 31 bajtów
foldl1(\x y->(x+y)*(x+y+1)/2+y)
Wypróbuj online!
Scala, 34 bajty
_.reduce((x,y)=>(x+y)*(x+y+1)/2+y)
Wypróbuj online
Anonimowa funkcja typu Seq[Int] => Int. Stosuje parowanie kantorów do dwóch elementów, aż wynikiem będzie pojedyncza liczba całkowita.
C (gcc) , 62 \$\cdots\$ 56 55 bajtów
Zapisano bajt dzięki Ceilingcat !!!
f(a,l)int*a;{l=l?*++a=*a-(*a+=a[1])*~*a/2,f(a,l-1):*a;}
Wypróbuj online!
Wprowadza tablicę liczb naturalnych i jej długość minus \$1\$i zwraca unikalną liczbę naturalną przy użyciu parowania Cantora .
Łuska , 7 bajtów
FS+ȯΣḣ+
Wypróbuj online!
Rekurencyjne parowanie Cantora (to samo podejście, co odpowiedź HyperNeutrino ).
FS+ȯΣḣ+
F # Fold over list (=recursively apply to pairs):
S+ȯΣḣ+ # Cantor-pairing bijection:
S # Hook: combine 2 functions using same (first) argument
+ # add first argument to
ȯ # combination of 2 3 functions:
Σ # sum of
ḣ # series from 1 up to
+ # sum of first & second arguments
Retina , 59 bajtów
.+
*
+`(_+)\1
$1@ @_ _ ^'@P`.+ N$`.
$.%`
¶
_
@_
+`_@
@__
_
Wypróbuj online! Wyjaśnienie:
.+
*
+`(_+)\1
$1@
@_
_
Konwertuj dane wejściowe na binarne, używając @for 0i _for 1.
^'@P`.+
W lewo wszystkie linie o @tej samej długości.
N$`. $.%`
¶
Transponuj i połącz linie.
_
@_
+`_@
@__
_
Konwertuj z dwójkowego na dziesiętny.