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

Ответ 1

Вы ищете биективное отображение NxN -> N. Они используются, например. dovetailing. Посмотрите этот PDF для введения в так называемые функции сопряжения. Википедия вводит определенную функцию спаривания, а именно функцию Cantor pairing:

Три замечания:

• Как ясно из других, если вы планируете реализовать функцию сопряжения, вы можете вскоре найти вам произвольно большие целые числа (bignums).
• Если вы не хотите проводить различие между парами (a, b) и (b, a), затем выполните сортировку a и b перед применением спаривания.
• Вообще-то я соврал. Вы ищете биективное отображение ZxZ -> N. Функция Кантора работает только с неотрицательными числами. Однако это не проблема, потому что легко определить биекцию f : Z -> N, например:
  • f (n) = n * 2, если n >= 0
  • f (n) = -n * 2 - 1, если n < 0

Ответ 2

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

Теперь функция Szudzik:

(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-битных входов может быть настолько непростительным!

Функция 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, который 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, которое является прохладным. Я не уверен, как сделать то же самое для функции спаривания Кантора, но не пытался, насколько это не так эффективно. Кроме того, больше вычислений, связанных с функцией спаривания Кантора, означает, что он медленнее тоже.

Вот реализация С#.

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

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

Ответ 3

Если 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;
}

Ответ 4

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

Или моя логика испорчена?

Ответ 5

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

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

Ответ 6

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

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

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

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

например.

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

Ответ 7

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 сопоставляет числа, близкие друг к другу (по сравнению с другими методами).

Я не понял, о чем вы говорите:

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

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

Ответ 8

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

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

Ответ 9

Хотя ответ 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 более общий метод. Также значительно проще декодировать; не требующих квадратных корней, для начала:)

Ответ 10

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

• Здесь неупорядоченная функция спаривания:

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

• Для 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>
  

Ответ 11

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

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

Ответ 12

Вот расширение кода @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 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

Ответ 13

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

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

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

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

Ответ 14

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

Ответ 15

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

A = B + C * N

где

B = A% N = B

C = A/N = C

Ответ 16

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

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

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

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

Ответ 17

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

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


def vec_unpack(number):
    return [number % 65536, int(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] Vector multiplication

который проходит через эти две точки