Лексикографска пермутация

[mkmarinov]

Да се намери 500-та (започваме да броим от 1) лексикографска пермутация на 0,1,2,3,4,5.

[strangerforever]

1-120 започват с 0
121-240 започват с 1
241-360 започват с 2
361-480 започват с 3
481-600 започват с 4
601-720 започват с 5

481-504 започват с 40
505-528 започват с 41
529-552 започват с 42
553-576 започват с 43
577-600 започват с 45

481-486 започват с 401
487-492 започват с 402
493-498 започват с 403
499-504 започват с 405

499-500 започват с 4051
501-502 започват с 4052
503-504 започват с 4053

499 започва с 40512
500 започва с 40513

=> 500 е 4,0,5,1,3,2

Малко bruteforce-нато, има си и общ алгоритъм, естествено.

[Гост]

Нещо с шесчична бройна сисчьема?

[mkmarinov]

Поне аз го направих с "факториелна" бройна система:
[tex]a_na_{n-1}\dots a_10_{(!)}=0.0! + a_1 1! + a_2 2! + \dots + a_n n![/tex], като имаме условието [tex]a_n \le n[/tex] (ясно е защо последната цифра винаги е 0)
Че всяко естествено число има единствено представяне е очевидно твърдение с нетрудно доказателство.
Взимаме редицата от символи [tex]\{ 0, 1, 2, 3, 4, 5 \}[/tex]; искаме и те да са лексикографски подредени.
[tex]499_{(10)} = 403010_{(!)}[/tex] (взимаме 499 вместо 500 т.к. в бройната система започваме броенето от 0, а за пермутациите - от 1)
За да получим пермутацията, взимаме n-тия символ и го "задраскваме" от множеството (като броенето започва от 0). Ще "построим" пермутацията по нейният номер в бройната система. Нека [tex]p[/tex] е нашата пермутация:
[tex]\{ 0, 1, 2, 3, 4, 5\} - 4, p=4[/tex]
[tex]\{ 0, 1, 2, 3, 5 \} - 0, p=40[/tex]
[tex]\{1, 2, 3, 5\} - 3, p=405[/tex]
[tex]\{1, 2, 3\} - 0, p=4051[/tex]
[tex]\{ 2, 3 \} - 1, p=40513[/tex]
[tex]\{2 \} - 0, p=405132[/tex]
Доказателството за верността на алгоритъма остава като упражнение за читателя .

Задачата грубо я "откраднах" от projecteuler, като оригиналът беше да се намери милионната пермутация на 0123456789 - същата работа, но големината на числата може да предизвика нужда от калкулатор .