Отображение двух целых чисел в одно уникальным и детерминированным способом

Функция сопряжения Cantor действительно одна из лучших, учитывая ее простоту, скорость и компактность, но есть кое-что еще лучше, опубликованное в Wolfram Мэтью Шудзиком здесь. Ограничение функции сопряжения Кантора (относительно) состоит в том, что диапазон закодированных результатов не всегда остается в пределах 2N-битового целого числа, если входные данные представляют собой два N-битовых целых числа. То есть, если мои входные данные представляют собой два 16 битовых целых числа в диапазоне от 0 to 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-битные.

Введите функцию Судзика:

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

Теперь при всем при этом выход всегда был положительным. В мире со знаком было бы еще больше экономии места, если бы мы могли перенести половину вывода на отрицательную ось. Для Шудзика это можно сделать так:

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 целого числа со знаком, я использовал 4N целочисленный тип (последнее деление на 2 возвращает результат к 2N).

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

Если A и B можно выразить двумя байтами, вы можете объединить их в 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;
}

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

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

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

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

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

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

e.g.

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

Пусть число a будет первым, b - вторым. Пусть p будет a+1 -м простым числом, q будет b+1-м простым числом

Тогда результат будет pq, если a<b,, или 2pq, если a>b. Если a=b, пусть будет p^2.

Построить отображение не так уж и сложно:

   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, немного сложнее.

f(a, b) = s(a+b) + a, где s(n) = n*(n+1)/2

• Это функция - она ​​детерминированная.
• Это также инъективно - f отображает разные значения для разных пар (a, b). Вы можете доказать это, используя факт: s(a+b+1)-s(a+b) = a+b+1 < a.
• Он возвращает довольно маленькие значения - хорошо, если вы собираетесь использовать его для индексации массива, поскольку массив не обязательно должен быть большим.
• Он удобен для кеширования - если две пары (a, b) близки друг к другу, то f сопоставляет им числа, которые близки друг к другу (по сравнению с другими методами).

Я не понял, что Вы имеете в виду под:

всегда должен давать целое число либо с положительной, либо с отрицательной стороны целых чисел.

Как я могу написать (больше), (меньше) символов в этом форуме?

Хотя ответ Stephan202 является единственным по-настоящему общим, для целых чисел в ограниченном диапазоне вы можете сделать лучше. Например, если ваш диапазон 0..10 000, вы можете:

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

Результаты могут соответствовать одному целому числу в диапазоне вплоть до квадратного корня из мощности целочисленного типа. Это упаковывается немного более эффективно, чем более общий метод Stephan202. Кроме того, его значительно проще декодировать; для начала, не требуя квадратных корней :)

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

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>
   

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

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

Вот расширение кода @DoctorJ на неограниченные целые числа на основе метода, заданного @nawfal. Он может кодировать и декодировать. Он работает с обычными массивами и множеством массивов.

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

Как насчет чего-то более простого: для двух чисел A и B пусть str будет конкатенацией: 'A' + ';' + 'B'. Тогда пусть на выходе будет хэш (str). Я знаю, что это не математический ответ, но простой скрипт на Python (который имеет встроенную хеш-функцию) должен выполнить эту работу.

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

A = B + C * N

где

B=A % N = B

C=A / N = C

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

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

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

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

Скажем, у вас есть 32-битное целое число, почему бы просто не переместить A в первую 16-битную половину, а B - в другую?

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


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

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

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

Даны положительные целые числа A и B, пусть D = количество цифр A, а E = количество цифр B. Результатом может быть конкатенация D, 0, E, 0, A и B.

Пример: A = 300, B = 12. D = 3, E = 2 result = 302030012. При этом используется тот факт, что единственное число, которое начинается с 0, это 0,

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

Минусы: размер результатов - это проблема. Но это нормально, почему мы все равно храним неограниченные целые числа на компьютере.

Если вам нужно больше контроля, например выделить X бит для первого числа и Y бит для второго числа, вы можете использовать этот код:

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

Всего я использую 32 бита. Идея здесь в том, что если вы хотите, например, чтобы первое число было до 10 бит, а второе число было до 12 бит, вы можете сделать это:

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

Теперь вы можете сохранить в num_a максимальное число, равное 2^10 - 1 = 1023, и в num_b максимальное значение 2^12 - 1 = 4095.

Чтобы установить значение для num A и num B:

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

Теперь bnum - это все биты (всего 32 бита. Вы можете изменить код, чтобы использовать 64 бита). Чтобы получить num a:

int a = nums_mapper.GetNumA(bnum);

Чтобы получить число b:

int b = nums_mapper.GetNumB(bnum);

РЕДАКТИРОВАТЬ: bnum можно хранить внутри класса. Я не сделал этого из-за собственных нужд. Я поделился кодом и надеюсь, что он будет полезен.

Спасибо за источник: https://www.geeksforgeeks.org/extract-k-bits-given-position-number/ для функции извлечения битов, а также спасибо mouviciel за ответ в этом посте. Используя их в источниках, я смог найти более продвинутое решение.

Мы можем закодировать два числа в одно в пространстве O (1) и времени O (N). Предположим, вы хотите кодировать числа в диапазоне 0-9 в один, например. 5 и 6. Как это сделать? Простой,

  5*10 + 6 = 56. 
   
    5 can be obtained by doing 56/10 
    6 can be obtained by doing 56%10.

Даже для двузначного целого числа, скажем, 56 и 45, 56 * 100 + 45 = 5645. Мы снова можем получить отдельные числа, выполнив 5645/100 и 5645% 100

Но для массива размера n, например. a = {4,0,2,1,3}, допустим, мы хотим закодировать 3 и 4, поэтому:

 3 * 5 + 4 = 19               OR         3 + 5 * 4 = 23
 3 :- 19 / 5 = 3                         3 :- 23 % 5 = 3
 4 :- 19 % 5 = 4                         4 :- 23 / 5 = 4

Обобщая его, получаем

    x * n + y     OR       x + n * y

Но мы также должны позаботиться об изменении значения; так что это заканчивается как

    (x%n)*n + y  OR x + n*(y%n)

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