Trywialnie możliwe jest utworzenie funkcji bijectywnej z (zestawu wszystkich liczb całkowitych) do (np. Funkcja tożsamości).$\mathbb{Z}$$\mathbb{Z}$

Jest także możliwe, aby utworzyć bijective funkcję z na (zbiorem wszystkich par 2 całkowitymi, a iloczyn z i ). Na przykład możemy wziąć sieć reprezentującą punkty całkowite na płaszczyźnie 2D, narysować spiralę od 0 na zewnątrz, a następnie zakodować pary liczb całkowitych jako odległość wzdłuż spirali, gdy przecina ona ten punkt.Z 2 Z $\mathbb{Z}$$\mathbb{Z}^2$$\mathbb{Z}$$\mathbb{Z}$

(Funkcja, która robi to z liczbami naturalnymi, jest znana jako funkcja parowania .)

W rzeczywistości istnieje rodzina tych bijectywnych funkcji:

Wyzwanie

Zdefiniuj rodzinę funkcji (gdzie jest dodatnią liczbą całkowitą) za pomocą właściwości, która biotycznie odwzorowuje liczby całkowite na -liczby całkowite.k f k ( x ) $f_k(x)$$k$$f_k(x)$$k$

Twoje zgłoszenie powinno przy danych wejściowych i zwrócić .x f k ( x $k$$x$$f_k(x)$

To jest golf golfowy , więc wygrywa najkrótsza ważna odpowiedź (mierzona w bajtach).

Dane techniczne

• Można dowolnej rodziny o ile spełnia powyższe kryteria.$f_k(x)$
• Zachęcamy do dodania opisu działania rodziny funkcji, a także fragmentu do obliczenia odwrotności funkcji (nie jest to uwzględnione w liczbie bajtów).
• Jest w porządku, jeśli funkcja odwrotna jest niepoliczalna, o ile można udowodnić, że funkcja jest bijectywna.
• Możesz użyć dowolnej odpowiedniej reprezentacji dla liczb całkowitych ze znakiem i list liczb całkowitych ze znakiem dla swojego języka, ale musisz zezwolić, aby dane wejściowe do funkcji były nieograniczone.
• Musisz tylko obsługiwać wartości od do 127.$k$

Alice , 14 12 bajtów

/O
\i@/t&Yd&

Wypróbuj online!

Funkcja odwrotna (nie golfowa):

/o     Q
\i@/~~\ /dt&Z

Wypróbuj online!

Wyjaśnienie

Alice ma wbudowany bijection między ℤ i ℤ ² , który można obliczyć za pomocą Y(rozpakuj) i jego odwrotność Z (spakuj). Oto fragment dokumentów wyjaśniających bijection:

Szczegóły bijectcji są prawdopodobnie nieistotne w większości przypadków użycia. Najważniejsze jest to, że pozwala to użytkownikowi zakodować dwie liczby całkowite w jednym i wyodrębnić później dwie liczby całkowite. Przez wielokrotne stosowanie polecenia pack całe listy lub drzewa liczb całkowitych mogą być przechowywane w jednym numerze (choć nie w sposób szczególnie wydajny pod względem pamięci). Odwzorowanie obliczone przez operację spakowania jest funkcją bijectywną ℤ ² → ℤ (tj. Mapowanie jeden na jeden). Po pierwsze, liczby całkowite {..., -2, -1, 0, 1, 2, ...} są mapowane na liczby naturalne (w tym zero), takie jak {..., 3, 1, 0, 2, 4 , ...}(innymi słowy, ujemne liczby całkowite są odwzorowane na nieparzyste liczby naturalne, a nieujemne liczby całkowite są odwzorowane na liczby parzyste). Dwie liczby naturalne są następnie mapowane na jedną za pomocą funkcji parowania Cantora , która zapisuje liczby naturalne wzdłuż przekątnych pierwszej ćwiartki siatki liczb całkowitych. W szczególności {(0,0), (1,0), (0,1), (2,0), (1,1), (0,2), (3,0), ...} są odwzorowany na {0, 1, 2, 3, 4, 5, 6, ...} . Wynikowa liczba naturalna jest następnie odwzorowywana z powrotem na liczby całkowite przy użyciu odwrotności wcześniejszego bjectu. Polecenie rozpakuj oblicza dokładnie odwrotność tego odwzorowania.

Jak wspomniano powyżej, możemy użyć tej operacji rozpakowania również do mapowania ℤ do ℤ ^k . Po zastosowaniu go do początkowej liczby całkowitej możemy ponownie rozpakować drugą liczbę całkowitą wyniku, co daje nam listę trzech liczb całkowitych. W rezultacie aplikacje k-1Y dają nam k liczb całkowitych.

Możemy obliczyć odwrotność, pakując listę Zod końca.

Sam program ma następującą strukturę:

/O
\i@/...d&

Jest to tylko podstawowy szablon dla programu, który odczytuje zmienną liczbę liczb całkowitych dziesiętnych jako dane wejściowe i drukuje zmienną liczbę jako wynik. Tak więc rzeczywisty kod jest po prostu:

t   Decrement k.
&   Repeat the next command k-1 times.
Y   Unpack.

Jedną z rzeczy, o których chciałbym się odnieść, jest „dlaczego Alice miałaby wbudowaną funkcję bijectji ℤ → ℤ ² , czy to nie terytorium golfa”? Podobnie jak w przypadku większości dziwniejszych wbudowanych Alice, głównym powodem jest zasada projektowa Alice, że każde polecenie ma dwa znaczenia, jedno dla trybu Kardynał (liczba całkowita) i jedno dla Tryb porządkowy (łańcuch), a te dwa znaczenia powinny być w jakiś sposób powiązane z podaniem Tryb kardynalny i porządkowy daje poczucie, że są lustrzanymi wszechświatami, w których rzeczy są w pewnym sensie takie same, ale także różne. I dość często miałem polecenie dla jednego z dwóch trybów, które chciałem dodać, a następnie musiałem dowiedzieć się, z jakim innym poleceniem je sparować.

W przypadku Yi Ztrybie porządkową było pierwsze: Chciałem mieć funkcję do przeplatania dwóch ciągów (zip) i oddzielić je ponownie (Rozpakuj). Jakość tego, co chciałem uchwycić w trybie kardynalnym, polegało na utworzeniu jednej liczby całkowitej z dwóch i możliwości późniejszego wyodrębnienia dwóch liczb całkowitych, co sprawia, że ​​taki bijection jest naturalnym wyborem.

Doszedłem również do wniosku, że byłoby to bardzo przydatne poza golfem, ponieważ pozwala przechowywać całą listę, a nawet drzewo liczb całkowitych w jednej jednostce pamięci (element stosu, komórka taśmy lub komórka siatki).

Python, 96 93 bajtów

def f(k,x):
 c=[0]*k;i=0
 while x:v=(x+1)%3-1;x=x//3+(v<0);c[i%k]+=v*3**(i//k);i+=1
 return c

Działa to w zasadzie poprzez konwersję liczby wejściowej xna zbalansowane trójskładnikowe , a następnie rozłożenie najmniej znaczących tritów (cyfr trójskładnikowych) najpierw między różnymi współrzędnymi w sposób okrągły. Tak na k=2przykład, każdy nawet umieszczone trit przyczyniłoby się do xkoordynowania i każdy nieparzysty pozycjonowane trit przyczyniłoby się do ywspółrzędnych. Gdyż k=3mielibyście pierwszy, czwarty i siódmy trit (itd.) Przyczyniający się do x, podczas gdy drugi, piąty i ósmy przyczyniają się do y, a trzeci, szósty i dziewiąty przyczyniają się do z.

Na przykład za pomocą k=2, spójrzmy na x=35. W zbalansowanym trójskładniku, 35jest 110T(używając notacji artykułu z Wikipedii, gdzie Treprezentuje -1cyfrę). Dzielenie trits daje 1T(pierwsza i trzecia trits, licząc od prawej) dla xwspółrzędnej i 10(druga i czwarta trit) dla ywspółrzędnej. Przekształcamy każdą współrzędną z powrotem na dziesiętną, otrzymujemy 2, 3.

Oczywiście nie przekształcam jednocześnie całej liczby na zbalansowane trójskładnikowe w kodzie golfowym. Obliczam tylko jeden tryt na raz (w vzmiennej) i dodam jego wartość bezpośrednio do odpowiedniej współrzędnej.

Oto nieodwrócona funkcja odwrotna, która pobiera listę współrzędnych i zwraca liczbę:

def inverse_f(coords):
    x = 0
    i = 0
    while any(coords):
        v = (coords[i%3]+1) % 3 - 1
        coords[i%3] = coords[i%3] // 3 + (v==-1)
        x += v * 3**i
        i += 1
    return x

Moja ffunkcja jest chyba godna uwagi ze względu na swoją wydajność. Wykorzystuje tylko O(k)pamięć i O(k) + O(log(x))znalezienie czasu zajmuje dużo czasu, dzięki czemu może pracować z bardzo dużymi wartościami wejściowymi. Spróbuj f(10000, 10**10000)na przykład, a otrzymasz odpowiedź niemal natychmiast (dodanie dodatkowego zera do wykładnika wykładziny, więc xzajmuje 10**100000to około 30 sekund na moim starym komputerze). Funkcja odwrotna nie jest tak szybka, głównie dlatego, że trudno jest powiedzieć, kiedy jest wykonywana (skanuje wszystkie współrzędne po każdej zmianie, więc zajmuje to trochę O(k*log(x))czasu). Prawdopodobnie można go zoptymalizować, aby był szybszy, ale prawdopodobnie jest już wystarczająco szybki dla normalnych parametrów.

Łuska , 10 bajtów

§~!oΠR€Θݱ

Wypróbuj online!

Funkcja odwrotna ma również 10 bajtów.

§o!ȯ€ΠRΘݱ

Wypróbuj online!

Wyjaśnienie

Kierunek do przodu:

§~!oΠR€Θݱ  Implicit inputs, say k=3 and x=-48
        ݱ  The infinite list [1,-1,2,-2,3,-3,4,-4,..
       Θ    Prepend 0: [0,1,-1,2,-2,3,-3,4,-4,..
 ~    €     Index of x in this sequence: 97
§    R      Repeat the sequence k times: [[0,1,-1,..],[0,1,-1,..],[0,1,-1,..]]
   oΠ       Cartesian product: [[0,0,0],[1,0,0],[0,1,0],[1,1,0],[-1,0,0],[0,0,1],..
  !         Index into this list using the index computed from x: [-6,1,0]

Odwrotny kierunek:

§o!ȯ€ΠRΘݱ  Implicit inputs, say k=3 and y=[-6,1,0]
     ΠRΘݱ  As above, k-wise Cartesian product of [0,1,-1,2,-2,..
   ȯ€       Index of y in this sequence: 97
§o!         Index into the sequence [0,1,-1,2,-2,.. : -48

Wbudowany produkt kartezjański Πzachowuje się ładnie w przypadku nieskończonych list, wyliczając każdy k -ple dokładnie raz.

Wolfram Language (Mathematica) , 61 bajtów

SortBy[Range[-(x=2Abs@#+Boole[#>=0]),x]~Tuples~#2,#.#&][[x]]&

Wypróbuj online!

(Pobiera na wejściu liczbę całkowitą, a następnie długość krotki.)

Odwrotność:

If[OddQ[#],#-1,-#]/2&@Tr@Position[SortBy[Range[-(x=Ceiling@Norm@#),x]~Tuples~Length@#,#.#&],#]&

Wypróbuj online!

Jak to działa

Pomysł jest prosty: zamieniamy liczbę całkowitą na dodatnią liczbę całkowitą (odwzorowując 0,1,2,3, ... na 1,3,5,7, ... i -1, -2, -3, ... do 2,4,6, ...), a następnie indeksuj do wszystkich k- sortek, posortowanych według odległości od początku, a następnie według domyślnego podziału remisów przez Mathematica.

Ale nie możemy używać nieskończoną listę, więc kiedy patrzymy na n ^th k -tuple, tylko generować k -tuples liczb całkowitych w przedziale {- n , ..., n }. Jest to z pewnością wystarczające, ponieważ n- ^ta najmniejsza k- liczba według normy ma normę mniejszą niż n , a wszystkie krotki normy n lub mniej znajdują się na tej liście.

Na odwrót, po prostu generujemy wystarczająco długą listę k- małż, znajdujemy pozycję danego k- małż na tej liście, a następnie odwracamy operację „fold na dodatnią liczbę całkowitą”.

J, 7 bajtów

#.,|:#:

Kod J, aby zrobić to krępująco proste

Bardzo prostą funkcją parowania (lub funkcją krotkowania) jest po prostu przeplatanie cyfr rozwinięcia binarnego każdej z liczb. Na przykład (47, 79)sparowano by jako takie:

1_0_0_1_1_1_1
 1_0_1_1_1_1
-------------
1100011111111

lub 6399. Oczywiście, możemy w sposób trywialny uogólnić na dowolne n-krotki.

Sprawdźmy, jak to działa czasownik po czasowniku.

#:jest anty-podstawa druga, gdy jest używana monadycznie, zwraca binarne rozwinięcie liczby. #: 47 79daje wynik:

0 1 0 1 1 1 1
1 0 0 1 1 1 1

|:jest operatorem transpozycji, który po prostu obraca tablicę. Obracanie wyniku #: 47 79daje:

0 1
1 0
0 0
1 1
1 1
1 1
1 1

Gdy jest używany monadycznie, ,jest operatorem ravela, tworzy z tabeli 1-wymiarową listę:

0 1 1 0 0 0 1 1 1 1 1 1 1 1

Na koniec #.konwertuje binarne rozszerzenie z powrotem, dając nam wynik 6339.

To rozwiązanie będzie działać dla dowolnego ciągu liczb całkowitych.

Perl 6 , 148 bajtów

my@s=map ->\n{|grep {n==abs any |$_},(-n..n X -n..n)},^Inf;my&f={$_==1??+*!!do {my&g=f $_-1;my@v=map {.[0],|g .[1]},@s;->\n{@v[n>=0??2*n!!-1-2*n]}}}

Wypróbuj online!

Nie golfowany:

sub rect($n) {
    grep ->[$x,$y] { abs($x|$y) == $n }, (-$n..$n X -$n..$n);
}

my @spiral = map { |rect($_) }, ^Inf;

sub f($k) {
    if ($k == 1) {
        -> $_ { $_ }
    } else {
        my &g = f($k-1);
        my @v = map -> [$x, $y] { $x, |g($y) }, @spiral;
        -> $_ { $_ >= 0 ?? @v[2*$_] !! @v[-1-2*$_] }
    }
}

Wyjaśnienie:

• rect($n)jest funkcją pomocniczą, która generuje współrzędne punktów integralnych na krawędzi prostokąta od współrzędnych (-$n,$n)do($n, $n) .

• @spiral jest leniwą, nieskończoną listą integralnych punktów na krawędziach prostokątów o rosnącym rozmiarze, zaczynając od 0.

• f($k)zwraca funkcję, która jest $kbijectionem liczb całkowitych na -tule liczb całkowitych.

Jeśli $kjest 1,f zwraca odwzorowanie tożsamości -> $_ { $_ }.

Inaczej, &g jest rekurencyjnie uzyskiwane mapowanie z liczb całkowitych na $k-1liczby całkowite.

Następnie @spiralwychodzimy z początku i w każdym punkcie $ktworzymy -tuple, biorąc współrzędną X i spłaszczony wynik wywołania gze współrzędną Y. To leniwie generowane mapowanie jest przechowywane w tablicy @v.

@vzawiera wszystkie $k-pacje zaczynające się od indeksu 0, więc aby rozszerzyć indeksowanie na ujemne liczby całkowite, po prostu mapujemy dodatnie dane wejściowe na liczby parzyste, a ujemne dane wejściowe na liczby nieparzyste. Zwracana jest funkcja (zamknięcie), która wyszukuje elementy @vw ten sposób.

JavaScript, 155 bajtów

f=k=>x=>(t=x<0?1+2*~x:2*x,h=y=>(g=(v,p=[])=>1/p[k-1]?v||t--?0:p.map(v=>v&1?~(v/2):v/2):[...Array(1+v)].map((_,i)=>g(v-i,[...p,i])).find(u=>u))(y)||h(y+1))(0)

f=k=>x=>(t=x<0?1+2*~x:2*x,h=y=>(g=(v,p=[])=>1/p[k-1]?v||t--?0:p.map(v=>v&1?~(v/2):v/2):[...Array(1+v)].map((_,i)=>g(v-i,[...p,i])).find(u=>u))(y)||h(y+1))(0)

<p>k = <input id=k value=2>
<p>from <input id=a value=-5>
<p>to <input id=b value=5>
<p><button type="button" onclick="for(o.value='',i=+a.value;i<=b.value;i++)o.value+=[i,f(+k.value)(i)].join(':')+'\n';">generate</button>
<p><pre><output id=o>

Wersja Prettify:

k => x => {
  // Map input to non-negative integer
  if (x > 0) t = 2 * x; else t = 2 * -x - 1;
  // we try to generate all triples with sum of v
  g = (v, p = []) => {
    if (p.length === k) {
      if (v) return null;
      if (t--) return null;
      // if this is the t-th one we generate then we got it
      return p;
    }
    for (var i = 0; i <= v; i++) {
      var r = g(v-i, [...p, i]);
      if (r) return r;
    }
  }
  // try sum from 0 to infinity
  h = x => g(x) || h(x + 1);
  // map tuple of non-negative integers back
  return h(0).map(v => {
    if (v % 2) return -(v + 1) / 2
    else return v / 2;
  });
}

• Najpierw mapujemy wszystkie liczby całkowite na wszystkie nieujemne liczby całkowite jeden po drugim:
  • jeśli n> 0, to wynik = n * 2
  • w przeciwnym razie wynik = -n * 2 - 1
• Po drugie, dajemy wszystkim krotkom z nieujemnymi liczbami całkowitymi długości k kolejność:
  • obliczyć sumę wszystkich elementów, najpierw mniejszy
  • jeśli suma jest równa, porównaj od lewej do prawej, mniejsza jest pierwsza
  • W rezultacie otrzymaliśmy mapę dla wszystkich nieujemnych liczb całkowitych do krotek z k nieujemnymi liczbami całkowitymi
• Na koniec zamapuj nieujemne liczby całkowite w krotce podane w drugim kroku na wszystkie liczby całkowite o podobnej formule w pierwszym kroku

Wolfram Language (Mathematica) , 107 bajtów

(-1)^#⌈#/2⌉&@Nest[{w=⌊(√(8#+1)-1)/2⌋;x=#-w(w+1)/2,w-x}~Join~{##2}&@@#&,{2Abs@#-Boole[#<0]},#2-1]&

Wypróbuj online!

Odwrotnie, 60 bajtów

(-1)^#⌈#/2⌉&@Fold[+##(1+##)/2+#&,2Abs@#-Boole[#<0]&/@#]&

Wypróbuj online!

Wyjaśnienie:

Z -> N0 przez f(n) = 2n if n>=0 and -2n-1 if n<0

N0 -> N0 ^ 2 poprzez odwrotność funkcji parowania

N0 -> N0 ^ k Wielokrotnie stosuj powyższe wartości do lewej cyfry, aż uzyskamy długość k

N0 ^ k -> Z ^ k via f(n) = (-1)^n * ceil(n/2), pod względem elementu

Mathematica, 101 bajtów

(-1)^#⌈#/2⌉&@Nest[{a=#~IntegerExponent~2+1,#/2^a+1/2}~Join~{##2}&@@#&,{2Abs@#+Boole[#<=0]},#2-1]&

Podobnie jak powyżej (używa N zamiast N0), ale wykorzystuje odwrotność bijection f: N ^ 2 -> N przez f(a, b) = 2^(a - 1)(2b - 1)

JavaScript, 112 bajtów

k=>x=>(r=Array(k).fill(''),[...`${x<0?2*~x+1:2*x}`].map((c,i,s)=>r[(s.length-i)%k]+=c),r.map(v=>v&1?~(v/2):v/2))

1. przekonwertować na nieujemne
2. (n * k + i) od cyfry do i-tej liczby
3. nawrócić z powrotem

05AB1E , 20 bajtów

[D_#>3‰`<s])sô0ζεR3β

Wypróbuj online! Port odpowiedzi @ Blckknght. Odwrotnie, 17 bajtów:

[Z_#>3‰ø`<s])˜R3β

Wypróbuj online!

Galaretka , 15 bajtów

µ<1ạḤðŒRṗAS$Þ⁸ị

Wypróbuj online!

1-indeksowany.

Odwrotność:

AṀ×LŒRṗLAS$Þiµ:2NḂ}¡

Wypróbuj online!