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

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

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

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, заранее известной постоянной.
  • Я доберусь до этого рано или поздно, но, тем не менее, я бы выбрасывал это для сообщества, чтобы тем временем "развлекаться".

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

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

Связанные с этим

15.12.2008 19:21:59
Вопрос обещает быть очень интересным, за исключением того, что мне неясно, «я хочу иметь возможность, учитывая такую ​​последовательность, выполнить поиск в таблице и получить индекс в таблице, сгенерировать последовательность». Можете объяснить это немного подробнее, может быть, с примером? Спасибо.
Biswanath 15.12.2008 19:45:49
Где вопрос? Я не вижу знака вопроса?
Patrick Desjardins 15.12.2008 20:05:36
Это не Опасность. Хотя я явно не задавал вопрос, я думаю, что подразумеваемый вопрос совсем не трудно определить.
BCS 15.12.2008 20:14:33
4 ОТВЕТА
РЕШЕНИЕ

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

Давайте посмотрим на 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. Позволяет вызвать значение группы двоичного представления порядок группы .

Часть 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/2T (l, n), которые можно легко вычислить.

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

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% в верхней формуле, но она должна быть примерно такой.

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

1
8.02.2011 17:00:13
Интересно. Это не совсем касается того, как отобразить два полученных числа в целые числа в / pack / fashion, но я вижу несколько способов начать с этого.
BCS 7.12.2010 14:56:39

Это функция 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
0
15.12.2008 19:32:22
Я не ищу валидатор
BCS 15.12.2008 19:43:00

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

0
15.12.2008 19:36:57
Это потребует перечисления всего набора и последующего поиска. Вот чего я стараюсь избегать
BCS 15.12.2008 19:42:12
Хеш-часть (без сортировки) будет работать, но мне нужно будет создать идеальный хеш с несколькими тысячами записей.
BCS 15.12.2008 19:46:11

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

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

1
15.12.2008 19:53:16