|
Все перестановки 7 чисел (1,2,3,4,5,6,7) упорядочены в лексикографическом порядке, найдите перестановку с номером 2196. Я думал что, надо перевести 2196 в 7ичную сис.счисл, и подставить числа ,но оказалось не так. Хелп задан 8 Май '20 15:24 
SerbHaPilNik |
|
Эта задача имеет отношение скорее к так называемой "факториальной" системе счисления. При выписывании перестановок в лексикографическом порядке, сначала идут 6!=720 перестановок с первым символом 1, потом столько же с первым символом 2, и так далее. В числе 2196 предыдущий факториал "умещается" 3 раза: 2196=3*720+36, то есть группы с первой 1, 2, 3 проходят целиком. В нашей группе на первом месте находится 4, и далее нужно найти перестановку номер 36 на символах кроме 4. Поскольку 36 < 5!=120, перестановка находится в первой группе, когда после 4 идёт 1. Остаётся задача найти перестановку номер 36 на символах 2,3,5,6,7. В числе 36 "сидит" 4! один раз. Это даёт группу с символом 2 на третьем месте, и далее идёт символ 3. Итого у нас в начале следуют 413, и теперь ищем перестановку номер 12 на символах 2, 5, 6, 7. Легко видеть, что это последняя перестановка второй из групп по 3!=6 штук в каждой. Значит, мы должны поставить второй по величине символ 5 в начало, а оставшиеся символы расположить по убыванию: 5762. Всё вместе даёт перестановку 4135762. отвечен 8 Май '20 21:09 
falcao |