Комбинация нескольких чисел в одном

[sungmaster]

Допустим, у нас есть пронумерованные элементы массива. Курсор первого уровня (КПУ) - настоящий номер элемента. Курсор второго уровня (КВУ) - рекурсивная структура, в которой есть один КПУ и один КПУ/КВУ.

Если в качестве операции слияния курсоров использовать сумму, то имели бы примерно такую ситуацию: есть КПУ 1, 2, 4. Первый КВУ $1+2=3$; второй - $4+3=7$ (в моем случае сумма не подходит).

К КВУ ставится два условия: должна быть возможность обратного разложения курсора на его предков (полученный КПУ можно проверить на корректность); КВУ не должен превышать некоторого значения (в целях економии памяти). Глубина рекурсии заранее неизвестна.

Какие есть алгоритмы слияния чисел, удовлетворяющие возникшие условия?

[slavav]

Пусть КПУ принадлежит диапазону $[0, N-1]$.
Введём операции, которые реализуют стек из КПУ (s - стек, i значение КПУ):

empty(s)
    return s == 0

push(s, i)
    assert 0 <= i < N
    return s * (N + 1) + (i + 1)

pop(s)
    assert not empty(s)
    return s / (N + 1) # целочисленное деление

top(s)
    assert not empty(s)
    return s % (N + 1) - 1

[sungmaster]

В даной ситуации такой вариант не подходит, т.к. N где-то $2^{32}$, а глубина стека может быть больше 100. Для системы расход памяти критический, поэтому диапазон значений КВУ тоже должен быть ограничен (и желательно чтобы он занимал меньше 8 байт)

[arseniiv]

Можно попробовать что-то такое: Есть стандартная функция $f\colon\mathbb N\times\mathbb N\to\mathbb N$ (ноль включаем в натуральные), $f(m, n) = m + \frac{(m+n)(m+n+1)}2$, правда, для её обращения надо считать квадратный корень. Теперь можно отобразить КПУ только на нечётные числа ($a\mapsto 2a+1$), а коды пар — на чётные (умножаем на два), что всегда даст определить, из чего состоит пара. Это универсально, но может не подходить в деталях (например, корень не нравится). Можно использовать тот же подход, но с другой функцией для кода пары. Например, если для хранения компонент пары достаточно $a$ и $b$ бит, можно приписать их друг к другу, а к этому ещё приписать код $a$ (или $b$ — если одна из компонент имеет тенденцию быть короче другой, здесь есть смысл брать соответствующее ей число бит). Код, например, вот такой. Целочисленный sqrt для разбора полученного числа вычислять не понадобится. Если размер каждого поля может быть до 32 бит, и притом того фиксированного — только чётным их числом, можно прямо кодировать $a/2$ четырьмя битами, хотя выглядит всё равно как-то расточительно.

В общем, задача и сама странная.

[slavav]

sungmaster в сообщении #1081283 писал(а):

В даной ситуации такой вариант не подходит, т.к. N где-то $2^{32}$, а глубина стека может быть больше 100. Для системы расход памяти критический, поэтому диапазон значений КВУ тоже должен быть ограничен (и желательно чтобы он занимал меньше 8 байт)

Число различных стеков фиксированной высоты $i$ равно $N^i$.
Число различных стеков высоты не более $n$ равно $\sum\limits_{i=0}^{n}N^i = \frac{N^{n+1} - 1}{N - 1}$.
Каждый стек должен быть представлен своим уникальным числом. Для $N = 2^{32}$, $n = 100$ число стеков $\frac{2^{3232} - 1}{2^{32} - 1} \approx \frac{2^{3232}}{2^{32}} = 2^{3200}$.
Такое количество стеков требует для своего размещения $3200 / 8$ байт. Вам нужно 400 байт (на самом деле 401). Или не все стеки могут быть представлены?

[aa_dav]

slavav в сообщении #1081320 писал(а):

Вам нужно 400 байт

хуже:

sungmaster в сообщении #1081250 писал(а):

Глубина рекурсии заранее неизвестна.

sungmaster в сообщении #1081283 писал(а):

глубина стека может быть больше 100

[sungmaster]

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

[slavav]

sungmaster в сообщении #1081337 писал(а):

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

