Mapeo de dos enteros a uno, de una manera única y determinista

Imagine dos enteros positivos A y B. Quiero combinar estos dos en un solo entero C.

No puede haber otros enteros D y E que se combinen con C. Así que combinarlos con el operador de sum no funciona. Ej. 30 + 10 = 40 = 40 + 0 = 39 + 1 Tampoco funciona la concatinación. Ej. “31” + “2” = 312 = “3” + “12”

Esta operación de combinación también debe ser determinista (siempre produce el mismo resultado con las mismas entradas) y siempre debe dar como resultado un entero en el lado positivo o negativo de los enteros.

Está buscando un mapeo biyectivo NxN -> N Estos se utilizan para, por ejemplo, empalmar . Eche un vistazo a este PDF para una introducción a las llamadas funciones de emparejamiento . Wikipedia introduce una función de emparejamiento específica, a saber, la función de emparejamiento de Cantor :

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

Tres observaciones:

  • Como otros han dejado en claro, si planea implementar una función de emparejamiento, pronto descubrirá que necesita enteros arbitrariamente grandes (bignums).
  • Si no desea hacer una distinción entre los pares (a, b) y (b, a), entonces clasifique a y b antes de aplicar la función de emparejamiento.
  • En realidad, mentí. Está buscando un ZxZ -> N bijective ZxZ -> N La función de Cantor solo funciona en números no negativos. Sin embargo, esto no es un problema, porque es fácil definir un bijection f : Z -> N , así:
    • f (n) = n * 2 si n> = 0
    • f (n) = -n * 2 – 1 si n <0

La función de vinculación de Cantor es realmente una de las mejores, ya que es simple, rápida y eficiente en el uso del espacio, pero hay algo aún mejor publicado en Wolfram por Matthew Szudzik, aquí . La limitación de la función de emparejamiento de Cantor (relativamente) es que el rango de resultados codificados no siempre se mantiene dentro de los límites de un entero de 2N bit si las entradas son dos enteros de N bits. Es decir, si mis entradas son dos enteros de 16 bits que van de 0 to 2^16 -1 , entonces hay 2^16 * (2^16 -1) combinaciones de entradas posibles, por lo que, por el obvio Principio de Casillero , necesitamos una salida de tamaño de al menos 2^16 * (2^16 -1) , que es igual a 2^32 - 2^16 , o en otras palabras, un mapa de 32 bits debería ser ideal. Esto puede no ser de poca importancia práctica en el mundo de la progtwigción.

Función de emparejamiento de Cantor :

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

La asignación para dos enteros máximos de la mayoría de 16 bits (65535, 65535) será 8589803520, que como ve no puede encajar en 32 bits.

Entrar en la función de Szudzik :

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

La asignación para (65535, 65535) ahora será 4294967295, que como ve es un entero de 32 bits (0 a 2 ^ 32 -1). Aquí es donde esta solución es ideal, simplemente utiliza cada punto en ese espacio, por lo que nada puede hacer más eficiente el espacio.


Ahora, considerando el hecho de que generalmente tratamos con las implementaciones firmadas de números de varios tamaños en lenguajes / marcos, consideremos los enteros de signed 16 bits con signed 16 van desde -(2^15) to 2^15 -1 (más adelante veremos cómo extender incluso la salida para abarcar el rango firmado). Como a y b tienen que ser positivos, van de 0 to 2^15 - 1 .

Función de emparejamiento de Cantor :

El mapeo para dos enteros con la máxima cantidad máxima de 16 bits (32767, 32767) será 2147418112, el cual está justo por debajo del valor máximo para el entero de 32 bits con signo.

Ahora la función de Szudzik :

(32767, 32767) => 1073741823, mucho más pequeño ..

Vamos a dar cuenta de los enteros negativos. Eso va más allá de la pregunta original que conozco, pero está elaborando para ayudar a los futuros visitantes.

Función de emparejamiento de 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 que es Int64. ¡La salida de 64 bits para entradas de 16 bits puede ser tan imperdonable!

La función de 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 que es de 32 bits para el rango sin signo o de 64 bits para el rango con signo, pero aún mejor.

Ahora todo esto mientras que la salida siempre ha sido positiva. En mundo firmado, será aún más ahorro de espacio si pudiéramos transferir la mitad de la salida al eje negativo . Podrías hacerlo así para Szudzik’s:

 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 

Lo que hago: Después de aplicar un peso de 2 a las entradas y pasar por la función, luego divido la salida en dos y tomo algunas de ellas en el eje negativo multiplicando por -1 .

Vea los resultados, para cualquier entrada en el rango de un número de 16 bits con signo, la salida se encuentra dentro de los límites de un entero de 32 bits con signo que es bueno. No estoy seguro de cómo proceder de la misma manera para la función de vinculación de Cantor, pero no lo intenté tanto como no es tan eficiente. Además, más cálculos implicados en la función de emparejamiento de Cantor también significan que son más lentos .

Aquí hay una implementación de 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; } 

Como los cálculos intermedios pueden exceder los límites del entero con signo 2N , he usado el tipo entero 4N (la última división por 2 devuelve el resultado a 2N ).

