Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak

Pozdrav svima!! Zadaci koji slede su nivo IV godine srednje skole(dakle, ucili smo samo osnove kombinatorike, obrasce i sl. nikakve algoritme za resavanje i sl). Nemam apsolutno ideju kako ni da pocnem a kamoli da resim.
Molim vas za objasnjenja zadataka tj. postupka resavanja, nacin razmisljanja, principa resavanja a ne samo resenje.
Posebno ne razumem ovo sa 589. ili 1099. tj. n-tom permutacijom. A isto tako ne razumem u cemu je razlika u permutaciji od permutaciji od tih i tih elemenata i permutaciji u leksikografskom poretku,a o sto je to u 1. zadatku pod a i b. Mozda tu i jeste problem. Kada bih znao kao se one formiraju i odredjuju, onda bi i zadatak resio.
Rec je o sledecim zadacima:

1.
a) Odredi 1099. permutaciju od elemenata a,a,a,b,c,d,d,d;
b) Odredi 1100. permutaciju (u leksikografskom poretku) od elemenata aaabcddd;
v) Koja je po redu permutacija AVALA od po;etne permutacije AAALV?;
g) Odredi 55. permutaciju (u leksikografskom poretku) od elemenata aaabcc;
d) Koja je po redu (u leksikografskom poretku) permutacija:
- MATEMATIKA od pocetne permutacije AAAEIKMMTT;
- KOMBINATORIKA od pocetne permutacije AABIIKKMNOORT;

2.
a) Odrediti 1841. permutaciju od elemenata a, b, c, d, e, f, g.;
b) Odrediti 50. permutaciju elemenata 1,3,5,7,9;
v) Odrediti 389. permutaciju od elemenata 1,2,3,4,5,6.


Hvala svima unapred na posvecenom vremenu i pomoci!!!

Kako treba da se reše to zadaci? Da li treba da se napiše neki program, ili da se radi peške?

Evo da ti dam ideju.
Uzmi permutacije bez ponavljanja od 4 elementa. recimo 1,2,3,4
Tih permutacija ima 4!=24
Ako treba da generišeš sve permutacije i poređaš ih u rastućem redosledu, prva permutacija bi bila 1234, poslednja (24. permutacija bi bila 4321).
E sada, kada poređaš permutacije u rastućem redosledu, na početku MORAJU da budu permutacije koje počinju sa 1 (jer je jedan prvi i najmanji element)

Dakle permutacije koje počinju sa 1 izgledaju 1 x x x
Koliko tih permutacija ima?
Pošto smo broj jedan fiksirali na prvom mestu, onda ih ima 3!, jer je ostalo da permutujemo 3 preostala elementa.
Onda redosled ide
prva permutacija 1 x x x
SEDMA permutacija 2 x x x
TRINASETA permutacija 3 x x x
Devetnaesta: 4 x x x


Isto ide i sa permutacijama sa ponavljam.
U prvom zadatku, prva permutacija MORA da počne sa "a", pa onda izračunaš koliko prostali elemnti prave permutacija.
Posle permutacija koje počinju sa "a" idu permutacije koje počinju sa B i tako dalje...

Leksikografski poredak ti je klasicna sort() funkcija - sortiranje po abecednom redu (a < b < c < ... < z), kod numerickih podataka je to ocigledno (0 < 1 < 2 ... < 9). Znaci, AAB < ABA < BAA ... Kada ispises sve permutacije na papiru i sortiras ih od najmanjeg ka najvecem, treba da odredis N-ti broj po redu.

Uzmi konkretno ovaj (2b) - imas 5 razlicitih cifara, pa je matematicki gledano ukupan broj permutacija 5! = 5*4*3*2*1 = 120, a trazi se 50-ta permutacija po redu. Ako fiksiras jedinicu na vodecem mestu i permutiras ostale cetiri cifre dobijas: 13579, 13597, 13759, 13795, 13957 itd. Ukupan broj permutacija sa fiksiranom vodecom jedinicom je 4!, s obzirom da se 4 preostale cifre permutiraju. Najmanja permutacija je 13579, najveca je ocigldno 19753 i to je 24-ta po redu. Nakon nje, prvi sledeci najmanji broj koji mozes da napises od tih 5 cifara je 31579 i to je 25-ta po redu. Ako trojku fiksiras na prvom mestu i krenes da permutiras 4 preostale cifre dobijas: 31579, 31597, 31759, 31795, 31957 ... i tako redom. Posto se 4 cifre permutiraju a prva je fiksna opet imas 24 permutacije, pri cemu je prva 31579, a poslednja 39751. Ta poslednja je 48. u ukupnom nizu. Do 50 ti ostaju jos dve. Prvi najmanji broj iza 39751 je 51379, a naredni je 53197 i to je ujedno 50-ta permutacija.

Opsti slucaj se moze izvesti ovako: posmatras niz od n razlicitih elemenata - [ a1, a2 ... an ]. Ako fiksiras prvu cifru, a permutiras ostale imas ukupno (n-1)! permutacija, nakon cega, po leksikografskom poretku, a2 postaje vodeci element niza. Uocavamo da se vodeci element uvek menja na svakih (n-1)! permutacija, vodeca dva elementa na svakih (n-2)! permutacija ... vodecih k elemenata na svakih (n-k)!. Ako sa r oznacimo redni broj permutacije koji se trazi u zadatku, permutaciju sa tim rednim brojem odredjujemo ovako:

