algorithm - Сопоставление двух целых чисел с единым, уникальным и детерминированным образом




mapping integer (10)

Представьте себе два положительных целых числа A и B. Я хочу объединить эти два в единое целое C.

Не может быть никаких других целых чисел D и E, которые объединены с C. Поэтому объединение их с оператором сложения не работает. Например, 30 + 10 = 40 = 40 + 0 = 39 + 1 Также не работает конкатенация. Например, "31" + "2" = 312 = "3" + "12"

Эта операция комбинации также должна быть детерминированной (всегда давать тот же результат с теми же входами) и всегда должна давать целое число на положительной или отрицательной стороне целых чисел.


Возможно ли это?
Вы объединяете два целых числа. Они оба имеют диапазон -2,147,483,648 до 2,147,483,647, но вы будете принимать только положительные результаты. Это составляет 2147483647 ^ 2 = 4 61169E + 18 комбинаций. Так как каждая комбинация должна быть уникальной И привести к целому числу, вам понадобится какое-то волшебное целое число, которое может содержать это количество чисел.

Или моя логика ошибочна?


Вот расширение кода @DoctorJ для неограниченных целых чисел на основе метода, заданного @nawfal. Он может кодировать и декодировать. Он работает с обычными массивами и массивами 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://.com/a/15391420
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

Для положительных целых чисел в качестве аргументов и где порядок аргументов не имеет значения:

  1. Вот неупорядоченная функция спаривания :

    <x, y> = x * y + trunc((|x - y| - 1)^2 / 4) = <y, x>
    
  2. Для x ≠ y, здесь существует уникальная неупорядоченная функция спаривания :

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

Если A и B могут быть выражены с помощью 2 байтов, вы можете объединить их на 4 байта. Положите A на наиболее значительную половину и B на наименее значимую половину.

В языке C это дает (при условии sizeof (short) = 2 и 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;
}

Не сложно построить сопоставление:

   1  2  3  4  5  use this mapping if (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 this mapping if (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 use this if you need negative/positive
 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

Выяснив, как получить значение для произвольного a, b немного сложнее.


Проверьте это: http://en.wikipedia.org/wiki/Pigeonhole_principle . Если A, B и C имеют один и тот же тип, это невозможно. Если A и B являются 16-битными целыми числами, а C - 32-битными, то вы можете просто использовать сдвиг.

Сама природа алгоритмов хэширования заключается в том, что они не могут обеспечить уникальный хеш для каждого входа.


Стандартным математическим способом для целых положительных чисел является использование единственности простой факторизации.

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

Недостатком является то, что изображение имеет тенденцию охватывать довольно большой диапазон целых чисел, поэтому, когда дело доходит до выражения отображения в компьютерном алгоритме, у вас могут возникнуть проблемы с выбором подходящего типа для результата.

Вы можете изменить это, чтобы иметь дело с отрицательными x и y , кодируя флаги с полномочиями 5 и 7 терминов.

например

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

То, что вы предлагаете, невозможно. У вас всегда будут столкновения.

Чтобы сопоставить два объекта с другим одним набором, отображаемый набор должен иметь минимальный размер количества ожидаемых комбинаций:

Предполагая 32-битное целое число, у вас есть 2147483647 положительных целых чисел. Выбор двух из них, где порядок не имеет значения и с повторением дает 2305843008139952128 комбинаций. Это не подходит для множества 32-битных целых чисел.

Вы можете, однако, поместить это сопоставление в 61 бит. Использование 64-битного целого числа, вероятно, проще всего. Установите высокое слово на меньшее целое и низкое слово на большее.


имеем два числа B и C, кодируя их в одно число A

A = B + C * N

где

B = A% N = B

C = A / N = C


Функция спаривания Кантора действительно одна из лучших из них, учитывая ее простую, быструю и пространственную эффективность, но здесь есть что-то еще лучше опубликованное в Вольфраме Мэтью Сюдзик . Ограничение функции связывания Cantor (относительно) заключается в том, что диапазон закодированных результатов не всегда остается в пределах 2N битного целого числа, если входы представляют собой два N битовых целых числа. То есть, если мои входы представляют собой два 16 битных целых числа от 0 to 2^16 -1 , тогда возможны 2^16 * (2^16 -1) возможных комбинаций входных сигналов 2^16 * (2^16 -1) , поэтому по очевидному принципу Голубой волны нам нужно выход размером не менее 2^16 * (2^16 -1) , который равен 2^32 - 2^16 , или, другими словами, карта 32 битных чисел должна быть практически идеальной. Это может быть мало практическим в мире программирования.

Функция связывания Кантора :

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

Отображение для двух максимальных 16-битных целых чисел (65535, 65535) будет 8589803520, которое, как вы видите, не может быть помещено в 32 бита.

Введите функцию Szudzik :

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

Отображение для (65535, 65535) теперь будет 4294967295, которое, как вы видите, представляет собой 32-битное (от 0 до 2 ^ 32 -1) целое число. Именно здесь это решение идеально, оно просто использует каждую точку в этом пространстве, поэтому ничто не может получить больше пространства.

Теперь, учитывая тот факт, что мы обычно имеем дело с подписанными реализациями чисел различных размеров в языках / фреймах, давайте рассмотрим signed 16 битные целые числа от -(2^15) to 2^15 -1 (позже мы увидим, как расширяют даже вывод до диапазона над подписанным диапазоном). Так как a и b должны быть положительными, они варьируются от 0 to 2^15 - 1 .

Функция связывания Кантора :

Отображение для двух максимальных 16-разрядных знаковых целых чисел (32767, 32767) будет 2147418112, что просто не соответствует максимальному значению для 32-битного целого числа.

Теперь функция Судзика :

(32767, 32767) => 1073741823, намного меньше ..

Рассмотрим отрицательные целые числа. Это выходит за рамки первоначального вопроса, который я знаю, но просто для того, чтобы помочь будущим посетителям.

Функция связывания Кантора :

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, который является Int64. 64-разрядный выход для 16-битных входов может быть настолько непростительным!

Функция Судзика :

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, который 32 бит для неподписанного диапазона или 64 бит для подписанного диапазона, но все же лучше.

Теперь все это, в то время как выход всегда был положительным. В подписанном мире это будет еще более экономичным, если мы сможем перенести половину вывода на отрицательную ось . Вы могли бы сделать это так для 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

Что я делаю: после применения веса 2 к входам и прохождения через функцию я затем делю на вывод на два, а некоторые из них - на отрицательную ось, умножая на -1 .

См. Результаты, для любого ввода в диапазоне подписанного 16 битного номера, выход находится в пределах подписанного 32 битного целого числа, которое является прохладным. Я не уверен, как сделать то же самое для функции спаривания Кантора, но не пытался, насколько это не так эффективно. Более того, большее количество вычислений, связанных с функцией спаривания Кантора, означает, что он медленнее .

Вот реализация 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;
}

Поскольку промежуточные вычисления могут превышать пределы 2N целого числа со 2N , я использовал 4N целочисленный тип (последнее деление на 2 возвращает результат к 2N ).

Ссылка, которую я предоставил на альтернативном решении, красиво отображает график функции, использующей каждую точку пространства. Его удивительно видеть, что вы можете однозначно кодировать пару координат на один номер обратимо! Волшебный мир чисел !!





math