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

Question

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

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

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

Answer 1

Вот расширение кода @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://stackoverflow.com/a/15391420
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

Answer 2

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

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

Answer 3

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

Answer 4

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

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

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

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

Answer 5

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

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

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

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

Answer 6

давайте будем иметь два числа B и C, кодирующие их в одно число A

A = B + C * N

, где

B = A% N = B

C = A / N = C