Zanimljiv zadatak za razmisljanje.

Ko hoce da vezba vijuge moze da pokusa da resi ovaj zadatak.

Prvo mali zadacic za vezbu. Ako imamo neku permutaciju brojeva od 1 do n i ako ta prva permutacija predstavlja nacin kako premestamo brojeve koliki je minimalni broj koraka da bismo dobili pocetnu permutaciju. Evo primera. Imamo permutaciju (3,1,2,4). Svaki broj u permutaciji oznacava na koje mesto treba premestiti odgovarajuci broj.
U prvom koraku ce (3,1,2,4) da predje u (1,2,3,4)
U drugom koracu ce (1,2,3,4) da predje u (2,3,1,4) (premestanje radimo u skladu sa pocetnom permutacijom (3,1,2,4))
U trecem koraku ce (2,3,1,4) preci u (3,1,2,4)

Znaci trebalo nam je 3 koraka. Znaci u prvom zadatku nadjite minimalni broj koraka menjanja permutacije da bi smo dobili pocetnu permutaciju.
To je lak zadatak, a sad malo tezi.

Treba napraviti algoritam koji za uneti broj n odstampa jednu permutaciju koja ce zahtevati maksimalni broj koraka da bismo dobili pocetnu permutaciju.
Prakticno trazimo maksimum svih minimuma svih mogucih permutacija.

Ubih se da dešifrujem navedeni primer. Da ponovim šta predstavlja:

Imamo (3, 1, 2, 4). Premeštanje u skladu s permutacijom znači ovde da prvi član permutacije (trojka) ide na treću poziciju (baš zbog te trojke). Dalje, drugi član (jedinica) ide na prvu poziciju, pa treći član ide na drugu i četvrti ostaje na četvrtoj. Tako se dobija (1, 2, 3, 4).
Dalje opet po pravilu: prvi na treću, drugi na prvu i treći na drugu poziciju...

Da postavim smelu hipotezu: za svaku permutaciju od 1 do n se po ovoj igri nakon prvog koraka dobija (1, 2, ..., n).

Potpis

BoxUp
interesantna logička igra
Monty Hall paradoks - interaktivni demo

Sto se tice smelosti, bio si u pravu, jeste uvek pocetna permutacija.
Sto se tice ovog maksimuma, rekla bih da je to permutacija koja ima redni broj
1+(n!/2) gde pod rednim brojem podrazumevam leksikografski redosled permutacija, pa onda njenu poziciju u tom redosledu.

Pa nije bas. Tih permutacija ima dosta a tvoj algoritam treba da ispise bilo koju od njih.
Probaj prvo da resis laksi deo zadatka. Znaci da nadjes posle koliko koraka se dobija pocetna permutacija. To ne bi trebalo da bude bruteforce jer to dosta traje za neke permutacije od npr. 100 brojeva. Probaj matematicki da vidis koliko koraka je potrebno. Ako permutaciju predstavis grafom mozda ce ti biti lakse da dodjes do resenja.

Naravno da ima mnogo permutacija, pogotovo za veliko n...
Jos jednom da ponovimo, zadas n i trazis permutaciju koja ce imati najvise koraka da bi se premestanjem koje ona definise, vratili do pocetne permutacije. Da li je tako?
Pod pretpostavkom da je to tako, mislim da je trazena permutacija (jedna od onih koja zadovoljava zadati kriterijum) permutacija koja se nalazi na poziciji 1+(n!/2), a da se ona posle generise nije tesko.

Svodi se na cikluse u grafu.

U primeru (3, 1, 2, 4) postoje 2 ciklusa: prvi ciklus su pozicije 1, 2 i 3, a drugi pozicija 4.
Dužina svakog ciklusa jednaka je broju pozicija u njemu, predstavlja broj koraka do povratka u početno stanje. U primeru je prvi ciklus dužine tri, a drugi dužine jedan.
Zbir dužina jednak je ukupnom broju pozicija - u primeru je to četiri.
Broj koraka do rešenja je najmanji zajednički sadržilac dužina svih ciklusa. U primeru su tri koraka (3 * 1 = 3).

