Erzeugen Sie bei einer positiven k > 1und einer nicht negativen ganzen Zahl iein kTupel (oder einen kdimensionalen Vektor) von nicht negativen ganzen Zahlen. Für jeden k, die Karte von n zu n ^k , muss bijektiv sein . Das heißt, jede Eingabe isollte ein anderes Tupel erzeugen, und jedes mögliche Tupel muss von einer Eingabe erzeugt werden i.

Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.

Sie können für die Ausgabe jedes bequeme, eindeutige und flache Listenformat verwenden.

Ihre Lösung sollte keine künstlichen Grenzen setzen kund iSie können davon ausgehen, dass sie in die native Ganzzahlgröße Ihrer Sprache passen. Zumindest müssen Sie Werte bis zu einer 255nativen Ganzzahlgröße unterstützen, die kleiner ist.

Für alle 1 < k < 32, sollten Sie Ihren Code ein Ergebnis in wenigen Sekunden erzeugen (natürlich nur , wenn Ihre Antwort nicht unterstützt , dass große aufgrund der vorherigen Regel wird die Grenze entsprechend angepasst). Dies sollte kein Problem sein: Es ist möglich, diese Herausforderung so zu lösen, dass sie in wenigen Sekunden bis zu 2 ¹²⁸ funktioniert , aber das Limit besteht darin, Antworten zu vermeiden, die tatsächlich von bis iterieren , um das Ergebnis zu finden.i < 231i0i

Bitte geben Sie in Ihrer Antwort eine Beschreibung der von Ihnen gewählten Zuordnung und eine Begründung an, warum sie bijektiv ist (dies muss kein formaler Beweis sein).

Dies ist Code Golf, die kürzeste Antwort (in Bytes) gewinnt.

Verwandte Herausforderungen

• Generieren Sie ein ganzzahliges Paar aus einem nicht negativen
• Eine Liste aller rationalen Zahlen ausgeben

Pyth, 15 12 Bytes

ms+0_%Q>_zdQ

Testsuite

Meine Transformation ähnelt einer von xnors, befindet sich jedoch in der Basis 10. Sie entpackt die Eingabe in k separate Zahlen:

n = 21003034
k = 3

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

Die Nummern sind in absteigender Reihenfolge der ganz rechten Ziffer angeordnet, so dass alle Anordnungen einer beliebigen Nummerngruppe möglich sind.

Die Art und Weise, wie der Code funktioniert, ist, dass wir die Eingabe umkehren, dann die letzten 0, 1, ... k-1Ziffern abschneiden , dann jede kzehnte Ziffer nehmen, erneut umkehren, 0am Anfang ein kleben und in int konvertieren.

CJam, 20 Bytes

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

Das Mapping ist bijektiv, da es das Mapping aus dieser Antwort k - 1 mal anwendet .

Das Programm liest die Eingabe als i k. Probieren Sie es online im CJam-Interpreter aus .

Idee

Wir können eine bijektive Abbildung f: N → N ² konstruieren, indem wir f (i) wie folgt definieren:

• Konvertiere i in das Array seiner Binärziffern.

• Stellen Sie diesem Array eine 0 voran , wenn die Anzahl der Stellen ungerade ist.

• Deinterleave das resultierende Array, bilden neue im Prozess.

• Konvertieren Sie diese Arrays von der Basis 2 in eine Ganzzahl. Definieren Sie als Ergebnis f ₁ (i) und f ₂ (i) .

Um eine bijektive Abbildung g: N → N ^{3 zu erhalten} , können wir g (n) definieren: = (f ₁ (i), f ₁ (f ₂ (i)), f ₂ (f ₂ (i))) .

Um eine bijektive Abbildung h: N → N ^{4 zu erhalten} , können wir h (i) definieren: = (g ₁ (i), g ₂ (i), f ₁ (g ₃ (i)), f ₂ (g ₃ ( i))) .

Wenn wir den obigen Prozess fortsetzen, gelangen wir schließlich zu einer Bijektivkarte N → N ^k .

Code

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 Bytes

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

Es benutzt eine dummere Formel.

Probieren Sie es hier aus .

Erläuterung

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.

Zusammenfassend wird eine positive Ganzzahl zugeordnet zu:

1. Die Anzahl der nachgestellten Nullen.
2. Die ursprüngliche Ganzzahl mit nachgestellten Nullen wurde entfernt, umgekehrt und die nachstehende (ursprünglich initiale) 1 wurde entfernt.

Python 2, 62

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

Dieser Code ist hässlich und golfen, aber die Idee ist sehr einfach.

Packen Sie kbinäre Erweiterungen in eine, indem Sie jede kZiffer mit unterschiedlichen Offsets lesen . Beispiel: Mit k=3der Eingabe wird 357Folgendes zugeordnet (3,0,7):

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

Wenn Sie die Zahlen wieder zusammenzippen, wird dies rückgängig gemacht. Stellen Sie sich dabei die binären Erweiterungen als unendlich viele führende Nullen vor.

J, 38 28 27 Bytes

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

Dies ist ein stillschweigendes, dyadisches Verb, das i und k als linkes und rechtes Argument verwendet. Versuchen Sie es online mit J.js .

Idee

Wir definieren eine Abbildung f: N → N ^k durch f (i): = (α ₁ , ... α _k-1 , p ₁ ^{α _k} ... p ₂ ^{α _{k + 1}} ... - 1), wobei⟨p _n ⟩ist Folge von Primzahlen undi + 1 = p ₁ ^{α ₁} p ₂ ^{α ₂} ….

Nach dem Fundamental Arithmetic Theorem ist die durch g (i): = (α ₁ , α ₂ ,…) definierte Abbildung g: N → N ^ω (Exponenten der Primfaktorisierung von i + 1 ) bijektiv.

Da f (i) = (g ₁ (i), ... g _k-1 (i), g ^-1 (g _k (i), g _{k + 1} (i), ...)) , die Karte f bijektiv ist als Gut.

Code

                            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)

Die Funktion q wirkt auf Binärzahlen, indem jedes zweite Bit vom Ende an genommen wird. Infolgedessen q(z), q(z>>1)gibt es zwei Zahlen, deren Binärziffern sich streuen z. Zum Beispiel teilt sich 594 in 12 und 17.

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

Dies ist ein Misserfolg, da wir die Nummern wieder zusammenzippen können, um die ursprüngliche Nummer wiederherzustellen.

Die Funktion gwendet diese Bijektionszeiten k-1an und erweitert sie von einem einzelnen Element zu einem Paar zu einem Dreifachen ... zu einem k-Tupel. Jedes Mal wird das letzte Element auf zwei Elemente erweitert. Dies geschieht rekursiv, indem die Eingabe über die Bijektion einem Paar zugeordnet wird, das erste Element des Paares für den ersten Eintrag der Ausgabe verwendet und die Funktion rekursiv mit angewendet wirdk-1 auf das zweite Element angewendet wird, um die verbleibenden Einträge zu erzeugen.