Mapper deux entiers en un, de manière unique et déterministe

Imaginez deux entiers positifs A et B. Je veux combiner ces deux en un seul entier C.

Il ne peut pas y avoir d'autres entiers D et E qui se combinent en C. Donc, les combiner avec l'opérateur d'addition ne fonctionne pas. Par exemple 30 + 10 = 40 = 40 + 0 = 39 + 1 La concatination ne fonctionne pas non plus. Par exemple "31" + "2" = 312 = "3" + "12"

Cette opération de combinaison doit également être déterministe (toujours produire le même résultat avec les mêmes entrées) et doit toujours produire un entier du côté positif ou négatif des nombres entiers.

Vous recherchez une NxN -> Ncartographie bijective . Ceux-ci sont utilisés par exemple pour la queue d'aronde . Jetez un œil à ce PDF pour une introduction aux fonctions dites de couplage . Wikipedia introduit une fonction d'appariement spécifique, à savoir la fonction d'appariement Cantor :

Trois remarques:

• Comme d'autres l'ont clairement indiqué, si vous prévoyez d'implémenter une fonction d'appariement, vous découvrirez peut-être bientôt que vous avez besoin de nombres entiers arbitrairement grands (bignums).
• Si vous ne souhaitez pas faire de distinction entre les paires (a, b) et (b, a), triez a et b avant d'appliquer la fonction d'appariement.
• En fait, j'ai menti. Vous recherchez une ZxZ -> Ncartographie bijective . La fonction de Cantor ne fonctionne que sur les nombres non négatifs. Ce n'est pas un problème cependant, car il est facile de définir une bijection f : Z -> N, comme ceci:
  • f (n) = n * 2 si n> = 0
  • f (n) = -n * 2 - 1 si n <0

La fonction de couplage de Cantor est vraiment l'une des meilleures là-bas compte tenu de sa simplicité, de sa rapidité et de son faible encombrement, mais il y a quelque chose de mieux publié à Wolfram par Matthew Szudzik, ici . La limitation de la fonction d'appariement de Cantor (relativement) est que la plage de résultats codés ne reste pas toujours dans les limites d'un 2Nentier de bits si les entrées sont Ndes entiers de deux bits. Autrement dit, si mes entrées sont 16des entiers de deux bits allant de 0 to 2^16 -1, alors il y a des 2^16 * (2^16 -1)combinaisons d'entrées possibles, donc par le principe évident de Pigeonhole , nous avons besoin d'une sortie de taille au moins 2^16 * (2^16 -1), qui est égale 2^32 - 2^16, ou en d'autres termes, une carte de32les nombres de bits devraient être réalisables idéalement. Cela peut ne pas être de peu d'importance pratique dans le monde de la programmation.

Fonction d'appariement Cantor :

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

Le mappage pour deux nombres entiers maximum de 16 bits (65535, 65535) sera 8589803520 qui, comme vous le voyez, ne peut pas tenir sur 32 bits.

Entrez dans la fonction de Szudzik :

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

Le mappage pour (65535, 65535) sera désormais 4294967295 qui, comme vous le voyez, est un entier de 32 bits (0 à 2 ^ 32 -1). C'est là que cette solution est idéale, elle utilise simplement chaque point de cet espace, donc rien ne peut être plus efficace en termes d'espace.

Considérant maintenant le fait que nous traitons généralement les implémentations signées de nombres de différentes tailles dans les langages / frameworks, considérons signed 16les entiers binaires allant de -(2^15) to 2^15 -1(plus tard, nous verrons comment étendre même la sortie pour s'étendre sur la plage signée). Depuis aet bdoivent être positifs, ils vont de 0 to 2^15 - 1.

Fonction d'appariement Cantor :

Le mappage pour deux nombres entiers signés maximum 16 bits (32767, 32767) sera 2147418112, ce qui est juste en deçà de la valeur maximale pour un entier signé 32 bits.

Maintenant la fonction de Szudzik :

(32767, 32767) => 1073741823, beaucoup plus petit ..

Prenons les entiers négatifs. C'est au-delà de la question d'origine que je connais, mais juste pour élaborer pour aider les futurs visiteurs.

Fonction d'appariement 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 qui est Int64. La sortie 64 bits pour les entrées 16 bits peut être tellement impardonnable !!

La fonction 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 qui est 32 bits pour la plage non signée ou 64 bits pour la plage signée, mais encore mieux.

Maintenant, tout cela alors que la sortie a toujours été positive. Dans le monde signé, ce sera encore plus d'économie d'espace si nous pouvions transférer la moitié de la sortie sur l'axe négatif . Vous pouvez le faire comme ceci pour 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

Ce que je fais: Après avoir appliqué un poids de 2aux entrées et avoir parcouru la fonction, je divise ensuite la sortie par deux et amène certaines d'entre elles à l'axe négatif en multipliant par -1.

Voir les résultats, pour toute entrée dans la plage d'un 16nombre de bits signé , la sortie se situe dans les limites d'un 32entier de bit signé qui est cool. Je ne sais pas comment procéder de la même manière pour la fonction d'appariement Cantor, mais je n'ai pas essayé autant que ce n'est pas aussi efficace. De plus, plus de calculs impliqués dans la fonction d'appariement de Cantor signifient qu'elle est aussi plus lente .

Voici une implémentation 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;
}

