Auf dem Gebiet der Mathematik, die die Unendlichkeit studiert, ist bekannt, dass das kartesische Produkt einer endlichen Menge zählbarer Mengen ebenfalls zählbar ist .
Ihre Aufgabe ist es, zwei Programme zu schreiben, um dies zu implementieren, eines von Liste zu Ganzzahl, eines von Ganzzahl zu Liste.
Ihre Funktion muss bijektiv und deterministisch sein, was bedeutet, dass 1
sie immer einer bestimmten Liste und 2
immer einer anderen bestimmten Liste usw. zugeordnet wird.
Zuvor haben wir Ganzzahlen einer Liste zugeordnet, die nur aus 0
und besteht 1
.
Jetzt besteht die Liste jedoch aus nicht negativen Zahlen.
Technische Daten
- Programm / Funktion, angemessenes Eingabe- / Ausgabeformat.
- Ob die zugeordneten Ganzzahlen von
1
oder von beginnen,0
ist Ihre Wahl, was bedeutet, dass Sie0
nichts zuordnen müssen (aber können). - Das leere Array
[]
muss codiert sein. - Die Ein- / Ausgabe kann in einer beliebigen Basis erfolgen.
- Das Teilen von Code zwischen den beiden Funktionen ist zulässig .
Wertung
Das ist Code-Golf . Die niedrigste Punktzahl gewinnt.
Punktzahl ist die Summe der Längen (in Bytes) der beiden Programme / Funktionen.
code-golf
set-theory
Undichte Nonne
quelle
quelle
N^inf -> N
?Antworten:
Gelee ,
1816 BytesListe auf Ganzzahl,
108 BytesOrdnet Listen nicht negativer Ganzzahlen positiven Ganzzahlen zu. Probieren Sie es online aus!
Ganzzahl zur Liste, 8 Bytes
Ordnet positive Ganzzahlen Listen nicht negativer Ganzzahlen zu. Probieren Sie es online aus!
Hintergrund
Sei p 0 , p 1 , p 2 , ⋯ die Folge von Primzahlen in aufsteigender Reihenfolge.
Für jede Liste von nicht-negativen ganzen Zahlen A: = [a 1 , ⋯, ein n ] , bilden wir A bis P 0 z (A) p 1 a 1 ⋯ p n a n , wobei z (A) ist die Anzahl der nachfolgende Nullen von A .
Das Umkehren der obigen Karte ist unkompliziert. Für eine positive ganze Zahl k faktorisieren wir sie eindeutig als das Produkt aufeinanderfolgender Primzahlen n = p 0 α 0 p 1 α 1 ⋯ p n α n , wobei α n > 0 ist , und rekonstruieren dann die Liste als [α 1 , ⋯, α n ] , wobei α 0 -Nullen angehängt werden.
Wie es funktioniert
Liste in Ganzzahl
Ganzzahl zur Liste
Beispielausgabe
Die ersten hundert positiven ganzen Zahlen werden den folgenden Listen zugeordnet.
quelle
Python 2, 88 Bytes
Demo:
Python 2, 130 Bytes
Hier ist eine „effizientere“ Lösung, bei der die Bitlänge der Ausgabe in der Bitlänge der Eingabe eher linear als exponentiell ist.
quelle
e
möglicherweise nur die Umkehrung für Folgendes erstellend
:e=lambda l,i=0:l!=d(i)and-~e(l,i+1)
.Python 2,
204202 BytesFunktioniert durch wiederholtes Anwenden einer Z + x Z + <-> Z + -Bijektion, der die Listenlänge vorangestellt ist.
quelle
e
ist Liste zu Ganzzahl,d
ist Ganzzahl zu Liste (codieren / decodieren).Retina, 17 + 23 = 40 Bytes
Von der Liste zur Ganzzahl:
Probieren Sie es online aus!
Von der Ganzzahl zur Liste:
Probieren Sie es online aus!
Verwendet den Kaseorg-Algorithmus .
quelle