Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak

[es] :: Matematika :: Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak

[ Pregleda: 2190 | Odgovora: 13 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Aleksej.Alex

Član broj: 347832
Poruke: 7
*.dynamic.sbb.rs.



Profil

icon Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak19.03.2023. u 09:24 - pre 12 meseci
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!!!

[Ovu poruku je menjao Aleksej.Alex dana 19.03.2023. u 10:56 GMT+1]
 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak19.03.2023. u 12:07 - pre 12 meseci
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
Code:

1.   1 2 3 4
  2. 1 2 4 3
  3. 1 3 2 4
  4. 1 3 4 2
  5. 1 4 2 3
  6. 1 4 2 3
7.   2 1 3 4
...
13. 3 1 2 4
...
19. 4 1 2 3
...


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...
 
Odgovor na temu

B3R1
Berislav Todorovic
NL

Član broj: 224915
Poruke: 794



+630 Profil

icon Re: Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak19.03.2023. u 12:32 - pre 12 meseci
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.
 
Odgovor na temu

Aleksej.Alex

Član broj: 347832
Poruke: 7
*.dynamic.sbb.rs.



Profil

icon Re: Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak19.03.2023. u 12:43 - pre 12 meseci
Citat:
djoka_l:
Kako treba da se reše to zadaci? Da li treba da se napiše neki program, ili da se radi peške?


Potrebno je da se rese peske

 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak19.03.2023. u 12:50 - pre 12 meseci
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
 
Odgovor na temu

Aleksej.Alex

Član broj: 347832
Poruke: 7
*.dynamic.sbb.rs.



Profil

icon Re: Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak19.03.2023. u 12:50 - pre 12 meseci
Citat:
B3R1: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.


Resenje u zbirci kaze da je 50. permutacija 51397.

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

B3R1
Berislav Todorovic
NL

Član broj: 224915
Poruke: 794



+630 Profil

icon Re: Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak19.03.2023. u 13:04 - pre 12 meseci
Citat:
Aleksej.Alex: Resenje u zbirci kaze da je 50. permutacija 51397.

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:
Code (python):

#!/usr/bin/python3

import sys
from math import factorial as fact

def perm(a, r):
    n = len(a)                 # Duzina niza a
    if (r<2):                  # Kada r padne na 1 to je kraj
        return
    m = int((r-1)/fact(n-1))   # Redni broj vodeceg elementa u permutaciji
    b.append(a[m])             # Dodaj vodeci element u novi niz
    a.remove(a[m])             # Izbaci m-ti element iz originalnog niza
    r1 = r - m*fact(n-1)       # Razlika izmedju r i ukupnog broja permutacija dok a[m] ne postane vodeci
    if (r1 > 0):               # Sve dok smo u plusu - ponavljaj algoritam rekurzivno
        perm(a, r1)

# MAIN

a = [ 1, 3, 5, 7, 9]
b = []
r = 3
perm (a, r)
b = b + a
print (str(b))

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

Aleksej.Alex

Član broj: 347832
Poruke: 7
*.dynamic.sbb.rs.



Profil

icon Re: Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak19.03.2023. u 13:37 - pre 12 meseci
Citat:
B3R1: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?

[Ovu poruku je menjao Aleksej.Alex dana 19.03.2023. u 19:48 GMT+1]
 
Odgovor na temu

BrutalCoin

Član broj: 337807
Poruke: 126



+103 Profil

icon Re: Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak20.03.2023. u 01:41 - pre 12 meseci
A jel taj piton može da odredi 3715639. permutaciju skupa ["A(a", "28R4", "nK", "Ak", "28R4", "7a9j", "28R4", "L", "*-@", "124", "gx3"] ?

I koliko mu treba vremena?

 
Odgovor na temu

B3R1
Berislav Todorovic
NL

Član broj: 224915
Poruke: 794



+630 Profil

icon Re: Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak20.03.2023. u 08:57 - pre 12 meseci
Citat:
BrutalCoin: A jel taj piton može da odredi 3715639. permutaciju skupa ["A(a", "28R4", "nK", "Ak", "28R4", "7a9j", "28R4", "L", "*-@", "124", "gx3"] ?

I koliko mu treba vremena?

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:
Code (python):

>>> sorted(a)
['*-@', '124', '28R3', '28R4', '28R5', '7a9j', 'A(a', 'Ak', 'L', 'gx3', 'nK']


Permutacija koju trazis je:
Code (python):

[beri@vps1 ~]$ time ./r.py
['28R3', 'A(a', '28R4', 'Ak', '7a9j', '*-@', '124', '28R5', 'nK', 'L', 'gx3']

real    0m0.025s
user    0m0.017s
sys     0m0.008s

Gore vidis i vreme izvrsavanja.
 
Odgovor na temu

B3R1
Berislav Todorovic
NL

Član broj: 224915
Poruke: 794



+630 Profil

icon Re: Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak20.03.2023. u 09:24 - pre 12 meseci
Citat:
Aleksej.Alex:A dal bi mogla da se uradi skripta za permutacije sa ponavljanjem?

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
 
Odgovor na temu

djoka_l
Beograd

Član broj: 56075
Poruke: 3445

Jabber: djoka_l


+1462 Profil

icon Re: Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak20.03.2023. u 09:47 - pre 12 meseci
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:
Code:

prvo slovo, početna permutacija, broj permutacija, poslednja permutacija
a           1                    420               420
b           421                  140               560


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

Aleksej.Alex

Član broj: 347832
Poruke: 7
*.dynamic.sbb.rs.



Profil

icon Re: Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak20.03.2023. u 19:46 - pre 12 meseci
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.
 
Odgovor na temu

B3R1
Berislav Todorovic
NL

Član broj: 224915
Poruke: 794



+630 Profil

icon Re: Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak21.03.2023. u 12:18 - pre 12 meseci
U medjuvremenu sam osmislio i algoritam za opsti slucaj permutacija, gde se pojedini elementi mogu i da ponavljaju i on bi izgledao otprilike ovako:

* Sortiramo niz A = [ a[1], a[2], ... a[n] ] u leksikografskom poretku, od najmanjeg ka najvecem.
* Kumulativni brojac permutacija postavimo na nulu (npr. C=0)
* Za svaki unikatni element niza x definisemo funkciju R(x) koja oznacava broj ponavljanja elementa x u nizu A. Na primer, za niz [ 1, 2, 2, 2, 3, 3, 4, 4, 4, 4 ] funkcija R ce izgledati otprilike ovako: R = { 1 -> 1, 2 -> 3, 3 -> 2, 4 -> 4 }, jer je skup unikatnih elemenata niza A skup B={ 1, 2, 3, 4 }.
* Za svaki element x skupa unikatnih elemenata (B) odredimo ukupan broj permutacija ciji je vodeci element x. Taj broj se odredjuje tako sto iz originalnog niza izbacimo prvu instancu elemnta x i izracunamo ukupan broj permutacija tog "okrnjenog" niza. Znaci, pocinjemo recimo od jedinice, za koju pretpostavimo da je vodeca - iz niza A izbacimo 1 i ostaje nam [2, 2, 2, 3, 3, 4, 4, 4, 4 ]. Ukupan broj permutacija je 9!/(3!*2!*4!). Primer Python koda kojim se to racuna bi otprilike izgledao ovako:

Code (python):

def nPerm (array):
    np = fact(len(array))                      # Broj permutacija bez ponavljanja elemenata
    for elem in set(array):                    # Za svaki unikatni element niza "array" ...
        np = np / fact(array.count(elem))      # Podeli np faktorijelom broja ponavljanja elemnta
    return np

Sto je programska interpretacija poznate formule:



gde su k{i} brojevi ponavljanja elemenata iz posmatranog niza.

* Proverimo da li je zadati redni broj permutacije (r) manji od C. Ako jeste, pronasli smo vodeci element, on se garantovano nalazi u intervalu (C, P). Ako nije, kumulativnom brojacu C dodajemo broj P (C = C+P) i prelazimo na sledeci element skupa B ... postupak ponavljamo sve dok je r > C.
* Kada r postane manje od C - nasli smo vodeci element. Izbacimo prvu instancu vodeceg elementa iz originalnog niza A i ponavljamo postupak nad smanjenim nizom A'. Na primer, ako smo pronasli da je vodeci element 2, tada formiramo niz A' = [ 1, 2, 2, 3, 3, 4, 4, 4, 4 ]. Ako smo nasli da je vodeci element 3, tada je A' = [ 1, 2, 2, 2, 3, 4, 4, 4, 4 ].
* Dodamo vodeci element u novi niz - ako je to trojka u prvoj iteraciji cemo dobiti Q = [ 3 ].
* Kompletan postupak rekurzivno ponavljamo nad nizom A'.
* Krajnji rezultat je niz Q, koji ce na kraju ovog rekurzivnog postupka biti popunjen trazenom permutacijom.

Ima tu jos detalja, ali to je u grubim crtama to sto treba uraditi. Entuzijastima ostavljam punu implementaciju, nije tesko.
 
Odgovor na temu

[es] :: Matematika :: Kombinatorika: n-ta permutacija od elemenata i leksikografski poredak

[ Pregleda: 2190 | Odgovora: 13 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.