Как проиндексировать четверки целых чисел

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

Язык - C.

unsigned foo(unsigned x, unsigned y)
{
  return (x + y) * (x + y + 1) / 2 + x;
}

unsigned bar(unsigned i, unsigned j, unsigned k, unsigned l)
{
  return foo(foo(i, j), foo(k, l));
}

>тобразить их в непрерывную последовательность 1,2,3

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

> И как ты себе представляешь взаимно однозначное отображение двух множеств разных мощностей?

Если разрядность чисел не ограниченна, то все там одной мощности -- счетные множества.

Не совсем понятно условие задачи -- что значит "рандомно"?

Если все возможные четверки занумеровать -- отображение Кантора.

Если для каждого конкретного набора из n четверок найти их нумерацию -- упорядочивай их лексикографически, вот и будет тебе отображение. И любое другое будет от него отличаться лишь упорядочением.

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

> безымяной она быть не может по причине своей фундаментальности. может она все-таки имеет название?

Я не знаю названия.

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

да, согласен

Это и есть "нумерующая функция Кантора"

Канторовская фунция нумерации пар (Cantor pairing function) $\pi(k_1,k_2) := \frac{1}{2}(k_1 + k_2)(k_1 + k_2 + 1)+k_2$ обобщена (самим Кантором) до нумерации произвольных кортежей (Cantor tuple function)$\pi^{(n)}(k_1, \ldots, k_{n-1}, k_n) := \pi ( \pi^{(n-1)}(k_1, \ldots, k_{n-1}) , k_n)$ .

>Если разрядность чисел не ограниченна, то все там одной мощности -- счетные множества.

И вот тут с мы падаем с высот математики и бъемся лбом об машинную прозу. Если элементы четверки имеют разрядность 32 бита, то для отображения кортежей на множество целых чисел нам понадобится 128 разрядов. Проблем, в общем-то нет, но побурчать мне хочется%)

Огромное спасибо.
Числа по 2 байта :)

>Огромное спасибо. Числа по 2 байта :)

Тогда всё намного более очевидно: f(x)=x1+x2*2^16+x3*2^32+x4*2^48.

> Тогда всё намного более очевидно...

Я так и не понял постановку проблемы...

Если речь идет об отображении 4-х 16-битных чисел в одно 64-битное, то все, действительно, очевидно, (только я бы сложения с умножениями на ORы со сдвигами заменил). Если же надо переменумеровать "без дырок" заданный (случайный) набор из n четверок, то это не прокатит, надо их упорядочить в массив, а массив проиндексировать.

> И вот тут с мы падаем с высот математики и бъемся лбом об машинную прозу.

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

Есть набор квартетов:
{i_1,j_1,k_1,l_1}
{i_2,j_2,k_2,l_2}

и т.д.

N штук.

"Random" значит что индексы меняются в произвольном порядке, т.е. если у меня есть
{i_k,j_k,k_k,l_l}

то вовсе не обязательно что у меня в моем наборе найдется

{i_k+1,j_k,k_k,l_k} или {i_k,j_k+1,k_k,l_k} или {i_k,j_k,k_k+1,l_k}
или {i_k,j_k,k_k,l_k+1}


Проблема вот такая. Каждому такому квартету сопоставлено число double.
То есть есть массив двойной точности и размерности N - Prop. Необходима функция F, которая получая на вход квартет возвращала бы соответствующее ему число Prop(F(i,j,k,l)). Судя по всему это решаетша посредством хэша:

{i,j,k,l} -> IJKL (unique)

Hash: IJKL-> Pos (position in Prop )

Такое отображение будет делатьсы много раз (10^12) ...

> Такое отображение будет делатьсы много раз (10^12) ...

Да!

Как я понял, речь идет о том, чтобы для _заданного_ набора из n четверок найти 10^12 раз соответсвующий индекс этой четверки.

Надеюсь, ты понял, что для начала надо как-то упорядочить четверки в массиве. Далее нужно массив проиндексировать.

Хэш тут поможет, но -- опять же, с точностью до постановки задачи.

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

Если тебе надо при отсутствии квартета его добавить (то есть тебе надо как можо раньше определить, имеется такой квартет в базе, или он новый) , то лучший вариант -- префиксное дерево (если память позволяет), или бинарное дерево (тормознет в двоичный логарифм раз по сравнению с хэшом, зато память сэкономит, и в среднем быстрее определить отсутствующий узел); ну, если все уж ОЧЕНЬ толстое, то B+ дерево на диске, индексирующее массив на том же диске.

Удачи!