Biorąc pod uwagę dodatnią liczbę całkowitą k > 1i nieujemną liczbę całkowitą i, wygeneruj k-tuple (lub k-wymiarowy wektor) liczb całkowitych nieujemnych. Dla każdego k, mapa z ℕ do ℕ ^k , musi być bijective . Oznacza to, że każde wejście ipowinno dawać inną krotkę, a każda możliwa krotka musi być wytworzona przez jakiś wkład i.

Możesz napisać program lub funkcję, pobierając dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji i wypisując wynik przez STDOUT (lub najbliższą alternatywę), wartość zwracaną funkcji lub parametr funkcji (wyjściowej).

Możesz użyć dowolnego wygodnego, jednoznacznego, płaskiego formatu listy wyników.

Rozwiązanie powinno nakładać żadnych sztucznych limitów ki iale można założyć, że pasują one do natywnej wielkości całkowitej Twojego języka. Przynajmniej musisz obsługiwać wartości 255, ale nawet Twoja natywna liczba całkowita jest mniejsza.

Dla każdego 1 < k < 32, Twój kod powinien produkować wynik w ciągu kilku sekund (oczywiście, jeśli odpowiedź nie obsługuje tak duże ze względu na poprzedniej reguły limit zostanie odpowiednio skorygowana). Nie powinno to stanowić problemu: możliwe jest rozwiązanie tego problemu tak, aby działało do 2 ¹²⁸ w ciągu kilku sekund, ale limit polega na unikaniu odpowiedzi, które faktycznie powtarzają się w celu znalezienia wyniku.i < 231i0i

Podaj w odpowiedzi opis wybranego mapowania i uzasadnienie, dlaczego jest ono bijective (nie musi to być formalny dowód).

To jest kod golfowy, wygrywa najkrótsza odpowiedź (w bajtach).

Powiązane wyzwania

• Wygeneruj parę liczb całkowitych z nieujemnej
• Wypisuje listę wszystkich liczb wymiernych

Pyth, 15 12 bajtów

ms+0_%Q>_zdQ

Zestaw testowy

Moja transformacja jest podobna do jednej z xnor, ale w bazie 10. Działa poprzez rozpakowanie danych wejściowych na k oddzielnych liczb:

n = 21003034
k = 3

21003034
 1  3  4    134
2  0  3     203
  0  0        0

Liczby są uporządkowane w malejącej pozycji skrajnie prawej cyfry, dzięki czemu możliwe są wszystkie uporządkowania dowolnej grupy liczb.

Kod działa w ten sposób, że odwracamy dane wejściowe, następnie odcinamy ostatnie 0, 1, ... k-1cyfry, a następnie bierzemy każdą kcyfrę, ponownie odwracamy, przyklejamy 0na początku i konwertujemy na int.

CJam, 20 bajtów

