Битовая маска сочетания, Требуется алгоритм вычисления битовой маски сочетания Опции

[Corner]

Задача из комбинаторики.
Есть сочетание из N по M. Число возможных состояний считается по известной всем формуле с факториалами. Как компактно и быстро решить обратную задачу: зная номер сочетания, получить битовую маску размером M с N битами равными лог. 1. Номер сочетания, естественно, внутри множества сочетаний.
Итерационные алгоритмы очень медленные. Табличные требуют нехилых таблиц. А хочется уложить в 1 к плиток или меньше.

Сообщение отредактировал Corner - Aug 24 2016, 08:21

[Corner]

Небольшое уточнение. Принцип нумерации масок сочетаний - любой. Главное, чтобы разные номера гарантированно давали разные маски.
ПС: прямая задача 63 из 1024 с требуемой скоростью влезает в самую толстую ПЛИС, что есть под рукой. Задача решена "в лоб".

Сообщение отредактировал Corner - Aug 24 2016, 12:01

[andyp]

Можно у гугла спросить про

unrank permutation

Сам пользовался только последовательным лексикографическим перечислением перестановок. На эту тему можно посмотреть std::next_permutation из стандаратной библиотеки с++

Ну и еще поискать на тему Gosper's hack - это быстрый способ получения следующей в лексикографическом смысле перестановки.

[Corner]

Можно у гугла спросить про
unrank permutation

Гугл знает только rank permutation.

Сам пользовался только последовательным лексикографическим перечислением перестановок. На эту тему можно посмотреть std::next_permutation из стандаратной библиотеки с++
Ну и еще поискать на тему Gosper's hack - это быстрый способ получения следующей в лексикографическом смысле перестановки.

Это итерационные методы. Уже все попробовал. На Сях замечательно выходит. А в ПЛИС места мало для такого подхода. И, еще хочется, пока используется предыдущая маска, уже посчитать следующую. Вернее, не следующую, а новую с любым положением. И на это всего несколько мс есть.
ПС: сейчас пробую скрестить итерации, конвейер и таблицу. Метод нашел, но мозги в пятой позиции от попыток написать на Сях алгоритм генерации сценария.

Сообщение отредактировал Corner - Aug 25 2016, 10:56

[andyp]

Гугл знает только rank permutation.

Unrank тоже знает. Это как раз то, что требуется - по номеру получить собственно k-перестановку.

Вот например, ссылка на с код для k-перестановок с первой страницы поискового запроса "unrank k-permutation"
https://github.com/samwgoldman/rank_permutations
Там же еще ссылки на алгоритмы вылетают. Практическую ценность оценить не могу - только бегло посмотрел.

Это итерационные методы. Уже все попробовал. На Сях замечательно выходит. А в ПЛИС места мало для такого подхода. И, еще хочется, пока используется предыдущая маска, уже посчитать следующую. Вернее, не следующую, а новую с любым положением. И на это всего несколько мс есть.
ПС: сейчас пробую скрестить итерации, конвейер и таблицу. Метод нашел, но мозги в пятой позиции от попыток написать на Сях алгоритм генерации сценария.

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

[Corner]

На той же странице автор сознается, что его к - перестановка работает некорректно))) сам алгоритм "обратный в лоб", но с ошибками.

[Corner]

Как обычно, сам все решил... мда...