Блог

Знаете ли вы какой-либо способ получить k-й элемент комбинации длиной в m элементов в O (1)? Ожидаемое решение должно работать для любого размера входных данных и любого m-значения.

Позвольте мне объяснить эту проблему на примере (код python):

 >>> import itertools
>>> data = ['a', 'b', 'c', 'd']
>>> k = 2
>>> m = 3
>>> result = [''.join(el) for el in itertools.combinations(data, m)]
>>> print result
['abc', 'abd', 'acd', 'bcd']
>>> print result[k-1]
abd
  

Для заданных данных k-м (2-м в данном примере) элементом комбинации из m элементов является abd. Возможно ли получить это значение (abd) без создания всего комбинаторного списка?

Я спрашиваю, потому что у меня есть данные ~ 1 000 000 символов, и невозможно создать полный комбинаторный список длиной в m символов, чтобы получить k-й элемент.

Решением может быть псевдокод или ссылка на страницу, описывающую эту проблему (к сожалению, я ее не нашел).

Спасибо!

http://en.wikipedia.org/wiki/Permutation#Numbering_permutations

В принципе, выразить индекс в факториальной системе счисления и использовать его цифры в качестве выборки из исходной последовательности (без замены).

Не обязательно O (1), но следующее должно быть очень быстрым:

Возьмите оригинальный алгоритм комбинаций:

 def combinations(elems, m):
    #The k-th element depends on what order you use for
    #the combinations. Assuming it looks something like this...
    if m == 0:
        return [[]]
    else:
        combs = []
        for e in elems:
            combs  = combinations(remove(e,elems), m-1)
  

Для n начальных элементов и m длины комбинации мы имеем n!/(n-m)!m! общее количество комбинаций. Мы можем использовать этот факт, чтобы перейти непосредственно к нашей желаемой комбинации:

 def kth_comb(elems, m, k):
    #High level pseudo code
    #Untested and probably full of errors
    if m == 0:
        return []
    else:
        combs_per_set = ncombs(len(elems) - 1, m-1)
        i = k / combs_per_set
        k = k % combs_per_set
        x = elems[i]
        return x   kth_comb(remove(x,elems), m-1, k)
  

сначала вычислите r = !n/(!m*!(n-m)) с помощью n количество элементов

тогда floor (r / k) — это индекс первого элемента в результате,

удалите его (сдвиньте все следующее влево)

выполните m—, n— и k = r%k

и повторяйте, пока m не будет равно 0 (подсказка, когда k равно 0, просто скопируйте следующие символы в результат)

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

1. Выводит все K-индексы в удобном формате для любого N выбранного K файла. K-индексы могут быть заменены более описательными строками или буквами. Этот метод делает решение такого рода задач довольно тривиальным.

2. Преобразует K-индексы в соответствующий индекс записи в отсортированной таблице биномиальных коэффициентов. Этот метод намного быстрее, чем более старые опубликованные методы, которые основаны на итерации. Он делает это, используя математическое свойство, присущее Треугольнику Паскаля. Об этом говорится в моей статье. Я считаю, что я первый, кто открыл и опубликовал эту технику, но я могу ошибаться.

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

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

5. Класс написан на .NET C # и предоставляет способ управления объектами, связанными с проблемой (если таковые имеются), с использованием универсального списка. Конструктор этого класса принимает значение bool с именем InitTable, которое при значении true создаст общий список для хранения объектов, которыми нужно управлять. Если это значение равно false, то оно не создаст таблицу. Таблицу не нужно создавать, чтобы выполнить 4 вышеуказанных метода. Для доступа к таблице предусмотрены методы доступа.

6. Существует связанный тестовый класс, который показывает, как использовать класс и его методы. Он был тщательно протестирован в 2 случаях, и известных ошибок нет.

Чтобы прочитать об этом классе и загрузить код, смотрите Таблицу биномиального коэффициента.

Преобразовать этот класс в Java, Python или C не должно составить труда.