Ограниченная последовательность для отображения индекса

Question

Я ломаю голову над тем, как отобразить набор последовательностей в последовательные целые числа.

Все последовательности следуют этому правилу:

A_0 = 1
A_n >= 1
A_n <= max(A_0 .. A_n-1) + 1

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

Пример: для длины 3 есть 5 действительных последовательностей. Быстрая функция для выполнения следующей карты (желательно в обоих направлениях) была бы хорошим решением

1,1,1   0
1,1,2   1
1,2,1   2
1,2,2   3
1,2,3   4

---

• Цель упражнения - получить упакованную таблицу с отображением 1-1 между действительными последовательностями и ячейками.
• Размер множества ограничен только числом возможных последовательностей.
• Сейчас я не знаю, какой будет длина последовательности, но она будет маленькой, <12, заранее известной константой. </li>
• Рано или поздно я доберусь до этого, но, тем не менее, я бы выложил это для сообщества, чтобы тем временем "повеселиться".

---

это разные допустимые последовательности

1,1,2,3,2,1,4
1,1,2,3,1,2,4
1,2,3,4,5,6,7
1,1,1,1,2,3,2

это не

1,2,2,4
2,
1,1,2,3,5

---

Относится к this

Answer 1

Существует естественная индексация последовательности, но ее не так просто вычислить.

Давайте поищем A_n для n> 0, так как A_0 = 1.

Индексация выполняется в 2 этапа.

Часть 1:

Группировка последовательностей по местам, где A_n = max (A_0 .. A_n-1) + 1. Назовите эти места шаги .

• На шагах идут последовательные номера (2,3,4,5, ...).
• В нешаговых местах мы можем поставить числа от 1 до количества шагов с индексом меньше k.

Каждая группа может быть представлена ​​в виде двоичной строки, где 1 - шаг, а 0 - не шаг. Например. 001001010 означает группу с 112aa3b4c, a <= 2, b <= 3, c <= 4. Поскольку группы индексируются двоичным числом, происходит естественная индексация групп. От 0 до 2 ^ длина - 1. Позволяет вызвать значение двоичного представления группы <em>порядок группы .

Часть 2:

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

Легко рассчитать количество последовательностей в одной группе. Это номер формы 1 ^ i_1 * 2 ^ i_2 * 3 ^ i_3 * ....

Объединение:

Это дает ключ из 2 частей: <Steps, Group> Затем его необходимо сопоставить с целыми числами. Чтобы сделать это, мы должны найти, сколько последовательностей в группах, у которых порядок меньше некоторого значения. Для этого давайте сначала выясним, сколько последовательностей в группах заданной длины. Это может быть вычислено, проходя через все группы и суммируя количество последовательностей или подобное с повторением. Пусть T (l, n) будет числом последовательностей длины l (A_0 опущено), где максимальное значение первого элемента может быть n + 1. Чем держит:

T(l,n) = n*T(l-1,n) + T(l-1,n+1)
T(1,n) = n

Поскольку l + n <= sequence length + 1 есть ~ sequence_length^2/2 T (l, n) значений, которые можно легко вычислить.

Далее следует рассчитать количество последовательностей в группах на порядок меньше или равный заданному значению. Это можно сделать суммированием значений T (l, n). Например. количество последовательностей в группах с порядком <= 1001010 двоичных, равным </p>

T(7,1) +         # for 1000000
2^2 * T(4,2) +   # for 001000
2^2 * 3 * T(2,3) # for 010

Оптимизация:

Это даст отображение, но прямая реализация для объединения ключевых частей в лучшем случае будет >O(1). С другой стороны, часть ключа Steps мала, и, вычисляя диапазон Groups для каждого значения Steps, таблица поиска может уменьшить это значение до O(1).

Я не уверен на 100% в верхней формуле, но должно быть что-то вроде этого.

С этими замечаниями и повторениями можно составить последовательность функций -> индекс и индекс -> последовательность. Но не так тривиально: -)

Answer 2

Я думаю, что хеш без сортировки должен быть.

Поскольку A0 всегда начинается с 0, возможно, я думаю, что мы можем думать о последовательности как о числе с основанием 12 и использовать его основание 10 в качестве ключа для поиска. (Все еще не уверен в этом).

Answer 3

Учитывая последовательность, я бы отсортировал ее, а затем использовал бы хэш отсортированной последовательности в качестве индекса таблицы.

Answer 4

Это функция Python, которая может выполнить эту работу за вас, при условии, что вы сохранили эти значения в файле и передали строки в функцию

def valid_lines(lines):
    for line in lines:
        line = line.split(",")
        if line[0] == 1 and line[-1] and line[-1] <= max(line)+1:
            yield line

lines = (line for line in open('/tmp/numbers.txt'))
for valid_line in valid_lines(lines):
    print valid_line