Доброго времени суток, уважаемые программисты !
Вот сегодня столкнулся с задачей : есть n элементов (1,2,3,..,n) . Нужно научиться генерировать все перестановки из n элементов с заданным количеством инверсий за разумное время.
Имеется в виду, что n>17, что делает полный перебор неприменимым .
Вот и суть вопроса - известны ли вам алгоритмы,которые помогут решить данную задачу ? Если есть какие-то мысли и не лень - выкладывайте, буду благодарен.
Пока есть мысль делать перебор с отсечением, если количество инверсий стало больше, чем задано . Но, наверное, это плохая идея . Что-то подсказывает, что можно применить динамическое программирование, но ума не приложу, как .
Возможно я сильно туплю, поправьте.
Если надо генерить все перестановки с данным числом инверсий - асимптотически это будет в любом случае почти факториал.
Вернее Cf(k)n, что-то типа того
(я кстати не минусовал=), лично против JKeeJ1e30 ничего не имею)
Вы меня раскусили.
Так вот, задача сведена к нахождению всех таких таблиц, где выполняется ограничение ti < i и сумма всех элементов — данное количество инверсий. Это уже выглядит полегче, и можно перебором разумным находить. Потом ещё всякие оптимизации добавлять. Но количество будет всё равно большим, как уже сказали.
все перестановки, которые имеют одно количество инверсий не лежат в одной гиепрплоскости перестановочного многогранника. Тоисть они никогда не смежны.
Детали можешь узнать у меня (подойди на кафедру ПМИММ или ЕК)