Étant donné que les calculs intermédiaires peuvent dépasser les limites de l' 2Nentier signé, j'ai utilisé le 4Ntype entier (la dernière division par 2ramène le résultat à 2N).

Le lien que j'ai fourni sur une solution alternative représente bien un graphique de la fonction utilisant chaque point dans l'espace. C'est incroyable de voir que vous pouvez coder de manière unique une paire de coordonnées en un seul numéro de manière réversible! Monde magique des nombres !!

Si A et B peuvent être exprimés avec 2 octets, vous pouvez les combiner sur 4 octets. Mettez A sur la moitié la plus significative et B sur la moitié la moins significative.

En langage C, cela donne (en supposant que sizeof (short) = 2 et 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;
}

Est-ce seulement possible?
Vous combinez deux entiers. Ils ont tous deux la plage -2 147 483 648 à 2 147 483 647 mais vous ne prendrez que les positifs. Cela fait 2147483647 ^ 2 = 4,61169E + 18 combinaisons. Étant donné que chaque combinaison doit être unique ET entraîner un entier, vous aurez besoin d'une sorte d'entier magique qui peut contenir cette quantité de nombres.

Ou ma logique est-elle défectueuse?

La méthode mathématique standard pour les entiers positifs consiste à utiliser l'unicité de la factorisation principale.

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

L'inconvénient est que l'image a tendance à s'étendre sur une assez large gamme d'entiers, donc quand il s'agit d'exprimer le mappage dans un algorithme informatique, vous pouvez avoir des problèmes avec le choix d'un type approprié pour le résultat.

Vous pouvez le modifier pour gérer le négatif xet yen encodant des drapeaux avec des pouvoirs de 5 et 7 termes.

par exemple

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

Soit le nombre ale premier, ble second. Soit ple a+1-ième nombre premier, qsoit leb+1 -ième nombre premier

Ensuite, le résultat est pq, si a<b,ou 2pqsi a>b. Si a=b, que ce soit p^2.

Ce n'est pas si difficile de construire une cartographie:

   1 2 3 4 5 utilisez ce mappage 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 utilisez ce mappage si (a, b) == (b, a) (miroir)
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 utilisez-le si vous avez besoin de négatif / positif
 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

Trouver comment obtenir la valeur d'un arbitraire a, b est un peu plus difficile.

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

• C'est une fonction - elle est déterministe.
• Il est également injectif - f mappe différentes valeurs pour différentes paires (a, b). Vous pouvez le prouver en utilisant le fait: s(a+b+1)-s(a+b) = a+b+1 < a.
• Il renvoie des valeurs assez petites - bonnes si vous allez l'utiliser pour l'indexation de tableaux, car le tableau n'a pas besoin d'être grand.
• Il est compatible avec le cache - si deux paires (a, b) sont proches l'une de l'autre, alors f leur associe des nombres proches (par rapport à d'autres méthodes).

Je n'ai pas compris ce que vous entendez par:

devrait toujours produire un entier du côté positif ou négatif des entiers

Comment puis-je écrire (supérieur à), (inférieur à) des caractères dans ce forum?

Bien que la réponse de Stephan202 soit la seule vraiment générale, pour les entiers dans une plage bornée, vous pouvez faire mieux. Par exemple, si votre plage est de 0 à 10 000, vous pouvez faire:

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

Les résultats peuvent tenir dans un seul entier pour une plage allant jusqu'à la racine carrée de la cardinalité du type entier. Cela s'emballe légèrement plus efficacement que la méthode plus générale de Stephan202. Il est également beaucoup plus simple à décoder; ne nécessitant pas de racines carrées, pour commencer :)

