Mapowanie dwóch liczb całkowitych do jednej w unikalny i deterministyczny sposób

Wyobraź sobie dwie dodatnie liczby całkowite A i B. Chcę połączyć te dwie w jedną liczbę całkowitą C.

Nie może być innych liczb całkowitych D i E, które łączą się z C. Tak więc łączenie ich z operatorem dodawania nie działa. Np. 30 + 10 = 40 = 40 + 0 = 39 + 1 Nie działa też konkatynacja. Np. „31” + „2” = 312 = „3” + „12”

Ta kombinacja operacji powinna również być deterministyczna (zawsze dawać ten sam wynik przy tych samych danych wejściowych) i zawsze powinna dawać liczbę całkowitą po stronie dodatniej lub ujemnej liczb całkowitych.

Szukasz NxN -> Nmapowania bijective . Służą one np . Dovetailing . Zapoznaj się z tym plikiem PDF, aby uzyskać wprowadzenie do tak zwanych funkcji parowania . Wikipedia wprowadza określoną funkcję parowania, a mianowicie funkcję parowania Cantor :

Trzy uwagi:

• Jak wyjaśnili inni, jeśli planujesz zaimplementować funkcję parowania, może wkrótce okazać się, że potrzebujesz dowolnie dużych liczb całkowitych (bignów).
• Jeśli nie chcesz rozróżniać par (a, b) i (b, a), posortuj aib przed zastosowaniem funkcji parowania.
• Właściwie to skłamałem. Szukasz ZxZ -> Nmapowania bijective . Funkcja Cantora działa tylko na liczbach nieujemnych. Nie stanowi to jednak problemu, ponieważ łatwo zdefiniować bijection f : Z -> N, tak jak poniżej :
  • f (n) = n * 2, jeśli n> = 0
  • f (n) = -n * 2-1, jeśli n <0

Funkcja parowania kantora jest naprawdę jedną z lepszych, ponieważ jest prosta, szybka i zajmuje mało miejsca, ale jest coś jeszcze lepiej opublikowanego w Wolfram przez Matthew Szudzika tutaj . Ograniczeniem funkcji parowania Cantora (względnie) jest to, że zakres zakodowanych wyników nie zawsze mieści się w granicach 2Nbitowej liczby całkowitej, jeśli dane wejściowe są dwiema Nliczbami całkowitymi. Oznacza to, że jeśli moje dane wejściowe są 16liczbami całkowitymi od dwóch bitów 0 to 2^16 -1, to możliwe są 2^16 * (2^16 -1)kombinacje danych wejściowych, więc zgodnie z oczywistą zasadą Pigeonhole potrzebujemy wyjścia o wielkości co najmniej 2^16 * (2^16 -1)równej 2^32 - 2^16lub innymi słowy mapie32idealnie powinny być możliwe liczby bitowe. To może nie mieć praktycznego znaczenia w świecie programowania.

Funkcja parowania kantora :

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

Odwzorowanie dla dwóch maksymalnie 16-bitowych liczb całkowitych (65535, 65535) będzie wynosić 8589803520, który, jak widać, nie mieści się w 32 bitach.

Wejdź w funkcję Szudzika :

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

Mapowanie dla (65535, 65535) będzie teraz 4294967295, co jak widać jest liczbą całkowitą 32-bitową (od 0 do 2 ^ 32 -1). Właśnie tam to rozwiązanie jest idealne, po prostu wykorzystuje każdy punkt w tej przestrzeni, więc nic nie może zapewnić więcej miejsca.

Teraz, biorąc pod uwagę fakt, że zwykle mamy do czynienia z podpisanymi implementacjami liczb o różnych rozmiarach w językach / frameworkach, rozważmy signed 16liczby całkowite od - -(2^15) to 2^15 -1(później zobaczymy, jak rozszerzyć nawet wyjście do zakresu ponad podpisany zakres). Od ai bmuszą być pozytywne, różnią się od 0 to 2^15 - 1.

Funkcja parowania kantora :

Odwzorowanie dla dwóch maksymalnie 16-bitowych liczb całkowitych ze znakiem (32767, 32767) będzie wynosić 2147418112, czyli niewiele więcej niż maksymalna wartość dla 32-bitowej liczby całkowitej ze znakiem.

Teraz funkcja Szudzika :

(32767, 32767) => 1073741823, znacznie mniejszy ..

Rozważmy liczby całkowite ujemne. To jest poza pierwotnym pytaniem, które znam, ale po prostu opracowaniem, aby pomóc przyszłym użytkownikom.

Funkcja parowania kantora :

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, który jest Int64. 64-bitowy sygnał wyjściowy dla 16-bitowych sygnałów wejściowych może być tak nieprzebaczalny !!

Funkcja Szudzika :

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, który jest 32-bitowy dla zakresu bez znaku lub 64-bitowy dla zakresu ze znakiem, ale wciąż lepszy.

