Mappare due interi a uno, in modo unico e deterministico

Immagina due interi positivi A e B. Voglio combinare questi due in un singolo intero C.

Non ci possono essere altri interi D ed E che si combinano con C. Quindi combinarli con l’operatore di addizione non funziona. Ad esempio 30 + 10 = 40 = 40 + 0 = 39 + 1 Né funziona la concatinazione. Ad esempio “31” + “2” = 312 = “3” + “12”

Questa operazione di combinazione dovrebbe anche essere deterministica (fornire sempre lo stesso risultato con gli stessi input) e dovrebbe sempre produrre un numero intero sul lato positivo o negativo degli interi.

Stai cercando una mapping NxN -> N biettiva. Questi sono usati per esempio a coda di rondine . Dai un’occhiata a questo PDF per un’introduzione alle cosiddette funzioni di abbinamento . Wikipedia introduce una specifica funzione di accoppiamento, ovvero la funzione di accoppiamento di Cantor :

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

Tre osservazioni:

  • Come altri hanno chiarito, se si prevede di implementare una funzione di abbinamento, è ansible trovare presto i numeri interi arbitrariamente grandi (bignum).
  • Se non si desidera fare una distinzione tra le coppie (a, b) e (b, a), quindi ordinare a e b prima di applicare la funzione di associazione.
  • In realtà ho mentito. Stai cercando una mapping ZxZ -> N La funzione di Cantor funziona solo su numeri non negativi. Tuttavia, questo non è un problema, perché è facile definire una biiezione f : Z -> N , in questo modo:
    • f (n) = n * 2 se n> = 0
    • f (n) = -n * 2 – 1 se n <0

La funzione di accoppiamento di Cantor è davvero una delle migliori là fuori considerando la sua semplicità, velocità e efficienza nello spazio, ma c’è qualcosa di ancora meglio pubblicato su Wolfram di Matthew Szudzik, qui . La limitazione della funzione di accoppiamento di Cantor (relativamente) è che l’intervallo di risultati codificati non rimane sempre nei limiti di un numero intero a 2N bit se gli input sono due interi N bit. Cioè, se i miei input sono due interi a 16 bit che vanno da 0 to 2^16 -1 , allora ci sono 2^16 * (2^16 -1) combinazioni di input possibili, quindi con l’ovvio principio Pigeonhole , abbiamo bisogno di un uscita di dimensione almeno 2^16 * (2^16 -1) , che è uguale a 2^32 - 2^16 , o in altre parole, una mappa di numeri a 32 bit dovrebbe essere fattibile idealmente. Questo potrebbe non avere poca importanza pratica nel mondo della programmazione.

Funzione di accoppiamento di Cantor :

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

La mapping per due numeri massimi al massimo a 16 bit (65535, 65535) sarà 8589803520 che, come vedete, non può essere adattato a 32 bit.

Entra nella funzione di Szudzik :

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

La mapping per (65535, 65535) sarà ora 4294967295 che, come vedete, è un intero a 32 bit (da 0 a 2 ^ 32 -1). È qui che questa soluzione è ideale, utilizza semplicemente ogni singolo punto in quello spazio, quindi nulla può ottenere più spazio efficiente.


Considerando ora il fatto che di solito trattiamo le implementazioni firmate di numeri di varie dimensioni in linguaggi / framework, prendiamo in considerazione interi a signed 16 bit signed 16 che vanno da -(2^15) to 2^15 -1 (in seguito vedremo come estendi anche l’uscita per coprire l’intervallo firmato). Poiché b devono essere positivi, vanno da 0 to 2^15 - 1 .

Funzione di accoppiamento di Cantor :

La mapping per due numeri interi con segno massimo di 16 bit (32767, 32767) sarà 2147418112, che è appena inferiore al valore massimo per il numero intero a 32 bit con segno.

Ora la funzione di Szudzik :

(32767, 32767) => 1073741823, molto più piccolo ..

Facciamo conto degli interi negativi. Questo è al di là della domanda iniziale che conosco, ma solo l’elaborazione per aiutare i futuri visitatori.

Funzione di accoppiamento di Cantor :

 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 che è Int64. L’uscita a 64 bit per gli ingressi a 16 bit potrebbe essere così imperdonabile !!

La funzione di Szudzik :

 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 che è a 32 bit per intervallo senza segno o 64 bit per intervallo con segno, ma ancora migliore.

Ora tutto ciò mentre l’output è sempre stato positivo. Nel mondo firmato, ci sarà ancora più risparmio di spazio se potessimo trasferire metà dell’uscita sull’asse negativo . Potresti farlo in questo modo per 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 

Cosa faccio: dopo aver applicato un peso di 2 agli input e passando attraverso la funzione, divido l’output per due e ne prendo alcuni sull’asse negativo moltiplicando per -1 .

Vedi i risultati, per ogni input nell’intervallo di un numero a 16 bit con segno, l’uscita si trova entro i limiti di un intero con segno a 32 bit che è cool. Non sono sicuro di come andare nello stesso modo per la funzione di accoppiamento di Cantor, ma non ho provato tanto quanto non altrettanto efficiente. Inoltre, più calcoli coinvolti nella funzione di accoppiamento di Cantor significa anche più lento .

Ecco una implementazione in 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; } 

Poiché i calcoli intermedi possono superare i limiti del numero intero con 2N , ho utilizzato il tipo intero 4N (l’ultima divisione per 2 riporta il risultato a 2N ).

