Zuordnung von zwei Ganzzahlen zu einer auf einzigartige und deterministische Weise

234

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.

Schaden
quelle
10
Sie sollten klären, ob Sie Ganzzahlen in Software oder Ganzzahlen in Mathematik meinen. In der Software wählen Sie einen beliebigen Ganzzahltyp aus, der eine Größe hat, sodass Sie eine endliche Anzahl von ihnen haben. Daher gibt es keine Lösung (es sei denn, Ihre Eingabedaten liegen garantiert in einem bestimmten Bereich und Ihre Ausgabe kann es sein eine ganze Zahl). In Mathe siehe ASks Lösung.
Daniel Daranas
Ich spreche von begrenzten ganzen Zahlen in einem niedrigen, positiven Bereich. Sagen Sie 0 bis 10.000
Schaden
27
@harm: Also wie wäre es einfach 10,001*A + B?
BlueRaja - Danny Pflughoeft
2
Ich habe diese PHP-Funktionen gefunden: gist.github.com/hannesl/8031402
cakan
Wenn die Reihenfolge keine Rolle spielt, zB: (3,12) & (12,3) das gleiche Ergebnis liefern, verwende ich "A + B" + "A * B"
Sodj

Antworten:

233

Sie suchen nach einem bijektiven NxN -> NMapping. 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 :

pi (k1, k2) = 1/2 (k1 + k2) (k1 + k2 + 1) + k2

Drei Bemerkungen:

  • Wie andere deutlich gemacht haben, werden Sie möglicherweise bald beliebig große Ganzzahlen (Bignums) benötigen, wenn Sie eine Pairing-Funktion implementieren möchten.
  • Wenn Sie nicht zwischen den Paaren (a, b) und (b, a) unterscheiden möchten, sortieren Sie a und b, bevor Sie die Paarungsfunktion anwenden.
  • Eigentlich habe ich gelogen. Sie suchen nach einem bijektiven ZxZ -> NMapping. Die Cantor-Funktion funktioniert nur bei nicht negativen Zahlen. Dies ist jedoch kein Problem, da es einfach ist, eine Bijektion f : Z -> Nwie folgt zu definieren :
    • f (n) = n * 2, wenn n> = 0
    • f (n) = -n * 2 - 1, wenn n <0 ist
Stephan202
quelle
13
+1 Ich denke, dies ist die richtige Antwort für unbegrenzte ganze Zahlen.
Unbekannt
4
Wie kann ich wieder den Wert von k1, k2 erhalten?
MinuMaster
3
@MinuMaster: Dies wird im selben Wikipedia-Artikel unter Invertieren der Cantor-Pairing-Funktion beschrieben .
Stephan202
4
Siehe auch Szudziks Funktion, die unten durch newfal erklärt wird.
OliJG
1
Während dies für unbegrenzte Ganzzahlen korrekt ist, ist es für begrenzte Ganzzahlen nicht am besten. Ich denke, @ blue-rajas Kommentar ist bei weitem am sinnvollsten.
Kardasis
225

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 2NBit-Ganzzahl bleibt, wenn die Eingaben zwei NBit-Ganzzahlen sind. Das heißt, wenn meine Eingaben zwei 16Bit-Ganzzahlen im Bereich von sind 0 to 2^16 -1, sind 2^16 * (2^16 -1)Kombinationen von Eingaben möglich. Nach dem offensichtlichen Pigeonhole-Prinzip benötigen wir also mindestens eine Ausgabe mit einer Größe 2^16 * (2^16 -1), die gleich 2^32 - 2^16oder mit anderen Worten einer Karte von ist32Bitnummern sollten idealerweise machbar sein. Dies ist in der Programmierwelt möglicherweise nicht von geringer praktischer Bedeutung.

Cantor-Pairing-Funktion :

(a + b) * (a + b + 1) / 2 + a; where a, b >= 0

Die Zuordnung für zwei maximal 16-Bit-Ganzzahlen (65535, 65535) lautet 8589803520, was, wie Sie sehen, nicht in 32-Bit passt.

Geben Sie die Funktion von Szudzik ein :

a >= b ? a * a + a + b : a + b * b;  where a, b >= 0

Die Zuordnung für (65535, 65535) lautet jetzt 4294967295, was, wie Sie sehen, eine 32-Bit-Ganzzahl (0 bis 2 ^ 32 -1) ist. Hier ist diese Lösung ideal. Sie nutzt einfach jeden einzelnen Punkt in diesem Raum, sodass nichts platzsparender werden kann.


