Разработка схемы индексации для списка всех неубывающих последовательностей

Question

Предположим, что мы рассматриваем отсортированный список всех неубывающих последовательностей со значениями в диапазоне (1, max_num) и num_slots элементов в каждой последовательности, как я могу найти индекс некоторой заданной последовательности-члена за O(1) времясложность?Я на самом деле не , учитывая весь список заранее, я просто хочу найти индекс некоторой последовательности-члена, в которой содержится список всех существующих последовательностей.

Для конкретного примера предположим, что max_num = 3 и num_slots = 4.Тогда есть 15 последовательностей (или вообще, есть (max_num + num_slots - 1) choose (num_slots) последовательностей):

[[1, 1, 1, 1],
 [1, 1, 1, 2],
 [1, 1, 1, 3],
 [1, 1, 2, 2],
 [1, 1, 2, 3],
 [1, 1, 3, 3],
 [1, 2, 2, 2],
 [1, 2, 2, 3],
 [1, 2, 3, 3],
 [1, 3, 3, 3],
 [2, 2, 2, 2],
 [2, 2, 2, 3],
 [2, 2, 3, 3],
 [2, 3, 3, 3],
 [3, 3, 3, 3]]

Таким образом, учитывая входные данные последовательности, такие как [1, 2, 2, 3] вместе с информацией max_num = 3, я пытаюсь написатьфункция, которая возвращает правильный индекс 7. У меня нет списка всех последовательностей для работы.

---

Справочная информация

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

def gen(max_num, num_slots, l = None): 
    if l is None: 
        l = [[1] * num_slots] 
    cur = l[-1].copy() 
    for i in reversed(range(num_slots)): 
        if cur[i] < max_num: 
            cur[i] += 1 
            for j in range(i+1, num_slots): 
                cur[j] = cur[i] 
            l.append(cur) 
            return gen(max_num, num_slots, l) 
    return l

Answer 1

Существует биекция из k-подмножеств {1...n} (с повторением) в k-подмножеств {1...n + k − 1} (без повторения) путем сопоставления {c_0, c_1...c_(k−1)} с {c_0, c_(1+1), c_(2+2)...c_(k−1+k−1)} (см. здесь ).

После преобразования просто используйте вашу любимую утилиту для ранжирования комбинаций.

[3, 3, 3, 3]  -->  [3, 4, 5, 6]
[2, 3, 3, 3]  -->  [2, 4, 5, 6]
[2, 2, 3, 3]  -->  [2, 3, 5, 6]
[2, 2, 2, 3]  -->  [2, 3, 4, 6]
[2, 2, 2, 2]  -->  [2, 3, 4, 5]
[1, 3, 3, 3]  -->  [1, 4, 5, 6]
[1, 2, 3, 3]  -->  [1, 3, 5, 6]
[1, 2, 2, 3]  -->  [1, 3, 4, 6]
[1, 2, 2, 2]  -->  [1, 3, 4, 5]
[1, 1, 3, 3]  -->  [1, 2, 5, 6]
[1, 1, 2, 3]  -->  [1, 2, 4, 6]
[1, 1, 2, 2]  -->  [1, 2, 4, 5]
[1, 1, 1, 3]  -->  [1, 2, 3, 6]
[1, 1, 1, 2]  -->  [1, 2, 3, 5]
[1, 1, 1, 1]  -->  [1, 2, 3, 4]

import pyncomb

def convert(m, S):
  return (m + len(S) - 1, [ x-1 + i for x,i in zip(S, list(xrange(len(S)))) ])

def rank(m, S):
  k, s = convert(m, S)
  return pyncomb.ksubsetcolex.rank(k, s)

print rank(3, [1,2,2,3])
# 7

Answer 2

Для каждой цифры найдите разницу между этой и самой младшей цифрой.Добавьте 1 для каждой измененной позиции справа от любой измененной цифры

idx = 0;
for i in range(0,num_slots):
    d = SEQ[i]
    idx += d-min_num
    if (d > min_num):
        idx += num_slots-1 - i

Например:
[1,1,1,3] равно 0 + 0 + 0 + (2+0) или 2
[1,2,3,3] равно 0 + (1+2) + (2+1) + (2+0) или8
[3,3,3,3] - это (2+3) + (2+2) + (2+1) + (2+0) или 14