Il link che ho fornito su una soluzione alternativa descrive in modo accurato un grafico della funzione che utilizza ogni singolo punto nello spazio. È sorprendente vedere che è ansible codificare in modo univoco una coppia di coordinate in un unico numero in modo reversibile! Mondo magico di numeri !!

Se A e B possono essere espressi con 2 byte, è ansible combinarli su 4 byte. Metti A nella metà più significativa e B nella metà meno significativa.

In linguaggio C questo dà (assumendo sizeof (short) = 2 e 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; } 

È ansible?
Stai combinando due numeri interi. Entrambi hanno il range -2.147.483.648 a 2.147.483.647 ma si prenderanno solo gli aspetti positivi. Ciò rende 2147483647 ^ 2 = 4,61169E + 18 combinazioni. Poiché ogni combinazione deve essere unica e risultare in un numero intero, avrai bisogno di una sorta di numero intero magico che possa contenere questa quantità di numeri.

O la mia logica è difettosa?

Il modo matematico standard per gli interi positivi è utilizzare l’unicità della fattorizzazione primaria.

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

Il rovescio della medaglia è che l’immagine tende ad abbracciare una gamma piuttosto ampia di numeri interi, quindi quando si tratta di esprimere la mapping in un algoritmo del computer si possono avere problemi con la scelta di un tipo appropriato per il risultato.

Puoi modificarlo per gestire le x negative codificando un flag con potenze di 5 e 7 termini.

per esempio

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

Sia il numero a essere il primo, b il secondo. Sia p il numero a+1 -primo numero, q sia il numero primo b+1 -b

Quindi, il risultato è pq , se a o 2pq se a>b . Se a=b , lascia che sia p^2 .

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

  • Questa è una funzione – è deterministica.
  • È anche iniettivo – f mappa diversi valori per diverse coppie (a, b). Puoi dimostrarlo usando il fatto: s(a+b+1)-s(a+b) = a+b+1 < a .
  • Restituisce valori piuttosto piccoli, buoni se lo si utilizzerà per l'indicizzazione degli array, poiché l'array non deve essere grande.
  • È compatibile con la cache - se due (a, b) coppie sono vicine l'una all'altra, quindi f esegue il mapping dei numeri a loro vicini l'uno all'altro (rispetto ad altri metodi).

Non ho capito cosa intendi con:

dovrebbe sempre produrre un numero intero sul lato positivo o negativo degli interi

Come posso scrivere (più grande di), (meno di) personaggi in questo forum?

Per numeri interi positivi come argomenti e dove l’ordine degli argomenti non ha importanza:

  1. Ecco una funzione di abbinamento non ordinato :

      = x * y + trunc((|x - y| - 1)^2 / 4) =  
  2. Per x ≠ y, ecco una funzione di abbinamento non ordinata unica :

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

Sebbene la risposta di Stephan202 sia l’unica veramente generale, per i numeri interi in un intervallo limitato puoi fare di meglio. Ad esempio, se il tuo intervallo è 0. 10.000, allora puoi fare:

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

I risultati possono essere contenuti in un singolo numero intero per un intervallo fino alla radice quadrata della cardinalità del tipo intero. Questo pacchetto è leggermente più efficiente del metodo più generale di Stephan202. È anche molto più semplice da decodificare; non richiede radici quadrate, per i principianti 🙂

Controlla questo: http://en.wikipedia.org/wiki/Pigeonhole_principle . Se A, B e C sono dello stesso tipo, non può essere fatto. Se A e B sono interi a 16 bit e C è a 32 bit, allora puoi semplicemente usare lo spostamento.

La vera natura degli algoritmi di hashing è che non possono fornire un hash univoco per ogni input differente.

Non è così difficile build una mapping:

    1 2 3 4 5 usa questa mapping se (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 usa questa mapping se (a, b) == (b, a) (specchio)
 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 usa questo se hai bisogno di negativo / positivo
  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

Capire come ottenere il valore per un arbitrario a, b è un po ‘più difficile.

Ecco un’estensione del codice di @DoctorJ agli interi illimitati in base al metodo fornito da @nawfal. Può codificare e decodificare. Funziona con array normali e array numpy.

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

Quello che suggerisci è imansible. Avrai sempre collisioni.

Per mappare due oggetti in un altro singolo set, il set mappato deve avere una dimensione minima del numero di combinazioni previste:

Supponendo un numero intero a 32 bit, si hanno 2147483647 numeri interi positivi. Scegliere due di questi in cui l’ordine non ha importanza e con la ripetizione produce 2305843008139952128 combinazioni. Questo non si adatta bene al set di numeri interi a 32 bit.

Puoi, tuttavia, adattare questa mapping a 61 bit. L’utilizzo di un numero intero a 64 bit è probabilmente il più semplice. Imposta la parola alta sul numero intero più piccolo e la parola bassa su quella più grande.

Che ne dici di qualcosa di molto più semplice: dati due numeri, A e B lascia che str sia la concatenazione: ‘A’ + ‘;’ + ‘B’. Quindi lascia che l’output sia hash (str). So che questa non è una risposta matematica, ma un semplice python (che ha una funzione di hash incorporata) dovrebbe fare il lavoro.

diamo due numeri B e C, codificandoli nel numero singolo A

A = B + C * N

dove

B = A% N = B

C = A / N = C