Angesichts der Tatsache, dass wir uns normalerweise mit den signierten Implementierungen von Zahlen unterschiedlicher Größe in Sprachen / Frameworks befassen, betrachten wir signed 16Bit-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). Da aund bmüssen positiv sein, reichen sie von 0 to 2^15 - 1.

Cantor-Pairing-Funktion :

Die Zuordnung für zwei maximal 16-Bit-Ganzzahlen mit Vorzeichen (32767, 32767) lautet 2147418112, was knapp unter dem Maximalwert für vorzeichenbehaftete 32-Bit-Ganzzahlen liegt.

Nun Szudziks Funktion :

(32767, 32767) => 1073741823, viel kleiner.

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 :

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
(A + B) * (A + B + 1) / 2 + A;

(-32768, -32768) => 8589803520, das ist Int64. 64-Bit-Ausgabe für 16-Bit-Eingänge kann so unverzeihlich sein !!

Szudziks Funktion :

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
A >= B ? A * A + A + B : A + B * B;

(-32768, -32768) => 4294967295, 32 Bit für vorzeichenlosen Bereich oder 64 Bit für vorzeichenbehafteten Bereich, aber immer noch besser.

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:

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
C = (A >= B ? A * A + A + B : A + B * B) / 2;
a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;

(-32768, 32767) => -2147483648

(32767, -32768) => -2147450880

(0, 0) => 0 

(32767, 32767) => 2147418112

(-32768, -32768) => 2147483647

Was ich tue: Nachdem ich 2den 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 16Bitnummer liegt die Ausgabe innerhalb der Grenzen einer vorzeichenbehafteten 32Bit-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.

public static long PerfectlyHashThem(int a, int b)
{
    var A = (ulong)(a >= 0 ? 2 * (long)a : -2 * (long)a - 1);
    var B = (ulong)(b >= 0 ? 2 * (long)b : -2 * (long)b - 1);
    var C = (long)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}

public static int PerfectlyHashThem(short a, short b)
{
    var A = (uint)(a >= 0 ? 2 * a : -2 * a - 1);
    var B = (uint)(b >= 0 ? 2 * b : -2 * b - 1);
    var C = (int)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}

Da die Zwischenberechnungen die Grenzen der 2Nvorzeichenbehafteten Ganzzahl überschreiten können , habe ich den 4NGanzzahltyp verwendet (die letzte Division durch 2bringt das Ergebnis zurück zu 2N).

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 !!

nawfal
quelle
5
Was wäre die modifizierte Unhash-Funktion für vorzeichenbehaftete Ganzzahlen?
Arets Paeglis
7
Diese Antwort verwirrt mich. Wenn Sie einer einzelnen Zahl (0,0)zuordnen möchten (65535,65535), a<<16 + bist dies in jeder Hinsicht besser (schneller, einfacher, verständlicher, offensichtlicher) . Wenn Sie möchten , (-32768,-32768)um (327687,327687)zuerst statt, 32768 nur Gegenstand.
BlueRaja - Danny Pflughoeft
2
@ BlueRaja-DannyPflughoeft du hast recht. Meine Antwort wäre gültig, wenn die Reichweite nicht begrenzt oder unbekannt ist. Ich werde es aktualisieren. Ich hatte es geschrieben, bevor mir das Limit wichtig war. Das Bearbeiten dieser Antwort ist mir schon lange in den Sinn gekommen. Ich werde bald Zeit finden.
Nawfal
Funktioniert die Funktion von Szudzik für Kombinationen oder Permutationen? Es scheint Permutationen zu sein, oder? Wenn ich für die Kombination verwenden möchte, kann ich dann nur die IF- und Else-Teile des Algorithmus entfernen?
Jamie Marshall
Hier ist eine Python-Implementierung von Szudziks Funktion, die auf Tupel beliebiger Länge verallgemeinert ist: gitlab.com/snippets/32559
Doctor J
47

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):

int combine(short A, short B)
{
    return A<<16 | B;
}

short getA(int C)
{
    return C>>16;
}

short getB(int C)
{
    return C & 0xFFFF;
}
Mouviciel
quelle
3
combine()sollte return (unsigned short)(A<<16) | (unsigned short)(B); also , dass negative Zahlen richtig verpackt werden können.
Andy
2
@ Andy A<<16wird Grenzen überschreiten . Es sollte seinreturn (unsigned int)(A<<16) | (unsigned short)(B);
DanSkeel
15

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?

