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).

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...

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.

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.

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:

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?

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...

Pa to je izuzetno prosto dokazati. Pretpostavimo da je jedan od sabiraka (duzina jednog ciklusa) oblika gde je p neki prost broj a s broj ciji faktori nemaju broj p. Bolje bi bilo to rastaviti na i i da dobijemo jos neki ostatak koji mozda mozemo nekako da iskoristimo u nekom drugom sabirku a NZS se pritome ne smanjuje.
To da se dobije jos neki ostatak se lako dokaze. Ako je npr. onda
je bolje da to rastavimo u zbir jer je .

Evo sada sam ga pola sata trazio po cd-ovima (bolje da sam ponovo napisao resenje). Ovaj program sam napisao pre 8 godina dok sam jos bio u srednjoj skoli jer mi je tada nastavnik iz assemblera dao taj zadatak da resim.
Resenje je zakacrno uz poruku (valjda radi, nisam probao sada).
Ako ne uspes da ga provalis vrlo rado cu ga objasniti.