Исходная задача такая. Дана группа всех конечных перестановок натуральных чисел. Надо их перенумеровать (отсортировать) так, чтобы в начале шла тривиальная перестановка, потом перестановка 2-х чисел, потом перестановки, затрагивающие числа вплоть до 3, потом вплоть до 4-х, пяти и так далее. Иными словами, нужна такая последовательность перестановок, чтобы под номерами от 1 до n! включительно стояли перестановки, оставляющие все числа, бОльшие n, на месте. Причем все это нужно в контексте прикладного софта - то есть чтобы в код ложилось аккуратно.
Навскидку я нашел статью, где утверждается, что "естественный" порядок перестановок - это словарная сортировка, но она моему требованию не удовлетворяет. Там номер перестановки в последовательности зависит от степени рассматриваемой группы. Что неприемлемо.
Я эту задачу решил - нашел две таких последовательности (мог бы и еще - там решений беск. много), одну красиво алгоритмизировал - причем как туда, так и обратно, как из номера перейти к перестановке и как от перестановки к номеру, и расписал на Си. Работает, и требования по скорости/памяти приличные. Вторую тоже алгоритмизировал - но не так красиво. Теперь есть сильное чувство, что изобрел велосипед.
Наверняка у этой задачи есть классическое решение. Кто знает, как это правильно делается и где расписано? Ответы от читавших Кнута приветствуются. :)) |
e-mail: 
