Перейти к содержанию
    

Битовая маска сочетания

Задача из комбинаторики.

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

Итерационные алгоритмы очень медленные. Табличные требуют нехилых таблиц. А хочется уложить в 1 к плиток или меньше.

Изменено пользователем Corner

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

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

Изменено пользователем Corner

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

 

unrank permutation

 

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

unrank permutation

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

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

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

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

ПС: сейчас пробую скрестить итерации, конвейер и таблицу. Метод нашел, но мозги в пятой позиции от попыток написать на Сях алгоритм генерации сценария.

Изменено пользователем Corner

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

 

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

 

Вот например, ссылка на с код для k-перестановок с первой страницы поискового запроса "unrank k-permutation"

https://github.com/samwgoldman/rank_permutations

Там же еще ссылки на алгоритмы вылетают. Практическую ценность оценить не могу - только бегло посмотрел.

 

 

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

ПС: сейчас пробую скрестить итерации, конвейер и таблицу. Метод нашел, но мозги в пятой позиции от попыток написать на Сях алгоритм генерации сценария.

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Гость
Эта тема закрыта для публикации ответов.
×
×
  • Создать...