sciencetalk

wie kan mij helpen met het volgende probleem (uitleg).

de getallen van 9 cijfers die gevromd worden door de cijfers 1,2,3,4,5,6,7,8,9.

worden naar grootte gerangschikt. in de rij die ontstaat staat 123456789 vooraan.

welk getal staat op de 100.000-ste plaats.

alvast bedankt!

voor als het niet helemaal duidelijk is,

het gaat van klein naar groot.

123456798. dan komt 123456879,123456897....enz tot 987654321

Tof probleem, Ik heb een methode gevonden die toch wel wat rekenwerk vereist...

Als je het probleem herleidt valt er iets op. De getallen zijn in groepjes te verdelen.

Voorbeeld: tot 4 cijfers 1 tot 4 met als eerste 1234

We verkrijgen een rij van 4! = 24 getallen.

1234

1243

1324

1342

1423

1432

2134

...

Die getallen vallen te verdelen in 4 groepen van 6 (24 mogelijkheden / aantal mogelijkheden voor de eerste plaats)

Stel dat ik het 17e getal zoek, dan weet ik zeker dat dit begint met een 3. (de eerste 6 beginnen met 1, de volgende 6 met 2 enz...)

Hierna kan je het 2 getal vinden. Daar heb ik je immers nog 3 mogelijkheden, te verdelen over 6. Ze vallen te splitsen in groepjes van 2. We zochten het 17e getal (zonder de 12 van de eerste 2 groepen hebben we nog het 5e getal over). Hierdoor zijn we zeker dat dit getal in het groepje zit dat begint met een 34.

Nu hebben we nog 2 mogelijkheden over, en dit te verdelen over 2 groepjes. Hier is het vrij logisch dat het volgende getal 1 moet zijn. Het complete 17e getal is dus 3412 (het 18e getal is 3421 en het 19 begint met een 4)

Hetzelfde principe kan je toepassen op 9 cijfers en de 100 000 ste plaats. Wel wat werk.. Er bestaat waarschijnlijk een kortere methode voor?

Grappig om dit weer eens te zien.

Onlangs heb ik dit probleem ook opgelost bij Project Euler met een algoritme.

Door slim de getallen te wisselen kon ik alle permutaties maken en dan de 1.000.000e vinden.

Later kwam ik ook het wiki-artikel erover tegen met het algoritme dat de stappen beschrijft.

Met de methode van dietervdf is het nog mogelijk om dit wat sneller te doen door een ander start punt te nemen en alleen de benodigde permuaties te maken.

paac schreef: ↑vr 25 okt 2013, 10:26
Met de methode van dietervdf is het nog mogelijk om dit wat sneller te doen door een ander start punt te nemen en alleen de benodigde permuaties te maken.

Ik had het nog niet getest, maar als je alleen het 100.000e getal wilt hebben, dan kan met de methode van dietervdf het probleem dmv pen/papier/rekenmachine in een paar stappen worden uitgerekend(had voor mezelf het algoritme nodig, dus niet in deze methode verdiept eerst).

Voorbeeld van Project Euler met 0 t/m 9 en 1 miljoenste positie gaat dan als volgt

Er zijn 10! mogelijkheden welke zijn te verdelen in 10 * 9! sub-permutaties, dan ga je 9! met 1 t/m 10 vermenigvuldigen en kijken op welke positie hij boven de waarde 1.000.000 komt

Voor begin getal 0 gaat van positie 1 t/m 1 * 9! = 362.880

Voor begin getal 1 gaat van positie 362.881 t/m 2 * 9! = 725.760

Voor begin getal 2 gaat van positie 725.761 t/m 3 * 9! = 1.088.640

Hij komt boven de 1.000.000, dus het eerste getal van de permutatie is 2.

Neem een nieuwe permutatie zonder 2 (ofwel 0, 1, 3, 4, 5, 6, 7, 8, 9) en berekend de rest-waarde

100.000.000 - 725.760 = 274.240

Herhaal nu met voor 1 t/m 9 en 8! (het is nu 8! omdat er één mogelijkheid minder is)

Voor begin getal 0 gaat van positie 1 t/m 1 * 8! = 40.320

Voor begin getal 1 gaat van positie 40.321 t/m 2 * 8! = 80.640

Voor begin getal 3 gaat van positie 80.641 t/m 3 * 8! = 120.960

Voor begin getal 4 gaat van positie 120.961 t/m 4 * 8! = 161.280

Voor begin getal 5 gaat van positie 161.281 t/m 5 * 8! = 201.600

Voor begin getal 6 gaat van positie 201.601 t/m 6 * 8! = 241.920

Voor begin getal 7 gaat van positie 241.921 t/m 7 * 8! = 282.240

Hij komt boven de 274.240, dus het tweede getal van de permutatie is 7.

Neem een nieuwe permutatie zonder 7 (ofwel 0, 1, 3, 4, 5, 6, 8, 9) en berekend de rest-waarde

274.240 - 241.920 = 32.320

Dit kun je blijven herhalen totdat je de permutatie hebt.

Hetzelfde principe werkt ook voor jou vraagstuk