Boris Callens
quelle
+1 Das denke ich auch (obwohl ich die Berechnung durchgeführt habe, dass die Reihenfolge von A und B keine Rolle spielt)
lc.
4
Ja, Ihre Logik ist nach dem Pigeonhole-Prinzip korrekt. Leider hat der Fragesteller nicht angegeben, ob die Ganzzahl begrenzt ist oder nicht.
Unbekannt
Ja, ich hatte diesen nachträglichen Gedanken auch, aber ich dachte, die Botschaft ist im Wesentlichen dieselbe, also habe ich mich nicht darum gekümmert, sie neu zu berechnen.
Boris Callens
Außerdem wurde mir gerade klar, dass ich meine Lehrbücher zur Zufallsberechnung (wörtliche Übersetzung aus dem Niederländischen) wieder aufnehmen sollte.
Boris Callens
2
@ Boris: Kansrekening ist "Wahrscheinlichkeitstheorie".
Stephan202
8

Die mathematische Standardmethode für positive ganze Zahlen besteht darin, die Eindeutigkeit der Primfaktorisierung zu verwenden.

f( x, y ) -> 2^x * 3^y

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, xund yindem Sie Flags mit Potenzen von 5 und 7 Termen codieren.

z.B

f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)
CB Bailey
quelle
Die Mathematik ist in Ordnung. Aber wie Boris sagt, wenn Sie dies als Computerprogramm ausführen möchten, müssen Sie die Endlichkeit der Maschine berücksichtigen. Der Algorithmus funktioniert korrekt für eine Teilmenge der Ganzzahlen, die in der jeweiligen Maschine dargestellt werden können.
Yuval F
2
Ich habe dies in meinem zweiten Absatz angegeben. Die Tags auf der Frage geben "Algorithmus", "mathematisch" und "deterministisch" an, keine bestimmte Sprache. Der Eingabebereich ist möglicherweise nicht begrenzt und die Umgebung hat möglicherweise einen unbegrenzten ganzzahligen Typ 'bigint'.
CB Bailey
8

Die Zahl asei die erste, bdie zweite. Sei pdie a+1-te Primzahl, qsei die b+1-te Primzahl

Dann ist das Ergebnis pq, ob a<b,oder 2pqob a>b. Wenn a=b, lass es sein p^2.

Fragen
quelle
4
Ich bezweifle, dass Sie eine NP-Lösung wollen.
user44242
1
Ergibt dies nicht das gleiche Ergebnis für a = 5, b = 14 und a = 6, b = 15?
Lieven Keersmaekers
3
Zwei Produkte mit zwei verschiedenen Primzahlen können nicht dasselbe Ergebnis haben (eindeutige Primfaktorzerlegung). A = 5, b = 14 -> Ergebnis ist 13 * 47 = 611 a = 6, b = 15 -> Ergebnis ist 17 * 53 = 901
Fragen Sie
4

Es ist nicht so schwer, ein Mapping zu erstellen:

   1 2 3 4 5 Verwenden Sie diese Zuordnung, wenn (a, b)! = (B, a)
1 0 1 3 6 10
2 2 4 7 11 16
3 5 8 12 17 23
4 9 13 18 24 31
5 14 19 25 32 40

   1 2 3 4 5 Verwenden Sie diese Zuordnung, wenn (a, b) == (b, a) (Spiegel)
1 0 1 2 4 6
2 1 3 5 7 10
3 2 5 8 11 14
4 4 8 11 15 19
5 6 10 14 19 24


    0 1 -1 2 -2 Verwenden Sie diese Option, wenn Sie negativ / positiv benötigen
 0 0 1 2 4 6
 1 1 3 5 7 10
-1 2 5 8 11 14
 2 4 8 11 15 19
-2 6 10 14 19 24

Etwas schwieriger ist es, herauszufinden, wie man den Wert für ein beliebiges a, b erhält.

Delfin
quelle
4

