Stran 1 od 1

Permutacije

Objavljeno: So Jun 03, 2017 11:30 am
Napisal/-a lukazlatecan
Mislimo si neko permutacijo na množici n elementov. Če s to permutacijo po večkrat zaporedoma premešamo naše elemente, bo prej ali slej prišel vsak element nazaj na svoje prvotno mesto. Najmanjšemu številu izvedb permutacije, po katerem pride vsak element nazaj na prvotno mesto, pravimo red te permutacije.

Primer: Oglejmo si permutacijo [math]. Z eno uporabo te permutacije torej iz prvotnega vrstnega reda (1,2,3,4,5,6) nastane (3,6,4,1,5,2); iz slednjega nato, če našo permutacijo uporabimo še drugič, nastane (4,2,1,3,5,6); iz tega po tretji uporabi naše permutacije nastane (1,6,3,4,5,2), nato po četrti uporabi nastane (3,2,4,1,5,6), po peti (4,6,1,3,5,2) in po šesti (1,2,3,4,5,6). Permutacijo smo torej morali izvesti šestkrat, da smo prišli nazaj na začetni razpored, zato je red te permutacije enak 6.

Naloga
Znano je, da obstaja n! različnih permutacij n elementov. Napišite program, ki prebere n in izračuna povprečje redov vseh teh n! permutacij.

Vhodni podatki
V prvi vrstici je celo število n; zanj velja 1≤n≤50.

Izhodni podatki
Izpišite eno samo število – povprečje redov vseh permutacij n elementov, zaokroženo navzdol na celo število.

Nasvet: Če vaš programski jezik ne podpira dela z velikimi celimi števili, je za to nalogo dovolj dober tudi tip double. Za 1<n≤50 je povprečje vedno za več kot 0,005 oddaljeno od najbližjega celega števila, torej je malo verjetno, da bi zaradi zaokrožitvenih napak pri delu s plavajočo vejico na koncu, po zaokrožitvi povprečja na celo število, dobili napačen rezultat.

Primer vhoda

Koda: Izberi vse

2


Pripadajoč izhod

Koda: Izberi vse

1


Komentar
Pri n=2 imamo dve permutaciji: [math], ki ima red 1, in [math], ki ima red 2. Povprečje njunih redov je torej 1,5; ko to zaokrožimo navzdol na celo število, dobimo rezultat 1.

Re: Permutacije

Objavljeno: So Jun 03, 2017 4:02 pm
Napisal/-a Ptolomej
Vsako permutacijo lahko zapišemo kot produkt ciklov. Kaj to pomeni?
Razložimo to kar na našem primeru [math].

Vidimo, da pri tej permutaciji gre 1 v 3, 3 gre v 4 in 4 gre v 1, kar običajno zapišemo [math] in to imenujemo 3-cikel.
Podobno gre 2 v 6 in 6 v 2 in imamo 2-cikel [math]. Samo 5 gre v vase in to lahko zapišemo [math].

Potem lahko zapišemo našo permutacijo takole:
\[\binom{1\ 2\ 3\ 4\ 5\
6}{3\ 6\ 4\ 1\ 5\ 2} = (1,3,4)\circ (2,6)\circ (5)\]

Običajno števila (elemente), ki gredo vase sploh ne zapišemo, saj je jasno, da se nezapisana števila preslikajo vase, torej bi mi imeli:
\[\binom{1\ 2\ 3\ 4\ 5\
6}{3\ 6\ 4\ 1\ 5\ 2} = (1,3,4)\circ (2,6)\]

Poglejmo še en primer.
\[\binom{1\ 2\ 3\ 4\ 5\
6\ 7\ 8}{7\ 6\ 3\ 1\ 2\ 5\ 4\ 8} = (1,7,4)\circ (2,6,5)\]

Obratno, iz produkta ciklov lahko nazaj zapišemo celotno permutacijo. Recimo, da permutiramo števila od 1 do 9. Potem je
\[(1,3,5,8)\circ (2,9) = \binom{1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9}{3\ 9\ 5\ 4\
8\ 6\ 7\ 1\ 2}\]

Red vsakega cikla je natanko njegova dolžina. Ni težko videti, da je red vsake permutacije enak najmanjšemu skupnemu večkratniku ciklov. No, morda bo ta ideja o ciklih pomagal pri razreševanju naloge. :)

Re: Permutacije

Objavljeno: So Jun 03, 2017 7:07 pm
Napisal/-a lukazlatecan
Če pogledamo na primer razcep naše permutacije na cikle: (1,3,4)(2,6)(5)
Imamo tri cikle katerih dolžine so 3,2,1. Najmanjši skupni večkratnik je torej: v(3,2,1)=6. Se pravi lahko rečemo da ima taka permutacija red 6.
Ugotoviti moramo še torej koliko je takih permutacij, ki so sestavljene iz 3-cikla, 2-cikla in 1-cikla, kar ne bi smelo biti pretežko ...
Pogledali smo si primer, za permutacijo sestavljeno iz 3-cikla, 2-cikla in 1-cikla. Koliko pa je različnih oblik permutacij? Pomagamo si lahko z razčlenitvijo naravnega števila na pozitivne naravne sumande, pri čemer sumandi predstavljajo dolžine ciklov.
Za namig/pomoč prilagam naslednji program, ki razčleni število n na sumande.

Koda: Izberi vse

public class Sumandi {
    public static void main(String[] args) {
        int n = 5;
        razcepiNaSumande(n, n, "");
    }

    public static void razcepiNaSumande(int n, int m, String sestevek){
        if(n == 0){
            System.out.println(sestevek);
            return;
        }
        for(int i = Math.min(n,m); i>=1; i--){
            razcepiNaSumande(n-i, i, sestevek + " " + i);
        }
    }
}