Corner 0 24 августа, 2016 Опубликовано 24 августа, 2016 (изменено) · Жалоба Задача из комбинаторики. Есть сочетание из N по M. Число возможных состояний считается по известной всем формуле с факториалами. Как компактно и быстро решить обратную задачу: зная номер сочетания, получить битовую маску размером M с N битами равными лог. 1. Номер сочетания, естественно, внутри множества сочетаний. Итерационные алгоритмы очень медленные. Табличные требуют нехилых таблиц. А хочется уложить в 1 к плиток или меньше. Изменено 24 августа, 2016 пользователем Corner Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Corner 0 24 августа, 2016 Опубликовано 24 августа, 2016 (изменено) · Жалоба Небольшое уточнение. Принцип нумерации масок сочетаний - любой. Главное, чтобы разные номера гарантированно давали разные маски. ПС: прямая задача 63 из 1024 с требуемой скоростью влезает в самую толстую ПЛИС, что есть под рукой. Задача решена "в лоб". Изменено 24 августа, 2016 пользователем Corner Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
andyp 9 25 августа, 2016 Опубликовано 25 августа, 2016 · Жалоба Можно у гугла спросить про unrank permutation Сам пользовался только последовательным лексикографическим перечислением перестановок. На эту тему можно посмотреть std::next_permutation из стандаратной библиотеки с++ Ну и еще поискать на тему Gosper's hack - это быстрый способ получения следующей в лексикографическом смысле перестановки. Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Corner 0 25 августа, 2016 Опубликовано 25 августа, 2016 (изменено) · Жалоба Можно у гугла спросить про unrank permutation Гугл знает только rank permutation. Сам пользовался только последовательным лексикографическим перечислением перестановок. На эту тему можно посмотреть std::next_permutation из стандаратной библиотеки с++ Ну и еще поискать на тему Gosper's hack - это быстрый способ получения следующей в лексикографическом смысле перестановки. Это итерационные методы. Уже все попробовал. На Сях замечательно выходит. А в ПЛИС места мало для такого подхода. И, еще хочется, пока используется предыдущая маска, уже посчитать следующую. Вернее, не следующую, а новую с любым положением. И на это всего несколько мс есть. ПС: сейчас пробую скрестить итерации, конвейер и таблицу. Метод нашел, но мозги в пятой позиции от попыток написать на Сях алгоритм генерации сценария. Изменено 25 августа, 2016 пользователем Corner Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
andyp 9 25 августа, 2016 Опубликовано 25 августа, 2016 · Жалоба Гугл знает только rank permutation. Unrank тоже знает. Это как раз то, что требуется - по номеру получить собственно k-перестановку. Вот например, ссылка на с код для k-перестановок с первой страницы поискового запроса "unrank k-permutation" https://github.com/samwgoldman/rank_permutations Там же еще ссылки на алгоритмы вылетают. Практическую ценность оценить не могу - только бегло посмотрел. Это итерационные методы. Уже все попробовал. На Сях замечательно выходит. А в ПЛИС места мало для такого подхода. И, еще хочется, пока используется предыдущая маска, уже посчитать следующую. Вернее, не следующую, а новую с любым положением. И на это всего несколько мс есть. ПС: сейчас пробую скрестить итерации, конвейер и таблицу. Метод нашел, но мозги в пятой позиции от попыток написать на Сях алгоритм генерации сценария. Извините, тут уж ничем особо помочь не могу - как и говорил, сам только последовательный перебор перестановок делал. Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Corner 0 25 августа, 2016 Опубликовано 25 августа, 2016 · Жалоба На той же странице автор сознается, что его к - перестановка работает некорректно))) сам алгоритм "обратный в лоб", но с ошибками. Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
Corner 0 30 августа, 2016 Опубликовано 30 августа, 2016 · Жалоба Как обычно, сам все решил... мда... Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться