Zuordnen von zwei ganzen Zahlen zu einer einzigen und deterministischen Art

Cantor-pairing-Funktion ist wirklich einer der besseren gibt, bedenkt man seine einfache, schnell und Platz sparend, aber es ist sogar noch etwas besser veröffentlicht bei Wolfram von Matthew Szudzik, hier. Die Beschränkung des Cantor-pairing-Funktion (relativ) ist, dass der Bereich der codierten Ergebnisse, die nicht immer innerhalb der Grenzen einer 2N bit-Ganzzahl, wenn die Eingänge sind zwei N bit-Ganzzahlen. Das ist, wenn meine Eingaben sind zwei 16 - bit-Integer reicht von 0 to 2^16 -1dann gibt es 2^16 * (2^16 -1) Kombinationen von Produktionsfaktoren möglich, so dass durch die offensichtliche Schublade Prinzipbenötigen wir eine output-Größe, die mindestens 2^16 * (2^16 -1)die gleich 2^32 - 2^16 oder in anderen Worten, eine Karte von 32 bit-zahlen sollte machbar sein ideal. Dies kann nicht von wenig praktischer Bedeutung in der Programmierung Welt.

Cantor-pairing-Funktion:

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

Das mapping für zwei maximal die meisten 16-bit-Integer (65535, 65535) 8589803520, die, wie Sie sehen, kann nicht fit sein in 32 bit.

Geben Sie Szudzik die Funktion:

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

Mapping für (65535, 65535), werden nun 4294967295, die, wie Sie sehen, ist ein 32 bit (0 bis 2^32 -1) integer. Dies ist, wo diese Lösung ist ideal, es ist einfach, nutzt jeden einzelnen Punkt in diesem Raum, so dass nichts kann mehr Raum bekommen effiziente.

Nun, in Anbetracht der Tatsache, dass wir in der Regel mit dem deal unterzeichnet Implementierungen von zahlen in verschiedenen Größen Sprachen/frameworks, betrachten wir signed 16 - bit-Integer reicht von -(2^15) to 2^15 -1 (später werden wir sehen, wie Sie erweitern auch den Ausgang zu überspannen signed range). Da a und b müssen positiv sein, Sie reichen von 0 to 2^15 - 1.

Cantor-pairing-Funktion:

Das mapping für zwei maximal die meisten 16-bit-Ganzzahlen mit Vorzeichen (32767, 32767) werden 2147418112 die nur kurze maximaler Wert für signed 32 bit integer.

Nun Szudzik die Funktion:

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

Let ' s Konto für negative Ganzzahlen. Das ist über die ursprüngliche Frage, ich weiß, aber gerade die Ausarbeitung zu helfen, die künftigen Besucher.

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 die Int64. 64-bit-Ausgabe für 16-bit-Eingänge können so unverzeihlich!!

Szudzik die 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 unsigned-Bereich oder 64 bit für signed range, aber immer noch besser.

Nun all dies, während die Ausgabe wurde immer positiv. In der Welt unterzeichnet, es wird noch mehr Platz sparen, wenn wir überführen könnte die Hälfte der Leistung, um negativen Achse. Sie es tun könnten, wie dies für Szudzik:

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: Nach der Anwendung ein Gewicht von 2 zu der die Eingänge und die Funktion, die ich teilen Sie dann die Ausgabe durch zwei und nehmen einige von Ihnen an, negative Achse durch Multiplikation mit -1.

Sehen die Ergebnisse, die für alle Eingaben in der Palette der unterzeichneten 16 bit-Zahl, die Ausgabe liegt innerhalb der Grenzen einer signierten 32 bit-Ganzzahl, die ist cool. Ich bin mir nicht sicher wie Sie gehen über den gleichen Weg für die Cantor-pairing-Funktion, aber nicht versuchen, so viel wie es ist nicht so effizient. Darüber hinaus weitere Berechnungen beteiligt Cantor-pairing-Funktion bedeutet, dass Sie langsamer zu.

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 können die Grenzwerte überschreiten von 2N - Ganzzahl mit Vorzeichen, die ich verwendet habe 4N integer-Typ (die Letzte division durch 2 bringt wieder das Ergebnis zu 2N).

Den link habe ich auf die Alternative Lösung, der schön zeigt einen graph der Funktion unter Verwendung jeder einzelne Punkt im Raum. Seine erstaunlich, zu sehen, dass konnte man eindeutig Kodieren, ein paar Koordinaten auf eine einzelne Zahl reversibel! Magische Welt der zahlen!!

InformationsquelleAutor der Antwort nawfal

Ist das überhaupt möglich?

Sie sind die Kombination von zwei Ganzzahlen. Beide haben den Bereich -2,147,483,648 bis 2,147,483,647 aber Sie nehmen nur das positive.
Das macht 2147483647^2 = 4,61169 E+18 Kombinationen.
Da jede Kombination muss eindeutig sein UND im Ergebnis eine ganze Zahl, Sie müssen irgendeine Art von magischen integer enthalten kann, diese Menge von zahlen.

Oder ist meine Logik falsch?

InformationsquelleAutor der Antwort Boris Callens

Lassen Anzahl a der erste, der b die zweite. Lassen Sie p werden die a+1-te Primzahl, q werden die b+1-te Primzahl

Dann, das Ergebnis ist pqwenn a<b, oder 2pq wenn a>b. Wenn a=blass es sein p^2.

InformationsquelleAutor der Antwort ASk

Für positive Ganzzahlen als Argumente und where-argument ist die Reihenfolge egal:

1. Hier ist ein ungeordnete pairing-Funktion:

   <x, y> = x * y + trunc((|x - y| - 1)^2 /4) = <y, x>
   

2. Für x ≠ y, hier ist ein einzigartige ungeordnete pairing-Funktion:

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

InformationsquelleAutor der Antwort ma11hew28

Prüfen: http://en.wikipedia.org/wiki/Pigeonhole_principle. Wenn A, B und C sind vom gleichen Typ, es kann nicht getan werden. Wenn A und B sind 16-bit-Ganzzahlen, und C ist 32-bit, dann können Sie einfach schalten.

In der Natur der Hash-algorithmen ist, dass Sie nicht geben Sie einen eindeutigen hash für jeden anderen input.

InformationsquelleAutor der Antwort Groo

Hier ist eine Erweiterung der @DoctorJ 's code ankten ganzen zahlen, basierend auf der Methode von @nawfal. 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

InformationsquelleAutor der Antwort NStarman

Wie über etwas viel einfacheres: Gegeben zwei zahlen, A und B lassen str der Verkettung: 'A' + ';' + 'B'. Dann lassen Sie die Ausgabe hash(str.). Ich weiß, dass dies nicht eine mathematische Antwort, aber ein einfaches python (die hat eine eingebaute hash-Funktion) Skript sollte den job tun.

InformationsquelleAutor der Antwort Madhav Nakar