Алгоритм определения уникальности двух чисел

[Sirius]

Долго думал где ставить, решил всё таки в математике, так как думаю решается математически всё-таки

Помогите разобраться с алгоритмом.

Допустим есть два числа a и b или b и a - так вот надо сделать, чтобы результат алгоритма (любого действия) этих двух чисел вне зависимости от их расположения был уникальным.

Числа могут быть только целыми, не более 4 млрд.

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

Прошу в большей степени тех, кто уже сталкивался с таким алгоритмом - не хочу придумывать велосипед!

[незваный гость]

$2^{32} a + b$

Я полагаю, это не то, что Вы хотите услышать, но это вполне отвечает Вашему условию. Я привел пример, чтобы помочь Вам точнее сформулировать, что же Вам нужно.

[vbn]

попробуйте операцию деления

[незваный гость]

vbn писал(а):

попробуйте операцию деления

$\frac12 = \frac24$ -- и этот пример не уникален...

[незваный гость]

Кажется я начинаю понимать Вас. Вам нужна $hash(x,y)$ такая, что $hash(x,y)=hash(y,x)$, и $hash(x,y)=hash(z,t )\Rightarrow \{x,y\} =\{z,t\}$. правильно ли я Вас понял?

[yvanko]

Всего пар 32-битных чисел порядка числа 64-битных чисел так что ничего намного превосходящего
$2^{32}min(a,b)+max(a,b)$ не придумать

[незваный гость]

Можно обобщить для произволного числа чисел -- сортируем, и используем сортированный массив как hash.

Кстати, уникальных пар $2^{63}+2^{31}$, то есть с учетом уникальности в 63 бита никак не влезем.

[yvanko]

Ну так нам и не надо влезать в 63 бита - у нас их 64.
(к программистской части - когда у нас будет число, бельшее $2^{63}-1$, оно вылезет за переделы типа и станет раным $-2^{63}$и далее, но при этом разные числа будут оставаться разными.)

[Sirius]

незванный гость - да правильно поняли. Но hash кажется имеет так называемые коллизии - он не уникален!

Я думаю сделать просто float max(a,b) , min(a,b) (но тут дробная с нулями будет резаться вроде)

a и b - если а и b 32 бит по идее должны создать матрицу значений до 2 в 63 степени - вот только как сделать чтобы результаты были уникальными - и возможно ли вообще?

[незваный гость]

Sirius писал(а):

незванный гость - да правильно поняли. Но hash кажется имеет так называемые коллизии - он не уникален!

hash() может иметь столкновения. Строго говоря, hash() -- это функция, действующая из пространства своих аргументов в некоторое новое пространство (обычно целых чисел). Поскольку обычно пространство аргументов шире, то и возникают столлкновения (они же collision). Классический пример hash() -- md5() -- вычисление криптографически надежной контрольной суммы.

Sirius писал(а):

Я думаю сделать просто float max(a,b) , min(a,b) (но тут дробная с нулями будет резаться вроде)

Не понял. А чем 64 битное целое плохо? Переходя к float, Вы неминуемо теряете уникальность (или заметно раширяете размер числа.

Sirius писал(а):

a и b - если а и b 32 бит по идее должны создать матрицу значений до 2 в 63 степени - вот только как сделать чтобы результаты были уникальными - и возможно ли вообще?

См. выше ответyvanko

[MrD]

По сути Вам нужно отображение шахматной доски на 64 целых числа, или шахматного поля NxN -> N^2 (N=4 млрд.). От N^2, при условии абсолютной уникальности, никуда не денешься, а дальше обычная позиционная система счисления - a*N+b. Для коммутативности в качетсве "a" надо, например, выбрать меньшее число. Hash применяется когда надо отобразить NxN -> N, из за этого и возникают коллизии.

[незваный гость]

MrD писал(а):

Hash применяется когда надо отобразить NxN -> N, из за этого и возникают коллизии.

hash применяется в нескольких случаях. Один -- когда нужно прейти к более узкому множеству. Другой -- когда нужно обеспечить равномерность заполнения таблицы. Во втором случае размер hash"а может и совпадать с исходным -- кого это интересует.

Кстати, я бы не рискнул настаивать на $N \times N \to N$. Отображение строки в целое число под это определение вряд ли подпадет...

[MrD]

незванный гость писал(а):

Кстати, я бы не рискнул настаивать на $N \times N \to N$. Отображение строки в целое число под это определение вряд ли подпадет...

Согласен, правильно наверное о hash сказать так: отображение A->[1..n], где n меньше мощности A. Но я не стремился к точности, лишь хотел показать источник коллизий.
А ситуация, когда мощности совпадают имеет лишь теоретический смысл, imho.