* Posmatramo niz A = [ a[1], a[2], ... a[n] ].
* Odredimo redni broj elementa iz niza koji je vodeci u permutaciji - on ce biti m = int((r-1)/(n-1)!)+1, gde je int() celobrojna vrednost. U nasem slucaju, m = int(49/4!)+1 = int(49/24)+1 = 3.
* Odredimo ukupan broj permutacija dok dok m-ti element originalnog niza nije postao vodeci, to je ocigledno (m-1)*((n-1)!) = 2*24 = 48. Izracunamo razliku izmedju r i tog broja, odnosno: r' = r - (m-1)*((n-1)!). U nasem slucaju to je 50 - 48 = 2.
* Izbacimo element a[3] iz niza i formiramo novi niz B = [ a[1], a[2], a[4], a[5] ... a[n] ] koji ce imati n' = n-1 elemenata, u nasem slucaju to je 4.
* Ponavljamo gornji postupak nizom B - redni broj vodeceg elementa u nizu B je m' = int((r'-1)/(n'-1)!)+1 = int((2-1)/3!)+1 = 1 - znaci, prvi element u novom nizu je vodeci a to je 1.
* I tako dalje - postupak se ponavlja rekurzivno.

I tako dalje. Ok, ovo gore je vec za nivo redovnih studija, a ne srednje skole. :-)

Slicno moze da se izvede i sa ponavljanjem.

Potrebno je da se rese peske

Pa, počni

Evo prvi zadatak pod a)
Da li 1099. permutacija počinje sa a?
Ako fiksiraš "a" na prvom mestu, preostaje ti 7 slova: a a b c d d d
Tih slova ima 7 od kojih se a ponavlja 2 puta, a d 3 puta. Dakle tih permutacija ima 7!/(2!*3!)=420
Permutacije 1 - 420 počinju sa a. Dakle nismo našli 1099. permutaciju.
Fiksiraj b (to su permutacije od broja 421 pa na dalje) pa probaj da li stižeš do 1099

Resenje u zbirci kaze da je 50. permutacija 51397.

A kako onda da radim kontra kao zadatku 1. pod d?

Da, sitna greska - nakon 51379 zaista dolazi 51397. A inace, evo i programa koji implementira algoritam koji sam opisao, inace program je resio tacno kao sto je u zbirci. Uzgred, smatram da taj opsti slucaj ipak nije za nivo redovnih gimnazija, vec pre za studije ili Matematicku gimnaziju. I da, program radi samo za razlicite elemente, mada je verovatno lako da se doradi da radi i za slucaj kada se elementi ponavljaju:

Isti program za (2v) daje: 421635 - mozes da proveris u zbirci da li je tako. :-)

Da, tacno je...jos samo da python prevedem na matematicki jezik

_{[Ovu poruku je menjao Aleksej.Alex dana 19.03.2023. u 19:46 GMT+1]}

Radi tacno i sa slovima...mislim slovima dodelim brojeve resi ih i samo resenje prebacim u brojeve.

A dal bi mogla da se uradi skripta za permutacije sa ponavljanjem?

Kao sto sam gore napisao, elementi moraju da budu razliciti, tako da sam malcice preradio taj tvoj niz gore:
a = ["A(a", "28R3", "nK", "Ak", "28R4", "7a9j", "28R5", "L", "*-@", "124", "gx3"]

Prva permutacija je zapravo leksicki sortirani niz:


Permutacija koju trazis je:

Gore vidis i vreme izvrsavanja.

Naravno da moze. Stavise, verujem da postoji gotov algoritam za to koji su Donalt Knuth, Edsgar Dijkstra ili neke njima slicne face osmislile odavno pre nas ovde. :-)

Evo ti objasnjen kod na tu temu:

https://www.baeldung.com/cs/permutations-with-repetition

Evo da ti objasnim kako da rešiš prvi zadatak pod a:

a) Odredi 1099. permutaciju od elemenata a,a,a,b,c,d,d,d;

Ovde imaš permutaciju 8 elemenata sa ponavljanjem, 3, 1, 1, 3 tih permutacija ima 8!/(3!*3!)=1120, pa zadatak ima rešenje.

U leksikografskom poretku , prvo idu permutacije kojima je "a" na prvom mestu
a x x x x x x x
Onaj ostatak od 7 x-ova sadrži a a b c d d d
Sada posmatramo broj permutacija skupa od 7 elemenata kod kojih ima 2 i 3 ponavljanja (jedno a je na prvom mestu, pa jeostalo 2 a, a od pre imamo 3 d)
Broj ovih permutacija je 7!/(2!*3!)=420
Kada je b na prvom mestu, tada opet imamo permutacije od 7 elemenata ali 3 i 3 ponavljanja (ponovo imamo 3 a i 3 d), pa je broj permutacija 7!/(3!*3!)=140

napravi tabelu za svako slovo na prvom mestu:


Kada nađeš okoji opseg upada 1099. permutacija, onda napravi tabelu za dva slova, pa za 3 slova itd.

Hvala puno!
Shvatio i skoro sve resio.
Posto sam malo umoran ovaj 1. pod d sam ostavio za sutra, jer mi se cini da treba sa mnogo koncentracije da se radi ali i da ima dosta racunanja.