q~({4b2fmd2/z2fb~p}*

Mapowanie jest bijectywne, ponieważ stosuje mapowanie z tej odpowiedzi k - 1 razy.

Program odczytuje dane wejściowe jako i k. Wypróbuj online w interpretatorze CJam .

Pomysł

Możemy skonstruować bijective mapping f: N → N ² , definiując f (i) w następujący sposób:

• Konwertuj i na tablicę jego cyfr binarnych.

• Wpisz 0 do tej tablicy, jeśli jest nieparzysta liczba cyfr.

• Rozplataj uzyskaną tablicę, tworząc nowe w procesie.

• Konwertuj te tablice z podstawy 2 na liczbę całkowitą. Określić f ₁ (I) i f ₂ (I) , jak wyniki.

Aby uzyskać bijective mapping g: N → N ³ , możemy zdefiniować g (n): = (f ₁ (i), f ₁ (f ₂ (i)), f ₂ (f ₂ (i))) .

Aby uzyskać bijective mapping h: N → N ⁴ , możemy zdefiniować h (i): = (g ₁ (i), g ₂ (i), f ₁ (g ₃ (i)), f ₂ (g ₃ ( i))) .

Kontynuując powyższy proces, ostatecznie dochodzimy do mapy dwuskładnikowej N → ^Nk .

Kod

q~      e# Read and evaluate all input. This pushes i and k.
({      e# Do k-1 times:
  4b    e#   Convert the integer on the stack (initially i) to base 4.
  2fmd  e#   Replace each base-4 digit d by d/2 and d%2.
  2/    e#   Split into the chunks [d/2 d%2].
  z     e#   Transpose. This collects all quotients in one array and all
        e#   residues in another one.
  2fb   e#   Convert each array from base 2 to integer.
  ~     e#   Dump both integers on the stack.
  p     e#   Print the topmost one.
}*      e#

CJam, 18 bajtów

q~({)2bW%_1#p))b}*

Używa bardziej głupiej formuły.

Wypróbuj tutaj .

Wyjaśnienie

q~          e# Read input.
({          e# Repeat k-1 times:
    )       e# Increment the current integer (initially i), to make it positive.
    2b      e# Convert to binary.
    W%      e# Reverse the binary.
            e# The result can be any non-empty binary string without trailing 0s.
    _1#     e# Find the position of the first 1, or the number of initial 0s.
    p       e# Print.
    )       e# Extract the final bit, which is always 1.
            e# An array that can be any binary string is left in the stack.
    )       e# Increment the 1 to make it 2.
    b       e# Convert the binary string to a number using base 2.
            e# Only the number of initial 0s doesn't affect the result,
            e# which is exactly what is printed before.
}*          e# The final integer is printed automatically when the program ends.

Podsumowując, odwzorowuje dodatnią liczbę całkowitą na:

1. Liczba końcowych zer.
2. Oryginalna liczba całkowita z końcowymi zerami została usunięta, odwrócona, a końcowa (pierwotnie początkowa) 1 usunięta.

Python 2, 62

lambda z,k:[int('0'+bin(z)[~i:1:-k][::-1],2)for i in range(k)]

Ten kod jest brzydki i nadaje się do gry w golfa, ale pomysł jest bardzo prosty.

Zapakuj kbinarne rozszerzenia w jedno, odczytując każdą kcyfrę z różnymi przesunięciami. Na przykład za k=3pomocą danych wejściowych 357odwzorowuje się na (3,0,7):

101100101 <- 357
  1  0  1 -> 5
 0  0  0  -> 0
1  1  1   -> 7

Ponowne skompresowanie liczb odwraca je, więc jest to bijection. Czyniąc to, pomyśl o rozszerzeniach binarnych jako mających nieskończoną liczbę zer wiodących.

J, 38 28 27 bajtów

(({.,g^:_1@}.)g=:_ q:>:)~<:

To jest milcząca, dwójkowym czasownik że trwa I i K jako argumenty lewych i prawych. Spróbuj go online z J.js .

Pomysł

Definiujemy mapę f: N → N ^K przez F (I): (a = ₁ , ... a _k-1 , p ₁ ^{α _k} ... s ₂ ^{a _{k + 1}} ... - 1) , gdzie ⟨p _n ⟩ jest ciąg liczb pierwszych i i + 1 = p ₁ ^{α ₁} p ₂ ^{α ₂} … .

Według Podstawowego Twierdzenia Arytmetycznego mapa g: N → N ^ω zdefiniowana przez g (i): = (α ₁ , α ₂ ,…) (wykładniki pierwszej faktoryzacji i + 1 ) jest bijectywna.

Ponieważ f (i) = (g ₁ (i),… g _k-1 (i), g ^-1 (g _k (i), g _{k + 1} (i),…)) , mapa f jest dwuskładnikowa, ponieważ dobrze.

Kod

                            Left argument: i -- Right argument: k
                         <: Decerement k.
(                      )~   Reverse the order of the arguments and apply the
                            dyadic verb inside the parentheses to k-1 and i.
              g=:            Define a monadic helper verb g:
                     >:       Increment its right argument.
                 _ q:         Calculate the exponents of the prime factorization.
                             (implicit) Apply g to i.
(            )               Apply the dyadic verb inside the parentheses to k-1
                             and (g i).
           }.                 Drop the first k-1 elements of (g i)...
          @                   and...
     g^:_1                    apply the inverse of g to the result.
  {.                          Take the first k-1 elements of (g i).
    ,                         Append the rightmost result to the leftmost one.

Python 2, 72

q=lambda z:z and z%2+2*q(z/4)
g=lambda z,k:1/k*[z]or[q(z)]+g(q(z/2),k-1)

Funkcja qdziała na liczby binarne, biorąc co drugi bit, zaczynając od końca. W rezultacie q(z), q(z>>1)podaje dwie liczby, których cyfry binarne przeplatają się, aby dać z. Na przykład 594 dzieli się na 12 i 17.

1001010010   <- 594
 0 1 1 0 0   ->  12
1 0 0 0 1    ->  17

To jest bijection, ponieważ możemy spakować liczby z powrotem, aby odzyskać oryginalny numer.

Funkcja gstosuje te k-1czasy wstrząsów , rozszerzając się z jednego elementu do pary do potrójnego ... do k-pleple. Za każdym razem ostatni element jest rozszerzany do dwóch elementów. Odbywa się to rekurencyjnie poprzez mapowanie danych wejściowych na parę poprzez bijection, pobranie pierwszego elementu pary do pierwszego wejścia danych wyjściowych i zastosowanie funkcji rekurencyjnie k-1do drugiego elementu w celu uzyskania pozostałych wpisów.