Problem se preslikava na rastavljanje broja na sabirke tako da se dobije maksimum najmanjeg zajedničkog sadržioca sabiraka. U primeru:
4 = 4 => 4
4 = 3 + 1 => 3
4 = 2 + 2 => 2
4 = 2 + 1 + 1 => 2
4 = 1 + 1 + 1 + 1 => 1

A to je već neka druga matematika...

Potpis

BoxUp
interesantna logička igra
Monty Hall paradoks - interaktivni demo

Tako je! I trazim broj koraka. U stvari i ne moras da das permutaciju, dovoljno je broj koraka jer ako znas da napravis algoritam za to onda je lako naci i permutaciju.


Nisi u pravu.
Evo za n=4 ti mislis da je trazena permutacija 3124 sto nije tacno jer nam to daje samo 3 koraka a maksimalno je 4 kako je to novikorisnik pokazao.

Tako je! Mada nije trebalo da vam kazem da crtate graf, bilo bi zanimljivije da ste se sami setili toga :-)


Bravo! Resio si pola zadatka. To je laksi deo. Sada treba naci maksimum svih NZS-ova.

Recimo za n=5 najbolje je da imas dva ciklusa, jedan duzine 2 i jedan duzine 3 i to ce ti dati NZS=6
Posle kako izaberes te cikluse je manje bitno. Fora je naci duzine ciklusa koje daju najveci NZS.

E da, maksimum NZS-ova mislim da ne moze da se nadje nekom formulom vec treba da smislis neki algoritam koji ce brzo da da resenje.

Što već neko nije našao formulu?
Da, tek sam skontao da tema nije u forumu matematike. Nešto lepo da se isprogramira. Brute force?

Opet jedna hipoteza: traženi maksimum ima za sabirke samo proste brojeve i njihove stepene.

Odakle mi ovo? Ako su sabirci takvi, NZS će biti njihov prost proizvod...

... i kad dobijemo tražene sabirke (po algoritmu brute force ili onom koji tek treba da se pojavi), kako prikazati jednu od permutacija iz skupa rešenja?

Primer:
za n = 10 rešenje je iz tri ciklusa, po rastavljanju 10 = 2 + 3 + 5.
permutacija (2, 1, 5, 3, 4, 10, 6, 7, 8, 9) dobija se cikličnim šiftovanjem prva dva elementa (1, 2 -> 2, 1), zatim sledeća tri (3, 4, 5 -> 5, 4, 3) i poslednjih pet (? -> ?).

...

Zadatak za Art of Programming:
- odrediti funkciju koja za parametar ima prirodni broj i koja vraća niz sabiraka tog broja, takav da je najmanji zajednički sadržilac sabiraka maksimalan.

Potpis

BoxUp
interesantna logička igra
Monty Hall paradoks - interaktivni demo

Ne znam. Ovaj zadatak je cini mi se bio na jednoj olimpijadi iz programiranja.

Tacna ti je hipoteza.


Nemoj molim te brute force :-))
Zadatak je naci neki algoritam koji ce ti odmah napisati resenje. Ne treba ni sekunda da prodje.

Bas na nacin kako si pokazao. Resio si sve matematicki sta je moglo matematicki a sada ostaje da se nadje neki lep algoritam koji ce da resi problem. Ja sam koristio dinamicko programiranje.


Upravo na ovo se svodi pocetni zadatak. To je najvazniji i najtezi deo.

Voleo bih da vidim tvoje rešenje - recimo za dva dana - bez obzira da li se u međuvremenu postavi neka ispravna funkcija.

Potpis

BoxUp
interesantna logička igra
Monty Hall paradoks - interaktivni demo

Evo malo JS


prim je jedan pametni niz prostih brojeva.
prim.get (index) vraća prosti broj odgovarajućeg indexa: 0 => 2, 1 => 3, 2 => 5, ...

funkcija vraća mahimalni nzs svih kombinacija sabiraka prirodnog broja (po hipotezi da se rešenje sastoji samo od prostih brojeva i njihovih stepena).

poziv funkcije nije proizvoljan, već oblika maxnzs (broj, 0, 1) - za kršenje ovog pravila ne snosim posledice.

