MATEMANIJA

Data je permutacija [inlmath]43215[/inlmath] elemenata [inlmath]1,2,3,4,5[/inlmath]. Napisati njene susjedne permutacije.
E ovako, logično je da će jedna susjedna permutacija biti [inlmath]43251[/inlmath] ali problem je za ovu drugu. Meni jedino što pada na pamet da odredim broj prvobitne permutacije pa da na osnovu susjednih brojeva odredim i susjedne permutacije. Jeste da je to malo duži postupak, vjerovatno postoji neki kraći način.

Gamma je napisao:Data je permutacija [inlmath]43215[/inlmath] elemenata [inlmath]1,2,3,4,5[/inlmath]. Napisati njene susjedne permutacije.

Prema postavci zadatka, potrebno je napisati sve susedne permutacije. Nema tu dužeg ili kraćeg postupka, potrebno je napisati ih sve.
Zatim, šta podrazumevaš pod "susednom permutacijom"? Da li je to zamena mesta dva susedna elementa u datoj permutaciji ili nešto drugo?
ovo pitam zbog:

Gamma je napisao:Meni jedino što pada na pamet da odredim broj prvobitne permutacije

meni uopšte nije jasno šta je to "broj prvobitne permutacije".

Koliko sam ja tebe skontao pod susjednim permutacijama se podrazumjevaju sve permutacije ispred i iza [inlmath]43215[/inlmath] (na nju mislim kao prvobitnu)

desideri je napisao:Zatim, šta podrazumevaš pod "susednom permutacijom"?

Ja koliko sam skontao to su dvije permutacije koje se nalaze ispred i iza [inlmath]43215[/inlmath] u ove slučaju mislim da su to [inlmath]43152[/inlmath] i [inlmath]43251[/inlmath].

desideri je napisao:meni uopšte nije jasno šta je to "broj prvobitne permutacije".

Redni broj koja je to permutacija po redu npr [inlmath]50[/inlmath] a ove dvije su [inlmath]49[/inlmath] i [inlmath]51[/inlmath].

rjesenje ti je tacno

[inlmath]43152\;43215\;43251[/inlmath]

Jeste ako se pod susjednom permuciom podrazumjeva ono što sam i ja mislio. Dok desideri izgleda ima drugačije mišljenje.

pa permutacije se redaju "leksikografski"

Nisam reko da mi to nije jasno. Znam da su permutacije leksikografski uređene. Tako smo i učili. Poenta ove priče je da se pod susjednim permutacijama podrazumjevaju dvije permutacije jedna ispred zadate i jedna iza.

Gamma je napisao:Poenta ove priče je da se pod susjednim permutacijama podrazumjevaju dvije permutacije jedna ispred zadate i jedna iza.

Ok, onda je to – to. Ja nisam bio siguran na šta se misli. Mnogo je više rezona da se upravo ovako definišu susedne permutacije nego kao što sam ja mislio, to jest da susedni elementi u prvobitnoj permutaciji zamene mesta. Ali hajde da postavim i pitanje.
Napisati dve susedne permutacije od: [inlmath]R5@Y$[/inlmath]
Hoću da kažem da bi trebalo definisati i šta znači taj leksikografski princip ređanja i kada se može primeniti, odnosno da se ne može reći uvek koje su to dve susedne permutacije. Trebalo bi (valjda) i zadati neku "leksikografsku hijerarhiju", ili barem napisati početnu permutaciju.

Primer sličan ovom koji si naveo bile bi raznobojne kuglice (bela, crna, crvena, plava, zelena, žuta, smeđa, ljubičasta itd.) za koje bi trebalo odrediti poredak njihovih permutacija. Naravno da to nije moguće učiniti ako se prethodno ne definiše poredak samih boja, budući da su po defaultu boje međusobno ravnopravne.
Međutim, kad imamo cifre, tu je stvar jasna – uvek ih ređamo od manjih ka većim ciframa (ako se drugačije ne naglasi), ili kad imamo slova – ređamo ih po abecednom/azbučnom redu (jedan takav primer smo imali u ovoj temi).

Što se tiče susednih permutacija permutacije [inlmath]43215[/inlmath] – potrebno je menjati cifre zdesna nalevo. Npr. pri određivanju naredne permutacije (kad treba dobiti prvi veći petocifreni broj), pošto znamo da krajnju desnu cifru ne možemo izmeniti a da sve ostale ostanu na svojim mestima, onda menjamo pretposlednju dok one levo od nje ne diramo. Pošto je pretposlednja [inlmath]1[/inlmath], a na raspolaganju imamo još [inlmath]5[/inlmath] (koja je na poslednjem mestu), umesto [inlmath]1[/inlmath] ćemo staviti [inlmath]5[/inlmath], a onda ta jedinica ide na kraj, čime smo dobili prvu narednu permutaciju, [inlmath]43251[/inlmath], koju si ispravno odredio.

Slično određujemo i prethodnu permutaciju. Ne možemo promeniti samo kranju desnu cifru, prema tome moramo menjati i pretposlednju, tj. staviti manju od one koja se trenutno tu nalazi. Pošto je na tom mestu trenutno [inlmath]1[/inlmath], a nemamo na raspolaganju manju cifru od nje, to znači da moramo menjati cifru pre nje (onu na trećem mestu), i to tako da stavimo prvu manju od postojeće koja nam je na raspolaganju. Pošto tu imamo cifru [inlmath]2[/inlmath], a prva manja je [inlmath]1[/inlmath], to znači da će prve tri cifre biti [inlmath]431[/inlmath]. Na preostala dva mesta moramo grupisati preostale cifre ([inlmath]2[/inlmath] i [inlmath]5[/inlmath]) tako da dobijemo najveći petocifreni broj (jer tražimo prvu prethodnu permutaciju od [inlmath]43215[/inlmath], a to ćemo postići tako što preostale cifre poređamo u opadajućem redosledu – znači, [inlmath]52[/inlmath]. Tražena (prethodna) permutacija, dakle, glasi [inlmath]43152[/inlmath].

Ništa dok @Daniel ne razjasni sve dileme .
Evo još malo na ovu temu, baš me je zainteresovala, a stvarno sam prvi put čuo za susedne permutacije (hvala @Gamma i @Sinisa).
Zar nije najjednostavnije ispisati redom permutacije samo tri poslednja elementa (ostali se ionako prepisuju) to jest:
[dispmath]125\quad152\quad215\quad251\quad512\quad521[/dispmath]
Evidentno je da ih je samo šest. Tu se odmah vide susedne permutacije, osim, naravno, ako je zadata permutacija sa [inlmath]125[/inlmath] ili [inlmath]521[/inlmath] (na poslednja tri mesta). Onda bih uključio u razmatranje i četvrti element.
S tim u vezi, da li je prvi desni sused od [inlmath]54321[/inlmath] zapravo [inlmath]12345[/inlmath]? Mislim, ako se ide ciklično. Pitam da bih ovo skroz razjasnio (sebi, a verujem i drugima).