Milionowa permutacja

silvaran · Post autor: **silvaran** » 11 lip 2012, o 19:46

3124 jest jedną z możliwych permutaci cyfr 1, 2, 3 i 4. Jeśli wszystkie permutacje są posortowane liczbowo (od najmniejszej do największej) nazywamy to porządkiem leksykograficznym. Dla 0,1 i 2 będzie to:

012
021
102
120
201
210

Jaka jest milionowa permutacja w porządku leksykograficznym cyfr 0, 1, 2, 3, 4, 5, 6, 7, 8 i 9?

PS. Znam odpowiedź na to pytanie, bo sam je wczoraj rozwiązałem Można spróbować napisać program, który to wyznaczy, ale według mnie chyba szybciej jest chwilę pomyśleć i za pomocą kartki oraz ołówka rozwiązać to

ksisquare · Post autor: **ksisquare** » 12 lip 2012, o 10:25

A mój kalkulator ma od tego guzik

Kod: Zaznacz cały
http://pari.math.u-bordeaux.fr/
> numtoperm(10,0)
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

PARI/GP > numtoperm(10,1)
[10, 9, 8, 7, 6, 5, 4, 3, 1, 2]

PARI/GP > numtoperm(10,1000000)
[2, 5, 10, 7, 1, 4, 3, 9, 8, 6]

PARI/GP > numtoperm(10,1000001)
[1, 5, 10, 7, 2, 4, 3, 9, 8, 6]

silvaran · Post autor: **silvaran** » 14 lip 2012, o 12:00

Twój kalkulator układa to w odwrotnej kolejności niż jest to w zadaniu...

Odpowiedź na zadanie to:

odp:

miodzio1988 · Post autor: **miodzio1988** » 14 lip 2012, o 15:37

Nie jest to takie trudne wystarczy chwilę się zastanowić. Jaka będzie pierwsza cyfra?

Powiedzmy, że zero. Gdybyśmy mieli zero to zostaje nam do rozłożenia takie liczby:

\(\displaystyle{ 1, 2, 3, 4, 5, 6, 7, 8 i 9}\)

ich kombinacji jest \(\displaystyle{ 9!=362880}\)

więc do miliona nie doskoczymy.

Powiedzmy, że jeden. Gdybyśmy mieli jeden to zostaje nam do rozłożenia takie liczby:

\(\displaystyle{ 0, 2, 3, 4, 5, 6, 7, 8 i 9}\)

ich kombinacji jest \(\displaystyle{ 9!=362880}\). Po dodaniu mamy \(\displaystyle{ 725760}\), znowu nie mamy miliona.

Powiedzmy, że dwa. Gdybyśmy mieli dwa to wreszcie przekroczymy milion. Więc musi stać dwójka na początku.

I teraz z każdą następną cyfrą postępujemy analogicznie. Widzisz na jakiej zasadzie to działa? Na kartce w ten sposób zrobisz to. Fajne, nie? ;]

Pop[rawiłem literówke

OQO · Post autor: **OQO** » 14 lip 2012, o 16:50

Czemu 8! a nie 9!

miodzio1988 · Post autor: **miodzio1988** » 14 lip 2012, o 16:53

\(\displaystyle{ 9!}\) oczywiście. Nawet tak policzone jest

silvaran · Post autor: **silvaran** » 14 lip 2012, o 16:59

miodzio1988 pisze:I teraz z każdą następną cyfrą postępujemy analogicznie. Widzisz na jakiej zasadzie to działa? Na kartce w ten sposób zrobisz to. Fajne, nie? ;]

Wiem, że fajnie bo dokładnie tak sam to rozwiązałem

miodzio1988 · Post autor: **miodzio1988** » 14 lip 2012, o 17:06

Chyba łatwiejszego sposobu nie ma, więc po co temat? ;]

silvaran · Post autor: **silvaran** » 14 lip 2012, o 17:47

Uznałem zadanie za ciekawe i chciałem się podzielić na forum.

luka52 · Post autor: **luka52** » 14 lip 2012, o 18:56

Zadanie fajne, takie akurat na Kangura lub podobny konkurs.
Zatem odpowiadając na pytanie miodzio1988 - "po jajco"

ksisquare · Post autor: **ksisquare** » 14 lip 2012, o 20:38

@silvaran: w pamięci potrafię zamienić
10 -> 0
9 -> 1
...
2 -> 8
1 -> 9
i kolejność jest akuratna

luka52 · Post autor: **luka52** » 14 lip 2012, o 20:43

ksisquare, ale i tak po "zamianie" nie wyjdzie 2783915460, kalkulator inaczej to liczy.

silvaran · Post autor: **silvaran** » 15 lip 2012, o 00:00

ksisquare, dokładnie to miałem na myśli co napisał luka52