f(a, b) = s(a+b) + a, wo s(n) = n*(n+1)/2

  • Dies ist eine Funktion - sie ist deterministisch.
  • Es ist auch injektiv - f bildet verschiedene Werte für verschiedene (a, b) Paare ab. Sie können dies anhand der Tatsache beweisen : s(a+b+1)-s(a+b) = a+b+1 < a.
  • Es werden recht kleine Werte zurückgegeben - gut, wenn Sie es für die Array-Indizierung verwenden möchten, da das Array nicht groß sein muss.
  • Es ist cachefreundlich - wenn zwei (a, b) Paare nahe beieinander liegen, ordnet f ihnen Zahlen zu, die nahe beieinander liegen (im Vergleich zu anderen Methoden).

Ich habe nicht verstanden, was du meinst mit:

sollte immer eine ganze Zahl entweder auf der positiven oder der negativen Seite von ganzen Zahlen ergeben

Wie kann ich (größer als), (kleiner als) Zeichen in dieses Forum schreiben?

libeako
quelle
2
Größer als und kleiner als Zeichen sollten innerhalb gut funktionieren backtick escapes.
TRiG
Dies entspricht der Cantor-Pairing-Funktion und funktioniert daher nicht mit negativen Ganzzahlen.
Davor Josipovic
4

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:

#define RANGE_MIN 0
#define RANGE_MAX 10000

unsigned int merge(unsigned int x, unsigned int y)
{
    return (x * (RANGE_MAX - RANGE_MIN + 1)) + y;
}

void split(unsigned int v, unsigned int &x, unsigned int &y)
{
    x = RANGE_MIN + (v / (RANGE_MAX - RANGE_MIN + 1));
    y = RANGE_MIN + (v % (RANGE_MAX - RANGE_MIN + 1));
}

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 :)

bdonlan
quelle
Ist dies zufällig für Schwimmer möglich?
Lukas
4

Für positive ganze Zahlen als Argumente und wo die Reihenfolge der Argumente keine Rolle spielt:

  1. Hier ist eine ungeordnete Pairing-Funktion :

    <x, y> = x * y + trunc((|x - y| - 1)^2 / 4) = <y, x>
    
  2. Für x ≠ y gibt es eine einzigartige ungeordnete Paarungsfunktion :

    <x, y> = if x < y:
               x * (y - 1) + trunc((y - x - 2)^2 / 4)
             if x > y:
               (x - 1) * y + trunc((x - y - 2)^2 / 4)
           = <y, x>
    
ma11hew28
quelle
3

Ü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.

Groo
quelle
2

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.

#!/usr/bin/env python
from numbers import Integral    

def tuple_to_int(tup):
    """:Return: the unique non-negative integer encoding of a tuple of non-negative integers."""
    if len(tup) == 0:  # normally do if not tup, but doesn't work with np
        raise ValueError('Cannot encode empty tuple')
    if len(tup) == 1:
        x = tup[0]
        if not isinstance(x, Integral):
            raise ValueError('Can only encode integers')
        return x
    elif len(tup) == 2:
        # print("len=2")
        x, y = tuple_to_int(tup[0:1]), tuple_to_int(tup[1:2])  # Just to validate x and y

        X = 2 * x if x >= 0 else -2 * x - 1  # map x to positive integers
        Y = 2 * y if y >= 0 else -2 * y - 1  # map y to positive integers
        Z = (X * X + X + Y) if X >= Y else (X + Y * Y)  # encode

        # Map evens onto positives
        if (x >= 0 and y >= 0):
            return Z // 2
        elif (x < 0 and y >= 0 and X >= Y):
            return Z // 2
        elif (x < 0 and y < 0 and X < Y):
            return Z // 2
        # Map odds onto negative
        else:
            return (-Z - 1) // 2
    else:
        return tuple_to_int((tuple_to_int(tup[:2]),) + tuple(tup[2:]))  # ***speed up tuple(tup[2:])?***


def int_to_tuple(num, size=2):
    """:Return: the unique tuple of length `size` that encodes to `num`."""
    if not isinstance(num, Integral):
        raise ValueError('Can only encode integers (got {})'.format(num))
    if not isinstance(size, Integral) or size < 1:
        raise ValueError('Tuple is the wrong size ({})'.format(size))
    if size == 1:
        return (num,)
    elif size == 2:

        # Mapping onto positive integers
        Z = -2 * num - 1 if num < 0 else 2 * num

        # Reversing Pairing
        s = isqrt(Z)
        if Z - s * s < s:
            X, Y = Z - s * s, s
        else:
            X, Y = s, Z - s * s - s

        # Undoing mappint to positive integers
        x = (X + 1) // -2 if X % 2 else X // 2  # True if X not divisible by 2
        y = (Y + 1) // -2 if Y % 2 else Y // 2  # True if Y not divisible by 2

        return x, y

    else:
        x, y = int_to_tuple(num, 2)
        return int_to_tuple(x, size - 1) + (y,)


