Доброго времени суток, уважаемые программисты !
Вот сегодня столкнулся с задачей : есть n элементов (1,2,3,..,n) . Нужно научиться генерировать все перестановки из n элементов с заданным количеством инверсий за разумное время.
Имеется в виду, что n>17, что делает полный перебор неприменимым .
Вот и суть вопроса - известны ли вам алгоритмы,которые помогут решить данную задачу ? Если есть какие-то мысли и не лень - выкладывайте, буду благодарен.
Пока есть мысль делать перебор с отсечением, если количество инверсий стало больше, чем задано . Но, наверное, это плохая идея . Что-то подсказывает, что можно применить динамическое программирование, но ума не приложу, как .