Answer 3

Я подробно остановлюсь на ответе @ DavidFrank о том, почему это O (length + max_num), и приведу более понятный пример (тоже немного более сложный).

Для начала заметим:

Предположим, что полная серия возможна в F (длина, max_num) = X

Тогда для всех возможностей в X, начинающихся с 1, например [1, ....], у нас есть счет F (длина-1, max_num) в этой группе.

Для всей возможности в X, которая не начинается с 1, например [2, ....] или [3, ....], у нас есть счет F (length, max_num-1) .

Таким образом, мы можем использовать рекурсию, чтобы получить это в O (длина * max_num) (может стать O (length + max_num), если мы используем памятку) число сложности:

# This calculate the total number of X of possible entry given (length, max_num)
def calc_sum(length, max_num):
    if max_num == 1:
        return 1
    elif length == 1:
        return max_num
    else:
        total = calc_sum(length-1, max_num) + calc_sum(length, max_num-1)
        return total

Теперь мы рассмотрим результат, чтобы увидеть, можем ли мы сделать это O (1):

# This is clearly not going to make it O(1), so now we need some generalizations to NOT run this recursion.
import numpy as np
arr = np.zeros((6,6))
for i in range(6):
    for j in range(6):
        arr[i, j] = calc_sum(i+1, j+1)
print(arr)

Результат:

[[  1.   2.   3.   4.   5.   6.]
 [  1.   3.   6.  10.  15.  21.]
 [  1.   4.  10.  20.  35.  56.]
 [  1.   5.  15.  35.  70. 126.]
 [  1.   6.  21.  56. 126. 252.]
 [  1.   7.  28.  84. 210. 462.]]

Это треугольник Паскаля, если смотреть по диагонали на верхний правый угол.Диагонали треугольника Паскаля определяются как (x выберите y)

. Это дает понять, что это не может быть O (1) и, по крайней мере, будет O (length + max_num), потому что это общая сложность(Выбрать) функцию.

Мы прошли весь путь, чтобы доказать, что решение O (1) невозможно, если мы не ограничим (length + max_num) постоянным.

# We can expand by solving it now:
from scipy.special import comb # this is choose function.

def get_index(my_list, max_num):
    my_list = np.array(my_list)
    if len(my_list) == 1:
        return my_list[0] - 1
    elif my_list[0] == 1:
        return get_index(my_list[1:], max_num)
    elif my_list[0] != 1:
        return get_index(my_list - 1, max_num - 1) + comb(len(my_list)-2+max_num, max_num-1)

get_index([1,2,2,3],3) # 7

Совокупная сложность конечной функции с comb() по-прежнему равна O (длина + max_num), поскольку сложность всего, что находится за пределами comb, также равно O (длина + max_num).

Answer 4

Это O(|seq| + max_num).Обратите внимание, что это все еще намного быстрее, чем простой метод генерации всего и поиска, который является экспоненциальным в |seq|.

Идея состоит в том, что вы подсчитываете последовательности перед входной последовательностью.Например, вы хотите знать, что такое индекс [2, 4, 5, 6], когда max_num = 6.

• Count [1, *, *, *]
• Count [2, 2, *, *]
• Count [2, 3, *, *]
• (Примечание: вы не можете считать [2, 4, *, *], потому что тогдавы должны включить [2, 4, 6, 6] после вашего ввода. Вы всегда должны идти на единицу меньше, чем ваш ввод по указанному индексу)
• Количество [2, 4, 4, *]
• Количество [2, 4, 5, 5]

(для каждой строки вы можете использовать свою формулу (max_num + num_slots - 1) choose (num_slots) и суммировать их)

def combinations(slots, available):
    return choose(slots + available - 1, slots)

def find_index(seq, max_num):
    res = 0
    for digit_index in xrange(len(seq)):
        prev = seq[digit_index - 1] if digit_index > 0 else 1
        for digit in xrange(prev, seq[digit_index]):
            res += combinations(len(seq) - digit_index - 1, max_num - digit + 1)
    return res


print find_index([1, 2, 2, 3], 3)