Можно ли получить k-й элемент комбинации m-символ-длина в O (1)? - PullRequest
Новая
       2

Можно ли получить k-й элемент комбинации m-символ-длина в O (1)?

6 голосов
/ 16 мая 2011

Знаете ли вы, как получить 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 символов, и невозможно создать полный комбинаторный список длиной в м-символ, чтобы получитьk-й элемент.

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

Спасибо!

Ответы [ 4 ]

5 голосов
/ 16 мая 2011

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

Обычно выражают индекс в системе факторных чисел и используют его цифры в качестве выбора из исходной последовательности (без замены).

1 голос
/ 16 мая 2011

Не обязательно 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)
0 голосов
/ 25 сентября 2012

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

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

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

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

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

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

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

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

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

0 голосов
/ 16 мая 2011

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

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

уберите его (сдвиньте все влево)

делай m--, n-- и k = r% k

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

...