Перестановки и числа


Last modified:11:20 12.02.2009
Как-то пришлось мне делать программу решения линейной системы уравнений.
Тогда не было Matcad'а, компутеры были большие и с инета не содрать...
Алгоритм Гаусса (треугольное разложение) пошел, но пришлось искать в столбце лучшие числа, чтобы меньше типа нуля делить, а потом строки переставлять и запоминать, чтобы при решении наоборот.
Получился вектор перестановки вроде 1234 =>4321.
По ходу дела обнаружилось, что этому вектору соответствует код в факториальной системе счисления.
Это значит младший разряд может принимать значения 0 и 1, следующий 0,1,2 и т.д.
Я записывал по еврейски наоборот - с начала младший.
Так вот, каждой записи в этой системе счисления соответствует определенная перестановка и наоборот:
Перестановка <=> число факториальное <=> число обычное (не римское, а совецкое).
Так, самое большое трехразрядное число в факториальной 123 =1+2*(2+3*(3))= 23 в десятичной.
Я нашел 4 варианта алгоритма туда-назад., Могу напечатать результат и прогу на TP6 если кому интересно.
Хорошо, если кто разберется и добавит новое.
Потом обнаружил, что не первый придумал [1], но все равно приятно, что сам дошел!
Зачем это надо: - генерация перестановок и, возможно, определения свойств.
Например, младший разряд определяет четность (симметричность).
Мне это пригодилось для классификации дискретных квазилуп.
Кстати, там же далее есть более общий пример для сочетаний С(n,r).

[1] Сборник задач по дискретной математике."Наука"1977 стр.254.

Используются технологии uCoz