def isqrt(n):
    """":Return: the largest integer x for which x * x does not exceed n."""
    # Newton's method, via http://stackoverflow.com/a/15391420
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x
NStarman
quelle
2

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.

Madhav Nakar
quelle
2
aber (8,11) und (81,1) werden auf dieselbe Nummer 811 abgebildet
Leevi L
Das ist ein guter Punkt. Sie können dieses Problem beheben, indem Sie einfach ein Symbol in die Mitte einfügen. Also für (8, 11) Hash die Zeichenfolge "8-11" und für (81, 1) Hash die Zeichenfolge "81-1". Also im Allgemeinen für (A, B) Hash die Zeichenfolge "AB". (Ich weiß, es klingt hacky, aber es sollte funktionieren).
Madhav Nakar
Es ist auch falsch, weil diese Aufgabe darin besteht, zwei Ganzzahlen einer neuen Ganzzahl zuzuordnen, nicht einer Zeichenfolge mit einem Symbol
Leevi L
Ich komme eher aus einer CS-Perspektive als aus einer mathematischen (für mathematische Lösungen siehe obige Antworten). Ich nehme zwei ganze Zahlen und mache sie zu einer Zeichenfolge, wenn sie dann in eine ganze Zahl umgewandelt werden. Im Wesentlichen ja, ich ordne zwei Ganzzahlen einer neuen zu.
Madhav Nakar
1

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.

lc.
quelle
1

Angenommen, Sie haben eine 32-Bit-Ganzzahl. Warum nicht einfach A in die erste 16-Bit-Hälfte und B in die andere verschieben?

def vec_pack(vec):
    return vec[0] + vec[1] * 65536;


def vec_unpack(number):
    return [number % 65536, number // 65536];

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.

a = vec_pack([2,4])
b = vec_pack([1,2])

print(vec_unpack(a+b)) # [3, 6] Vector addition
print(vec_unpack(a-b)) # [1, 2] Vector subtraction
print(vec_unpack(a*2)) # [4, 8] Scalar multiplication
Stuffe
quelle
0

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.

Ankur Chauhan
quelle
2
Wie wählen Sie N, um diese Darstellung einzigartig zu machen? Wenn Sie dieses Problem lösen, wie unterscheidet sich diese Antwort von den oben genannten?
Beschneiden Sie den
Sie sollten hinzufügen, dass N größer sein muss als B und C.
Radoslav Stoyanov
0

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?

Ban Piao
quelle
0

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:

class NumsCombiner
{

    int num_a_bits_size;
    int num_b_bits_size;

    int BitsExtract(int number, int k, int p)
    {
        return (((1 << k) - 1) & (number >> (p - 1)));
    }

public:
    NumsCombiner(int num_a_bits_size, int num_b_bits_size)
    {
        this->num_a_bits_size = num_a_bits_size;
        this->num_b_bits_size = num_b_bits_size;
    }

    int StoreAB(int num_a, int num_b)
    {
        return (num_b << num_a_bits_size) | num_a;
    }

    int GetNumA(int bnum)
    {
        return BitsExtract(bnum, num_a_bits_size, 1);
    }

    int GetNumB(int bnum)
    {
        return BitsExtract(bnum, num_b_bits_size, num_a_bits_size + 1);
    }
};

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:

NumsCombiner nums_mapper(10/*bits for first number*/, 12/*bits for second number*/);

Jetzt können Sie in num_ader maximalen Anzahl 2^10 - 1 = 1023und im num_bMaximalwert von speichern 2^12 - 1 = 4095.

So stellen Sie den Wert für num A und num B ein:

int bnum = nums_mapper.StoreAB(10/*value for a*/, 12 /*value from b*/);

Jetzt bnumsind alle Bits (insgesamt 32 Bits. Sie können den Code so ändern, dass 64 Bits verwendet werden). So erhalten Sie num a:

int a = nums_mapper.GetNumA(bnum);

Um num b zu bekommen:

int b = nums_mapper.GetNumB(bnum);

BEARBEITEN: bnumkann 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 mouvicielAntwort in diesem Beitrag. Mit diesen Quellen konnte ich eine fortgeschrittenere Lösung finden

gil123
quelle