Wszystko to, podczas gdy wyniki zawsze były pozytywne. W podpisanym świecie zaoszczędzenie miejsca zajmowałoby jeszcze więcej, gdybyśmy mogli przenieść połowę mocy wyjściowej na oś ujemną . Możesz to zrobić w ten sposób dla Szudzika:

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

Co robię: po nałożeniu ciężaru 2na dane wejściowe i przejściu przez funkcję dzielę wyjście przez dwa i przenoszę niektóre z nich na oś ujemną, mnożąc przez -1.

Zobacz wyniki, dla dowolnego wejścia w zakresie liczby 16bitów ze znakiem , wyjście leży w granicach 32fajnej liczby całkowitej ze znakiem . Nie jestem pewien, jak postąpić w ten sam sposób dla funkcji parowania Cantor, ale nie próbowałem tyle, ile nie jest tak wydajna. Co więcej, więcej obliczeń związanych z funkcją parowania Cantora oznacza również jego spowolnienie .

Oto implementacja C #.

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

Ponieważ obliczenia pośrednie mogą przekraczać limity liczby 2Ncałkowitej ze znakiem, użyłem 4Ntypu liczby całkowitej (ostatni podział przez 2powoduje powrót wyniku 2N).

Link, który podałem w alternatywnym rozwiązaniu, ładnie przedstawia wykres funkcji wykorzystującej każdy pojedynczy punkt w przestrzeni. To niesamowite, że możesz jednoznacznie zakodować parę współrzędnych w pojedynczą liczbę w sposób odwracalny! Magiczny świat liczb !!

Jeśli A i B można wyrazić za pomocą 2 bajtów, możesz je połączyć na 4 bajtach. Połóż A na najbardziej znaczącej połowie, a B na najmniej znaczącej połowie.

W języku C daje to (przy założeniu sizeof (short) = 2 i 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;
}

Czy to w ogóle możliwe?
Łączycie dwie liczby całkowite. Oba mają zakres od -2 147 483 648 do 2 147 483 647, ale weźmiesz tylko pozytywy. To sprawia, że ​​2147483647 ^ 2 = 4,61169E + 18 kombinacji. Ponieważ każda kombinacja musi być unikalna ORAZ wynikać z liczby całkowitej, będziesz potrzebować jakiejś magicznej liczby całkowitej, która może zawierać taką liczbę liczb.

Czy moja logika jest wadliwa?

Standardowym matematycznym sposobem na dodatnie liczby całkowite jest użycie unikatowości faktoryzacji pierwotnej.

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

Minusem jest to, że obraz ma tendencję do rozciągania się na całkiem szeroki zakres liczb całkowitych, więc jeśli chodzi o wyrażenie odwzorowania w algorytmie komputerowym, możesz mieć problemy z wyborem odpowiedniego typu dla wyniku.

Możesz to zmienić, aby radzić sobie z negatywnymi xiy kodując flagi o potęgach 5 i 7 terminów.

na przykład

f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)

Niech liczba abędzie pierwszą, bdrugą. Niech pbędzie a+1-tą liczbą pierwszą, qbyć b+1-tą liczbą pierwszą

Zatem wynikiem jest pq, jeśli a<b,lub 2pqjeśli a>b. Jeśli tak a=b, niech tak będzie p^2.

Stworzenie mapowania nie jest trudne:

   1 2 3 4 5 użyj tego mapowania, jeśli (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 użyj tego mapowania, jeśli (a, b) == (b, a) (mirror)
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 użyj tego, jeśli potrzebujesz negatywnego / pozytywnego
 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

Ustalenie, w jaki sposób uzyskać wartość dla dowolnego a, b, jest nieco trudniejsze.

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

• To funkcja - jest deterministyczna.
• Jest także iniekcyjny - f odwzorowuje różne wartości dla różnych par (a, b). Można to udowodnić wykorzystując fakt: s(a+b+1)-s(a+b) = a+b+1 < a.
• Zwraca dość małe wartości - dobre, jeśli zamierzasz użyć go do indeksowania tablicy, ponieważ tablica nie musi być duża.
• Jest przyjazny dla pamięci podręcznej - jeśli dwie pary (a, b) są blisko siebie, to f odwzorowuje na nich liczby, które są blisko siebie (w porównaniu z innymi metodami).

Nie rozumiem, co masz na myśli przez:

powinna zawsze dawać liczbę całkowitą po stronie dodatniej lub ujemnej liczb całkowitych

Jak pisać (większe niż), (mniej niż) znaki na tym forum?

Chociaż odpowiedź Stephan202 jest jedyną naprawdę ogólną, w przypadku liczb całkowitych z ograniczonego zakresu można lepiej. Na przykład, jeśli twój zakres wynosi 0..10 000, możesz:

#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));
}

Wyniki mogą zmieścić się w jednej liczbie całkowitej dla zakresu do pierwiastka kwadratowego z liczności typu liczb całkowitych. Pakuje się to nieco wydajniej niż ogólniejsza metoda Stephan202. Dekodowanie jest również znacznie prostsze; nie wymagające pierwiastków kwadratowych, na początek :)