i konačno, tu je zakačena kompletna aplikacija koja daje, recimo za pomenuti ulaz 10:

Potpis

BoxUp
interesantna logička igra
Monty Hall paradoks - interaktivni demo

Poznat mi je ovaj zadatak, bavio sam se ja svojevremeno dosta tim takmicenjima iz programiranja.
Ono sto se secam, probacu da nadjem neki kontraprimer, je da dinamicko programiranje ne mora da da tacno resenje za ovaj problem. U vecini slucajeva hoce, ali generalno mislim da sam problem ne zadovoljava neke kriterijume za optimalnost resenja dinamickim programiranjem. (tu postoje neke matematicke strukture, matroidi, zaboravio sam vec sve to sad).
Cak nisam ni siguran da hipoteza o prostim brojevima stoji.

Naravno, ovo su samo moja secanja dok ne nadjem kontraprimer.

Mada sam i ja ovako resavao taj zadatak na jednom takmicenju, tamo je formulacija bila o nekoj deci koja prave neki krug i igraju ili tako nesto, nebitno.

Šta mu dođe pojam dinamičkog programiranja? Ja ili pojma nemam ili sam zaboravan. Hajde, da znam o čemu se priča.

Interesuje me sada kakvu primenu može da ima ova tema (neka permutacija, je li). Neko kriptovanje?

I još jedno pitanje: koliko ima rešenja za dato n?

Potpis

BoxUp
interesantna logička igra
Monty Hall paradoks - interaktivni demo

Ovo mi nije jasno. Pa dinamicko programiranje ne menja resenje vec samo nacin dolazenja do resenja tako sto npr. pamtis u nekom nizu/matrici medju korake.


Pa uvek mozes da imas neki ostatak ali fazon je da se prvo biraju prosti brojevi i njihovi stepeni ali moze da se desi da ti ostane neki ostatak koji ne mozes da iskoristis.

Pa to ti je ono kad pamtis medju korake pa ih iskoristis kada ponovo naletis na njih a ne da ides stalno u rekurziju. Tako bi ti mogao da unapredis tvoju funkciju mada ono radi dovoljno brzo i kada uneses broj 100. Cekas samo par sekundi, mada kada sam ja to resavao imao sam 25 Mhz pa bi tvoje resenje radilo malo duze dok je moje trenutno davalo rezultat. Probaj da napravis algoritam tako da ti ne ide uvek u rekurziju nego iskoristi to ako je vec prolazio kroz tu funkciju sa istim argumentima. Kao kada pravis program za nalazenje puta kroz lavirint pa umesto da svaki put ides na nove 4 strane ti pamtis u matrici da li si bio na tom novom polju i koliko ti je koraka trebalo pa ako je bilo potrebno manje koraka ti onda ne ulazis u rekurizju.

Inace ne radi ti program u svim slucajevima. Moj program za broj 100 daje sledece resenje:
100 *** Niz: 19 17 13 11 7 5 9 16 3 NZS: 232792560
a tvoj daje manji NZS.
Isto tako i za recimo 21
21 *** Niz: 7 5 3 4 2 NZS: 420
a tvoj daje NZS 330


Pa mozda, nisam se bavio time. Znam da PGP algoritam koristi velike proste brojeve pa isto ima permutaciju kojom kriptuje. Ti kada bi odredjen broj puta kriptovao informaciju sa istim kljucem dobio bi pocetnu informaciju. Ali problem je sto to zahteva puno vremena pa je zato prakticnije da probas nekim algoritmima da nadjes kontra-permutaciju kojom mozes da iz kodirane informacije dobijes originalnu.

U pravu si za ove primere. Umesto

bolje je

i još neke sitnije izmene u ostatku za ispravan ispis rešenja. To je opet u fajlu uz poruku.

Kako da budemo sigurni da je rešenje pravo, ako nigde ne stoji dokaz hipoteze o obliku rešenja?

Srki, stigao je red da objaviš svoje rešenje...

Potpis

BoxUp
interesantna logička igra
Monty Hall paradoks - interaktivni demo