El enlace que he proporcionado sobre la solución alternativa muestra muy bien un gráfico de la función que utiliza cada punto en el espacio. ¡Es increíble ver que puedes codificar de forma única un par de coordenadas en un solo número de manera reversible! Mundo mágico de los números !!

Si A y B se pueden express con 2 bytes, puede combinarlos en 4 bytes. Pon A en la mitad más significativa y B en la mitad menos significativa.

En lenguaje C, esto da (suponiendo sizeof (short) = 2 y 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; } 

¿Esto es posible?
Estás combinando dos enteros. Ambos tienen el rango -2,147,483,648 a 2,147,483,647 pero solo tomarás los aspectos positivos. Eso hace 2147483647 ^ 2 = 4,61169E + 18 combinaciones. Como cada combinación tiene que ser única Y dar como resultado un número entero, necesitarás algún tipo de número entero mágico que pueda contener esta cantidad de números.

¿O mi lógica es defectuosa?

La forma matemática estándar para enteros positivos es usar la singularidad de la factorización prima.

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

La desventaja es que la imagen tiende a abarcar un rango bastante grande de enteros, por lo que cuando se trata de express el mapeo en un algoritmo de computadora, puede tener problemas para elegir un tipo apropiado para el resultado.

Puede modificar esto para tratar con x e y negativos codificando banderas con potencias de 5 y 7 términos.

p.ej

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

Deje que el número a sea ​​el primero, b el segundo. Sea p el a+1 -número primo, q sea ​​el b+1 -número primo

Entonces, el resultado es pq , si a o 2pq si a>b . Si a=b , que sea p^2 .

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

  • Esta es una función: es determinista.
  • También es inyectiva: f mapea diferentes valores para diferentes pares (a, b). Puede probar esto usando el hecho: s(a+b+1)-s(a+b) = a+b+1 < a .
  • Devuelve valores bastante pequeños, es bueno si va a usarlo para la indexación de matriz, ya que la matriz no tiene que ser grande.
  • Es amigable con el caché: si dos pares (a, b) están cerca el uno del otro, f los asigna números que están cerca uno del otro (en comparación con otros métodos).

No entendí lo que quieres decir con:

siempre debe dar un entero en el lado positivo o negativo de los enteros

¿Cómo puedo escribir (mayor que), (menos de) caracteres en este foro?

Para enteros positivos como argumentos y donde el orden de argumento no importa:

  1. Aquí hay una función de emparejamiento desordenado :

      = x * y + trunc((|x - y| - 1)^2 / 4) =  
  2. Para x ≠ y, aquí hay una función única de emparejamiento desordenado :

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

Aunque la respuesta de Stephan202 es la única verdaderamente general, para enteros en un rango limitado puede hacerlo mejor. Por ejemplo, si su rango es 0..10,000, entonces puede hacer:

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

Los resultados pueden caber en un entero único para un rango hasta la raíz cuadrada de la cardinalidad del tipo entero. Este paquete es un poco más eficiente que el método más general de Stephan202. También es considerablemente más simple de decodificar; no requiere raíces cuadradas, para empezar 🙂

Mira esto: http://en.wikipedia.org/wiki/Pigeonhole_principle . Si A, B y C son del mismo tipo, no se puede hacer. Si A y B son enteros de 16 bits y C de 32 bits, entonces simplemente puede usar el desplazamiento.

La propia naturaleza de los algoritmos hash es que no pueden proporcionar un hash único para cada entrada diferente.

No es tan difícil construir un mapeo:

    1 2 3 4 5 usa este mapeo si (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 este mapeo si (a, b) == (b, a) (espejo)
 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 esto si necesitas 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

Averiguar cómo obtener el valor de una arbitraria a, b es un poco más difícil.

Aquí hay una extensión del código de @DoctorJ a enteros sin límites basados ​​en el método dado por @nawfal. Puede codificar y decodificar. Funciona con matrices normales y matrices 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 

Lo que sugieres es imposible. Siempre tendrás colisiones.

Para asignar dos objetos a otro conjunto único, el conjunto asignado debe tener un tamaño mínimo de la cantidad de combinaciones esperadas:

Suponiendo un entero de 32 bits, tiene 2147483647 enteros positivos. Elegir dos de estos donde el orden no importa y con la repetición rinde 2305843008139952128 combinaciones. Esto no encaja bien en el conjunto de enteros de 32 bits.

Sin embargo, puede ajustar esta asignación en 61 bits. Usar un entero de 64 bits es probablemente el más fácil. Establezca la palabra alta en el entero más pequeño y la palabra baja en el más grande.

¿Qué tal algo mucho más simple: dados dos números, A y B dejan que str sea la concatenación: ‘A’ + ‘;’ + ‘B’. Luego, deje que la salida sea hash (str). Sé que esta no es una respuesta matemática, pero una secuencia de comandos simple de python (que tiene una función hash incorporada) debería hacer el trabajo.

tengamos dos números B y C, codificándolos en el número único A

A = B + C * N

dónde

B = A% N = B

C = A / N = C