Pour les entiers positifs comme arguments et où l'ordre des arguments n'a pas d'importance:

1. Voici une fonction d'appariement non ordonnée :

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

2. Pour x ≠ y, voici une fonction d'appariement unique non ordonnée :

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

Vérifiez ceci: http://en.wikipedia.org/wiki/Pigeonhole_principle . Si A, B et C sont du même type, cela ne peut pas être fait. Si A et B sont des entiers 16 bits et C est 32 bits, vous pouvez simplement utiliser le décalage.

La nature même des algorithmes de hachage est qu'ils ne peuvent pas fournir un hachage unique pour chaque entrée différente.

Voici une extension du code de @DoctorJ aux entiers illimités basés sur la méthode donnée par @nawfal. Il peut encoder et décoder. Il fonctionne avec des tableaux normaux et des tableaux 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

Que diriez-vous de quelque chose de beaucoup plus simple: étant donné deux nombres, A et B soit str la concaténation: 'A' + ';' + 'B'. Ensuite, laissez la sortie être hachée (str). Je sais que ce n'est pas une réponse mathématique, mais un simple script python (qui a une fonction de hachage intégrée) devrait faire le travail.

Ce que vous proposez est impossible. Vous aurez toujours des collisions.

Afin de mapper deux objets à un autre ensemble unique, l'ensemble mappé doit avoir une taille minimale du nombre de combinaisons attendues:

En supposant un entier 32 bits, vous avez 2147483647 entiers positifs. Le choix de deux d'entre eux où l'ordre n'a pas d'importance et avec répétition donne 2305843008139952128 combinaisons. Cela ne rentre pas bien dans l'ensemble des entiers 32 bits.

Vous pouvez cependant adapter ce mappage en 61 bits. L'utilisation d'un entier 64 bits est probablement la plus simple. Définissez le mot haut sur le plus petit entier et le mot bas sur le plus grand.

Disons que vous avez un entier de 32 bits, pourquoi ne pas simplement déplacer A dans la première moitié de 16 bits et B dans l'autre?

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


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

En plus d'être aussi économe en espace que possible et peu coûteux à calculer, un effet secondaire vraiment cool est que vous pouvez faire des calculs vectoriels sur le nombre emballé.

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

ayons deux nombres B et C, en les codant en un seul nombre A

A = B + C * N

où

B = A% N = B

C = A / N = C

Étant donné les entiers positifs A et B, soit D = nombre de chiffres A a, et E = nombre de chiffres B a Le résultat peut être une concaténation de D, 0, E, 0, A et B.

Exemple: A = 300, B = 12. D = 3, E = 2 résultat = 302030012. Cela profite du fait que le seul nombre commençant par 0 est 0,

Pro: Facile à coder, facile à décoder, lisible par l'homme, les chiffres significatifs peuvent être comparés en premier, potentiel de comparaison sans calcul, vérification simple des erreurs.

Inconvénients: la taille des résultats est un problème. Mais ça va, pourquoi stockons-nous de toute façon des entiers illimités dans un ordinateur.

Si vous voulez plus de contrôle, comme allouer X bits pour le premier nombre et Y bits pour le deuxième nombre, vous pouvez utiliser ce code:

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

J'utilise 32 bits au total. L'idée ici est que si vous voulez par exemple que le premier nombre soit jusqu'à 10 bits et le second nombre jusqu'à 12 bits, vous pouvez le faire:

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

Vous pouvez maintenant stocker num_ale nombre maximal qui est 2^10 - 1 = 1023et la num_bvaleur maximale de 2^12 - 1 = 4095.

Pour définir la valeur de num A et num B:

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

Maintenant, bnumc'est tous les bits (32 bits au total. Vous pouvez modifier le code pour utiliser 64 bits) Pour obtenir num a:

int a = nums_mapper.GetNumA(bnum);

Pour obtenir num b:

int b = nums_mapper.GetNumB(bnum);

EDIT: bnumpeut être stocké dans la classe. Je ne l'ai pas fait parce que mes propres besoins, j'ai partagé le code et j'espère qu'il sera utile.

Merci pour la source: https://www.geeksforgeeks.org/extract-k-bits-given-position-number/ pour la fonction d'extraire des bits et merci également de mouvicielrépondre dans cet article. En utilisant ces sources, je pourrais trouver une solution plus avancée