Поиск минимума среди произведений перестановок

[INGELRII]

Есть некоторое множество перестановок заданной длины $a_1, a_2, ..., a_n$, и есть некая перестановка $b$. Считаем, что перестановка $x$ меньше перестановки $y$, если первые $k$ элементов в них совпадают, и элемент перестановки $x$ с номером $k+1$ меньше элемента перестановки $y$ с номером $k+1$ (ну то есть обычный лексикографический порядок). Можно ли найти наименьшую перестановку среди всех $a_1 b, a_2 b, ..., a_n b$ быстрее, чем выполнив все умножения и собственно найдя перебором из всех результатов?

[grizzly]

INGELRII в сообщении #1281954 писал(а):

Можно ли найти наименьшую перестановку среди всех $a_1 b, a_2 b, ..., a_n b$ быстрее, чем выполнив все умножения и собственно найдя перебором из всех результатов?

Наверняка можно. Вот что сразу приходит в голову. Найдём первые элементы всех этих перестановок и отбросим лишние. Если заданные перестановки разные, то какая-то оптимизация гарантированно будет.