Mapear 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. Por lo tanto, combinarlos con el operador de suma no funciona. Por ejemplo, 30 + 10 = 40 = 40 + 0 = 39 + 1 Tampoco funciona la concatenación. Por ejemplo, "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 producir un número entero en el lado positivo o negativo de los enteros.

Estás buscando un NxN -> Nmapeo biyectivo . Éstos se utilizan, por ejemplo, para hacer cola de milano . Eche un vistazo a este PDF para obtener una introducción a las llamadas funciones de emparejamiento . Wikipedia presenta una función de emparejamiento específica, a saber, la función de emparejamiento de Cantor :

Tres observaciones:

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

La función de emparejamiento de Cantor es realmente una de las mejores, considerando que es simple, rápida y eficiente en cuanto al 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 2Nnúmero entero de bits si las entradas son Nnúmeros enteros de dos bits. Es decir, si mis entradas son 16enteros de dos bits que van desde 0 to 2^16 -1, entonces hay 2^16 * (2^16 -1)combinaciones de entradas posibles, por lo que, según el Principio de Pigeonhole obvio , necesitamos una salida de tamaño al menos 2^16 * (2^16 -1), que sea igual 2^32 - 2^16o, en otras palabras, un mapa de32los números de bits deberían ser factibles idealmente. Esto puede no ser de poca importancia práctica en el mundo de la programació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 16 bits (65535, 65535) será 8589803520 que, como puede ver, no puede caber en 32 bits.

Ingrese 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 puede ver, 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 ser más eficiente.

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

Función de emparejamiento de Cantor :

La asignación para dos números enteros máximos con signo de 16 bits (32767, 32767) será 2147418112, que es justo por debajo del valor máximo para el número entero con signo de 32 bits.

Ahora la función de Szudzik :

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

Consideremos los enteros negativos. Eso está más allá de la pregunta original que conozco, pero solo se elabora 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 32 bits para rango sin signo o 64 bits para rango con signo, pero aún mejor.

Ahora todo esto mientras que la salida siempre ha sido positiva. En el mundo firmado, se ahorrará aún más 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 2a las entradas y pasar por la función, divido la salida por dos y llevo algunas de ellas al eje negativo multiplicando por -1.

Vea los resultados, para cualquier entrada en el rango de un 16número de bit con signo , la salida se encuentra dentro de los límites de un 32entero de bit con signo que es genial. No estoy seguro de cómo hacer lo mismo para la función de emparejamiento de Cantor, pero no intenté tanto como no es tan eficiente. Además, más cálculos involucrados en la función de emparejamiento de Cantor significa que también es más lento .

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 2Nentero con signo, he usado el 4Ntipo entero (la última división 2devuelve el resultado 2N).

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

Si A y B pueden expresarse con 2 bytes, puede combinarlos en 4 bytes. Ponga 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;
}

¿Es esto posible?
Estás combinando dos enteros. Ambos tienen el rango de -2,147,483,648 a 2,147,483,647 pero solo tomará los 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á algún tipo de número entero mágico que pueda contener esta cantidad de números.

¿O es mi lógica defectuosa?

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

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

La desventaja es que la imagen tiende a abarcar una amplia gama de enteros, por lo que cuando se trata de expresar el mapeo en un algoritmo informático, puede tener problemas para elegir un tipo apropiado para el resultado.

Puede modificar esto para tratar con negativo xy ycodificando 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 asea ​​el primero, bel segundo. Sea pel a+1enésimo número primo, qsea ​​el b+1enésimo número primo

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

No es tan difícil construir un mapeo:

   1 2 3 4 5 use esta asignación 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 use esta asignación 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 use esto si necesita 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

Descubrir cómo obtener el valor para un arbitrario a, b es un poco más difícil.

f(a, b) = s(a+b) + a, dónde s(n) = n*(n+1)/2

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

No entendí lo que quieres decir con:

siempre debe producir un número entero en el lado positivo o negativo de los enteros

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

Aunque la respuesta de Stephan202 es la única realmente general, para los enteros en un rango acotado 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 solo entero para un rango hasta la raíz cuadrada de la cardinalidad del tipo entero. Esto empaca un poco más eficientemente que el método más general de Stephan202. También es considerablemente más sencillo de decodificar; que no requieren raíces cuadradas, para empezar :)

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

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

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

2. Para x ≠ y, aquí hay una función de emparejamiento desordenada única :

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

Revisa 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 es de 32 bits, entonces simplemente puede usar el desplazamiento.

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

Aquí hay una extensión del código de @DoctorJ a enteros ilimitados basado en el método proporcionado 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

¿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 un simple script de Python (que tiene una función hash incorporada) debería hacer el trabajo.

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 del número de combinaciones esperadas:

Suponiendo un entero de 32 bits, tiene 2147483647 enteros positivos. Elegir dos de estos en los que el orden no importa y con la repetición produce 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 número entero de 64 bits es probablemente lo más fácil. Establezca la palabra alta en el entero más pequeño y la palabra baja en la más grande.

Digamos que tiene un número entero de 32 bits, ¿por qué no simplemente mueve A a la primera mitad de 16 bits y B a la otra?

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


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

Además de ser tan eficiente en espacio como sea posible y barato de calcular, un efecto secundario realmente genial es que puedes hacer cálculos vectoriales en el número empaquetado.

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

tengamos dos números B y C, codificándolos en un solo número A

A = B + C * N

dónde

B = A% N = B

C = A / N = C

Dados los enteros positivos A y B, supongamos que D = número de dígitos A tiene, y E = número de dígitos B tiene El resultado puede ser una concatenación de D, 0, E, 0, A y B.

Ejemplo: A = 300, B = 12. D = 3, E = 2 resultado = 302030012. Esto aprovecha el hecho de que el único número que comienza con 0, es 0,

Pro: fácil de codificar, fácil de decodificar, legible por humanos, se pueden comparar primero dígitos significativos, potencial de comparación sin cálculo, simple verificación de errores.

Contras: el tamaño de los resultados es un problema. Pero está bien, ¿por qué estamos almacenando enteros ilimitados en una computadora?

Si desea más control, como asignar bits X para el primer número e bits Y para el segundo número, puede usar este código:

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

Yo uso 32 bits en total. La idea aquí es que si desea, por ejemplo, que el primer número tenga hasta 10 bits y el segundo número tenga hasta 12 bits, puede hacer esto:

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

Ahora puede almacenar en num_ael número máximo que es 2^10 - 1 = 1023y en el num_bvalor máximo de 2^12 - 1 = 4095.

Para establecer el valor para num A y num B:

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

Ahora bnumes todos los bits (32 bits en total. Puede modificar el código para usar 64 bits) Para obtener num a:

int a = nums_mapper.GetNumA(bnum);

Para obtener num b:

int b = nums_mapper.GetNumB(bnum);

EDITAR: bnumse puede almacenar dentro de la clase. No lo hice porque mis propias necesidades compartí el código y espero que sea útil.

Gracias por la fuente: https://www.geeksforgeeks.org/extract-k-bits-given-position-number/ por la función para extraer bits y gracias también por mouvicielresponder en esta publicación. Usando estos para las fuentes podría encontrar una solución más avanzada