Stellen Sie sich zwei positive ganze Zahlen A und B vor. Ich möchte diese beiden zu einer einzigen ganzen Zahl C kombinieren.
Es kann keine anderen Ganzzahlen D und E geben, die sich zu C verbinden. Das Kombinieren mit dem Additionsoperator funktioniert also nicht. ZB 30 + 10 = 40 = 40 + 0 = 39 + 1 Konatination funktioniert auch nicht. ZB "31" + "2" = 312 = "3" + "12"
Diese Kombinationsoperation sollte auch deterministisch sein (immer das gleiche Ergebnis mit den gleichen Eingaben liefern ) und sollte immer eine ganze Zahl entweder auf der positiven oder der negativen Seite von ganzen Zahlen ergeben.
10,001*A + B
?Antworten:
Sie suchen nach einem bijektiven
NxN -> N
Mapping. Diese werden zB zum Verzahnen verwendet . In diesem PDF finden Sie eine Einführung in sogenannte Pairing-Funktionen . Wikipedia führt eine bestimmte Paarungsfunktion ein, nämlich die Cantor-Paarungsfunktion :Drei Bemerkungen:
ZxZ -> N
Mapping. Die Cantor-Funktion funktioniert nur bei nicht negativen Zahlen. Dies ist jedoch kein Problem, da es einfach ist, eine Bijektionf : Z -> N
wie folgt zu definieren :quelle
Die Cantor-Pairing-Funktion ist wirklich eine der besseren, wenn man bedenkt, dass sie einfach, schnell und platzsparend ist, aber hier gibt es etwas noch Besseres, das Matthew Szudzik bei Wolfram veröffentlicht hat . Die Einschränkung der Cantor-Pairing-Funktion (relativ) besteht darin, dass der Bereich der codierten Ergebnisse nicht immer innerhalb der Grenzen einer
2N
Bit-Ganzzahl bleibt, wenn die Eingaben zweiN
Bit-Ganzzahlen sind. Das heißt, wenn meine Eingaben zwei16
Bit-Ganzzahlen im Bereich von sind0 to 2^16 -1
, sind2^16 * (2^16 -1)
Kombinationen von Eingaben möglich. Nach dem offensichtlichen Pigeonhole-Prinzip benötigen wir also mindestens eine Ausgabe mit einer Größe2^16 * (2^16 -1)
, die gleich2^32 - 2^16
oder mit anderen Worten einer Karte von ist32
Bitnummern sollten idealerweise machbar sein. Dies ist in der Programmierwelt möglicherweise nicht von geringer praktischer Bedeutung.Cantor-Pairing-Funktion :
Geben Sie die Funktion von Szudzik ein :
Angesichts der Tatsache, dass wir uns normalerweise mit den signierten Implementierungen von Zahlen unterschiedlicher Größe in Sprachen / Frameworks befassen, betrachten wir
signed 16
Bit-Ganzzahlen im Bereich von-(2^15) to 2^15 -1
(später werden wir sehen, wie sogar die Ausgabe auf den signierten Bereich ausgedehnt werden kann). Daa
undb
müssen positiv sein, reichen sie von0 to 2^15 - 1
.Cantor-Pairing-Funktion :
Nun Szudziks Funktion :
Lassen Sie uns negative ganze Zahlen berücksichtigen. Das geht über die ursprüngliche Frage hinaus, die ich kenne, aber ich arbeite nur daran, zukünftigen Besuchern zu helfen.
Cantor-Pairing-Funktion :
Szudziks Funktion :
Jetzt alles, während die Ausgabe immer positiv war. In der signierten Welt wird es noch platzsparender sein, wenn wir die Hälfte der Ausgabe auf die negative Achse übertragen könnten . Sie könnten es für Szudzik so machen:
Was ich tue: Nachdem ich
2
den Eingaben ein Gewicht von zugewiesen und die Funktion durchlaufen habe, teile ich den Ausgang durch zwei und bringe einige von ihnen durch Multiplizieren mit auf die negative Achse-1
.Siehe die Ergebnisse. Für jede Eingabe im Bereich einer vorzeichenbehafteten
16
Bitnummer liegt die Ausgabe innerhalb der Grenzen einer vorzeichenbehafteten32
Bit-Ganzzahl, die cool ist. Ich bin mir nicht sicher, wie ich den gleichen Weg für die Cantor-Pairing-Funktion gehen soll, habe aber nicht so viel versucht, wie es nicht so effizient ist. Darüber hinaus bedeutet mehr Berechnungen in der Cantor-Pairing-Funktion, dass sie auch langsamer ist .Hier ist eine C # -Implementierung.
Da die Zwischenberechnungen die Grenzen der
2N
vorzeichenbehafteten Ganzzahl überschreiten können , habe ich den4N
Ganzzahltyp verwendet (die letzte Division durch2
bringt das Ergebnis zurück zu2N
).Der Link, den ich für eine alternative Lösung bereitgestellt habe, zeigt eine grafische Darstellung der Funktion, die jeden einzelnen Punkt im Raum nutzt. Es ist erstaunlich zu sehen, dass Sie ein Koordinatenpaar eindeutig reversibel in eine einzelne Zahl codieren können! Magische Welt der Zahlen !!
quelle
(0,0)
zuordnen möchten(65535,65535)
,a<<16 + b
ist dies in jeder Hinsicht besser (schneller, einfacher, verständlicher, offensichtlicher) . Wenn Sie möchten ,(-32768,-32768)
um(327687,327687)
zuerst statt, 32768 nur Gegenstand.Wenn A und B mit 2 Bytes ausgedrückt werden können, können Sie sie auf 4 Bytes kombinieren. Setzen Sie A auf die höchstwertige Hälfte und B auf die niedrigstwertige Hälfte.
In der C-Sprache ergibt sich (unter der Annahme, dass sizeof (short) = 2 und sizeof (int) = 4):
quelle
combine()
solltereturn (unsigned short)(A<<16) | (unsigned short)(B);
also , dass negative Zahlen richtig verpackt werden können.A<<16
wird Grenzen überschreiten . Es sollte seinreturn (unsigned int)(A<<16) | (unsigned short)(B);
Ist das überhaupt möglich?
Sie kombinieren zwei Ganzzahlen. Sie haben beide den Bereich -2.147.483.648 bis 2.147.483.647, aber Sie werden nur die positiven nehmen. Das ergibt 2147483647 ^ 2 = 4.61169E + 18 Kombinationen. Da jede Kombination eindeutig sein muss UND zu einer Ganzzahl führt, benötigen Sie eine magische Ganzzahl, die diese Anzahl von Zahlen enthalten kann.
Oder ist meine Logik fehlerhaft?
quelle
Die mathematische Standardmethode für positive ganze Zahlen besteht darin, die Eindeutigkeit der Primfaktorisierung zu verwenden.
Der Nachteil ist, dass das Bild in der Regel einen großen Bereich von Ganzzahlen umfasst. Wenn Sie also die Zuordnung in einem Computeralgorithmus ausdrücken, können Probleme bei der Auswahl eines geeigneten Typs für das Ergebnis auftreten.
Sie können dies ändern, um mit Negativen umzugehen,
x
undy
indem Sie Flags mit Potenzen von 5 und 7 Termen codieren.z.B
quelle
Die Zahl
a
sei die erste,b
die zweite. Seip
diea+1
-te Primzahl,q
sei dieb+1
-te PrimzahlDann ist das Ergebnis
pq
, oba<b,
oder2pq
oba>b
. Wenna=b
, lass es seinp^2
.quelle
Es ist nicht so schwer, ein Mapping zu erstellen:
Etwas schwieriger ist es, herauszufinden, wie man den Wert für ein beliebiges a, b erhält.
quelle
f(a, b) = s(a+b) + a
, wos(n) = n*(n+1)/2
s(a+b+1)-s(a+b) = a+b+1 < a
.Ich habe nicht verstanden, was du meinst mit:
Wie kann ich (größer als), (kleiner als) Zeichen in dieses Forum schreiben?
quelle
backtick escapes
.Obwohl die Antwort von Stephan202 die einzig wirklich allgemeine ist, können Sie für ganze Zahlen in einem begrenzten Bereich bessere Ergebnisse erzielen. Wenn Ihr Bereich beispielsweise 0..10.000 beträgt, können Sie Folgendes tun:
Die Ergebnisse können in eine einzelne Ganzzahl für einen Bereich bis zur Quadratwurzel der Kardinalität des Ganzzahltyps passen. Dies ist etwas effizienter als die allgemeinere Methode von Stephan202. Es ist auch wesentlich einfacher zu dekodieren; für den Anfang keine Quadratwurzeln erforderlich :)
quelle
Für positive ganze Zahlen als Argumente und wo die Reihenfolge der Argumente keine Rolle spielt:
Hier ist eine ungeordnete Pairing-Funktion :
Für x ≠ y gibt es eine einzigartige ungeordnete Paarungsfunktion :
quelle
Überprüfen Sie dies: http://en.wikipedia.org/wiki/Pigeonhole_principle . Wenn A, B und C vom gleichen Typ sind, kann dies nicht durchgeführt werden. Wenn A und B 16-Bit-Ganzzahlen und C 32-Bit sind, können Sie einfach die Verschiebung verwenden.
Die Natur von Hashing-Algorithmen besteht darin, dass sie nicht für jede unterschiedliche Eingabe einen eindeutigen Hash bereitstellen können.
quelle
Hier ist eine Erweiterung des Codes von @DoctorJ auf unbegrenzte Ganzzahlen, basierend auf der von @nawfal angegebenen Methode. Es kann codieren und decodieren. Es funktioniert mit normalen Arrays und Numpy-Arrays.
quelle
Wie wäre es mit etwas viel Einfacherem: Bei zwei Zahlen sei A und B die Verkettung: 'A' + ';' + 'B'. Dann sei die Ausgabe Hash (str). Ich weiß, dass dies keine mathematische Antwort ist, aber ein einfaches Python-Skript (das eine eingebaute Hash-Funktion hat) sollte den Job erledigen.
quelle
Was Sie vorschlagen, ist unmöglich. Sie werden immer Kollisionen haben.
Um zwei Objekte einem anderen einzelnen Satz zuzuordnen, muss der zugeordnete Satz eine Mindestgröße der Anzahl der erwarteten Kombinationen haben:
Unter der Annahme einer 32-Bit-Ganzzahl haben Sie 2147483647 positive Ganzzahlen. Wenn Sie zwei davon auswählen, bei denen die Reihenfolge keine Rolle spielt und die sich wiederholen, erhalten Sie 2305843008139952128 Kombinationen. Dies passt nicht gut in den Satz von 32-Bit-Ganzzahlen.
Sie können diese Zuordnung jedoch in 61 Bit anpassen. Die Verwendung einer 64-Bit-Ganzzahl ist wahrscheinlich am einfachsten. Setzen Sie das hohe Wort auf die kleinere Ganzzahl und das niedrige Wort auf die größere.
quelle
Angenommen, Sie haben eine 32-Bit-Ganzzahl. Warum nicht einfach A in die erste 16-Bit-Hälfte und B in die andere verschieben?
Abgesehen davon, dass dies so platzsparend wie möglich und kostengünstig zu berechnen ist, besteht ein wirklich cooler Nebeneffekt darin, dass Sie Vektormathematik für die gepackte Zahl durchführen können.
quelle
Lassen Sie uns zwei Zahlen B und C haben, die sie in eine einzige Zahl A codieren
A = B + C * N.
wo
B = A% N = B.
C = A / N = C.
quelle
Bei positiven ganzen Zahlen A und B sei D = Anzahl der Stellen, die A hat, und E = Anzahl der Stellen, die B hat. Das Ergebnis kann eine Verkettung von D, 0, E, 0, A und B sein.
Beispiel: A = 300, B = 12. D = 3, E = 2 Ergebnis = 302030012. Dies nutzt die Tatsache aus, dass die einzige Zahl, die mit 0 beginnt, 0 ist.
Pro: Einfach zu kodieren, leicht zu dekodieren, lesbar, signifikante Ziffern können zuerst verglichen werden, Vergleichsmöglichkeit ohne Berechnung, einfache Fehlerprüfung.
Nachteile: Die Größe der Ergebnisse ist ein Problem. Aber das ist in Ordnung, warum speichern wir sowieso unbegrenzte Ganzzahlen in einem Computer?
quelle
Wenn Sie mehr Kontrolle wünschen, z. B. X-Bits für die erste Nummer und Y-Bits für die zweite Nummer zuweisen, können Sie diesen Code verwenden:
Ich benutze insgesamt 32 Bit. Die Idee hier ist, dass Sie dies tun können, wenn Sie zum Beispiel möchten, dass die erste Nummer bis zu 10 Bit und die zweite Nummer bis zu 12 Bit beträgt:
Jetzt können Sie in
num_a
der maximalen Anzahl2^10 - 1 = 1023
und imnum_b
Maximalwert von speichern2^12 - 1 = 4095
.So stellen Sie den Wert für num A und num B ein:
Jetzt
bnum
sind alle Bits (insgesamt 32 Bits. Sie können den Code so ändern, dass 64 Bits verwendet werden). So erhalten Sie num a:Um num b zu bekommen:
BEARBEITEN:
bnum
kann in der Klasse gespeichert werden. Ich habe es nicht getan, weil ich den Code aufgrund meiner eigenen Bedürfnisse geteilt habe und hoffe, dass er hilfreich sein wird.Vielen Dank für die Quelle: https://www.geeksforgeeks.org/extract-k-bits-given-position-number/ für die Funktion zum Extrahieren von Bits und danke auch für die
mouviciel
Antwort in diesem Beitrag. Mit diesen Quellen konnte ich eine fortgeschrittenere Lösung findenquelle