Несколько мыслей:
1. Если у вас есть эффективный способ хранения номера родителя относительно потомка, то $N$ сильно уменьшается.
2. Если вы хотите хранить сотню элементов готовьте сотни бит.
3. Можно обратный путь хранить прямо в узлах графа, если структура данных и алгоритм позволяют.
4. Можно обратный путь хранить в стеке процедур, если поиск рекурсивный и в каждый момент времени вам нужен только один путь.
5. Нужно больше данных об алгоритме и окружении в котором он должен работать, чтобы продолжать разговор.

[sungmaster]

Предположим, что есть такой граф. Он хранит все 3-хбуквенные наборы, содержащие 'a' и 'b'

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

Хранение номера родителя в узле не оправдано, если родителей несколько, поскольку всё равно нужно каким-то образом указать, в какому из родителей нужно вернуться.

[aa_dav]

sungmaster

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

Рекомендую ознакомится с: http://meta.ru.stackoverflow.com/questi ... xy-problem (прокрутите чуть ниже до "Что такое 'ошибка X-Y'?")

[slavav]

Попробуем выжать всё что можно из числового стека.
Для каждого узла перенумеруем его предков. Количество предков узла обозначим $v(i)$, где $i$ - номер узла. Я буду нумеровать предков в диапазоне $[0, v(i) - 1]$. Пусть заданы функции abs_pred и rel_pred:

abs_pred(i, j):
    assert 0 <= i < N
    assert 0 <= j < v(i)
    return ? # абсолюный номер j-ого предка относительно узла i

rel_pred(i, ii):
    assert 0 <= i < N # абсолютный номер потомка
    assert 0 <= ii < N # абсолютный номер предка
    return ? # относительный номер предка ii для узла i

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

Тогда:

empty(s):
    # получаем номер узла
    i = s % N
    return v(i) == 0 # если нет предков, значит стек кончился

top(s):
    # получаем номер узла
    i = s % N
    return i

pop(s):
    # выталкиваем номер узла
    i = s % N
    s = s / N

    assert v(i) != 0

    # выталкиваем номер предка относительно потомка
    j = s % v(i)
    s = s / v(i)

    # получаем абсолютный номер предка
    ii = abs_pred(i, j)

    # заталкиваем абсолютный номер предка в стек
    s = s * N + ii

    return s

push(s, i):
    assert 0 <= i < N

    # выталкиваем номер узла
    ii = s % N
    s = s / N

    # номер вытолкнутого узла относительно нового узла
    j = rel_pred(i, ii)
    
    # заталкиваем относительный номер
    s = s * v(i) + j

    # заталкиваем абсолютный номер нового узла
    s = s * N + i

    return s

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

[sungmaster]

А можно показать работу этого алгоритма на каком-то примере?

aa_dav в сообщении #1081373 писал(а):

Рекомендую ознакомится с: http://meta.ru.stackoverflow.com/questi ... xy-problem (прокрутите чуть ниже до "Что такое 'ошибка X-Y'?")

В даном случае суть вопроса ближе к "что можно забить микроскопом".

Как один из вариантов, можно использовать какой-то алгоритм слияния (хоть и

arseniiv в сообщении #1081289 писал(а):

$f(m, n) = m + \frac{(m+n)(m+n+1)}2$

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

[rockclimber]

(Оффтоп)

aa_dav в сообщении #1081373 писал(а):

Рекомендую ознакомится с: http://meta.ru.stackoverflow.com/questi ... xy-problem (прокрутите чуть ниже до "Что такое 'ошибка X-Y'?")

Гораздо более понятным (и исторически первым в рунете, насколько я понимаю) описанием "проблемы XY", на мой взгляд, является это: http://www.gunsmoker.ru/2008/10/x-y-z.html

[aa_dav]

rockclimber в сообщении #1081413 писал(а):

Гораздо более понятным (и исторически первым в рунете, насколько я понимаю) описанием "проблемы XY", на мой взгляд, является это: http://www.gunsmoker.ru/2008/10/x-y-z.html

Плюсую. И это не оффтоп. Здесь это - не оффтоп.

sungmaster в сообщении #1081410 писал(а):

...потом получать остачу от деления на большое простое число, а при восстановлении угадывать первоначальное число.

Не надо забивать микроскопом. Не надо.

[slavav]

sungmaster в сообщении #1081410 писал(а):

А можно показать работу этого алгоритма на каком-то примере?

sungmaster в сообщении #1081351 писал(а):

Вот примеры путей для узлов. $N = 100$ для наглядности.

i v(i) стек        s
1   0  1             1
2   1  0,2           2
3   2  0,1,3       103
4   1  0,1,0,4     104
5   2  0,1,0,1,5   305
6   1  0,1,0,1,0,6 306