W przypadku dodatnich liczb całkowitych jako argumentów i gdy kolejność argumentów nie ma znaczenia:

1. Oto nieuporządkowana funkcja parowania :

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

2. Dla x ≠ y, oto unikalna funkcja nieuporządkowanego parowania :

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

Sprawdź to: http://en.wikipedia.org/wiki/Pigeonhole_principle . Jeśli A, B i C są tego samego typu, nie można tego zrobić. Jeśli A i B to 16-bitowe liczby całkowite, a C to 32-bit, możesz po prostu użyć przesunięcia.

Sama natura algorytmów mieszających polega na tym, że nie mogą one zapewnić unikatowego skrótu dla każdego innego wejścia.

Oto rozszerzenie kodu @DoctorJ na nieograniczone liczby całkowite oparte na metodzie podanej przez @nawfal. Może kodować i dekodować. Działa z normalnymi tablicami i tablicami liczbowymi.

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

Co powiesz na coś o wiele prostszego: Biorąc pod uwagę dwie liczby, A i B niech będą stratatation: 'A' + ';' + „B”. Niech wyjście będzie hash (str). Wiem, że nie jest to matematyczna odpowiedź, ale prosty skrypt python (który ma wbudowaną funkcję skrótu) powinien wykonać to zadanie.

To, co sugerujesz, jest niemożliwe. Zawsze będziesz mieć kolizje.

Aby zmapować dwa obiekty na inny pojedynczy zestaw, zmapowany zestaw musi mieć minimalną wielkość oczekiwanej liczby kombinacji:

Zakładając 32-bitową liczbę całkowitą, masz 2147483647 liczb całkowitych dodatnich. Wybranie dwóch z nich, w przypadku których kolejność nie ma znaczenia i przy powtarzaniu daje 2305843008139952128 kombinacji. Nie pasuje to dobrze do zestawu 32-bitowych liczb całkowitych.

Możesz jednak zmieścić to mapowanie w 61 bitach. Korzystanie z 64-bitowej liczby całkowitej jest prawdopodobnie najłatwiejsze. Ustaw wysokie słowo na mniejszą liczbę całkowitą, a niskie słowo na większą.

Załóżmy, że masz 32-bitową liczbę całkowitą. Dlaczego nie przenieść A do pierwszej 16-bitowej połowy, a B do drugiej?

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


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

Poza tym, że jest tak wydajny, jak to tylko możliwe i tani w obliczeniach, naprawdę fajnym efektem ubocznym jest to, że możesz wykonać matematykę wektorową na zapakowanej liczbie.

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

niech mamy dwie liczby B i C, kodując je w jedną liczbę A.

A = B + C * N

gdzie

B = A% N = B

C = A / N = C

Biorąc pod uwagę dodatnie liczby całkowite A i B, niech D = liczba cyfr A ma, a E = liczba cyfr B ma Wynik może być połączeniem D, 0, E, 0, A i B.

Przykład: A = 300, B = 12. D = 3, E = 2 wynik = 302030012. Wykorzystuje to fakt, że jedyną liczbą rozpoczynającą się od 0 jest 0,

Pro: Łatwe do kodowania, łatwe do odkodowania, czytelne dla człowieka, cyfry znaczące można najpierw porównać, możliwość porównania bez obliczeń, proste sprawdzanie błędów.

Minusy: Rozmiar wyników jest problemem. Ale to w porządku, dlaczego i tak przechowujemy w komputerze nieograniczone liczby całkowite.

Jeśli chcesz mieć większą kontrolę, na przykład alokuj bity X dla pierwszej liczby i bity Y dla drugiej liczby, możesz użyć tego kodu:

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);
    }
};

Używam w sumie 32 bitów. Chodzi o to, że jeśli chcesz na przykład, aby pierwsza liczba wynosiła do 10 bitów, a druga liczba do 12 bitów, możesz to zrobić:

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

Teraz możesz przechowywać w num_amaksymalnej liczbie, która jest 2^10 - 1 = 1023w num_bnaximum wartości 2^12 - 1 = 4095.

Aby ustawić wartość dla liczb A i B:

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

Teraz bnumsą wszystkie bity (łącznie 32 bity. Możesz zmodyfikować kod, aby używał 64 bitów) Aby uzyskać num a:

int a = nums_mapper.GetNumA(bnum);

Aby uzyskać num b:

int b = nums_mapper.GetNumB(bnum);

EDYCJA: bnummoże być przechowywana wewnątrz klasy. Nie zrobiłem tego, ponieważ własne potrzeby podzieliłem kod i mam nadzieję, że będzie on pomocny.

Dzięki za źródło: https://www.geeksforgeeks.org/extract-k-bits-given-position-number/ za funkcję wyodrębniania bitów i dziękuję również za mouvicielodpowiedź w tym poście. Używając ich do źródeł, mogłem znaleźć bardziej zaawansowane rozwiązanie