Eszköztár

89 Kezdőlap - Webszerkesztés - JavaScript - Permutáció

Feladat

Korábban, a Faktoriális című feladatban már megállapítottuk, hogy egy betűsorozat betűit hány különféle sorrendben lehet felírni. E gondolatot tovább szőve az Ön feladata most az, hogy készítsen programot, mely meg is jeleníti a lehetséges felírásokat.

Segítség

Elemek sorozatának lehetséges permutációit több különböző algoritmussal is elkészíthetjük. Ezek közül nem feltétlenül a leggyorsabb működésű, de minden bizonnyal a legrövidebb forráskódot jelentő megvalósítás a rekurzió alkalmazása. Ennek az elvét mutatja az alábbi mondatszerű leírás.

	Eljárás RekurzívPermutáció( i )
	    Ha i>N akkor Kiírás(...)
	    különben
	        Ciklus k := i-től N-ig
	            Csere(i,k)
	            RekurzívPermutáció( i+1 )
	            Csere(i,k)
	        Ciklus vége
	Eljárás vége

Az algoritmus egy tetszőleges nevű globális tömb elemeivel dolgozik. A tömb elemei 1-től N-ig sorszámozottak. A rekurziót ennek megfelelően i=1-től kell indítani. Ennek hatására a ciklus minden lépésben az i és k sorszámú elemeket cserélgeti (ahol k a ciklusváltozó):

• kicseréli e két elemet,
• az új sorrendű tömbelemekkel és 1-gyel növelt  i  értékkel meghívja önmagát,
• majd visszatérés után visszacseréli az elemeket.

Mindehhez nyilván a Csere( ) nevű műveletet meg kell valósítani.
Az algoritmus lefutása után tehát a tömbben az elemek az eredeti sorrendben lesznek benne, közben azonban minden lehetséges sorrend előfordul, és kiírásra kerül.

Fontos!
Az eljárás k ciklusváltozója lokális változó: minden eljáráshívás során új k változónak kell "születnie". Ez úgy oldható meg javascriptben, hogy a cikluson belül használni kell a var kulcsszót a változó deklarálásához:

		for( var k=i; k<=N; k++ )
		{
		    ...
		}

Ennek hiányában egy korábbi eljárás (globálisnak tekintett) változójának értékét írnánk felül az újonnan hívott eljárásban - ami nyilván nem helyes.

Figyelmeztetés!
Mivel egy pl. 8 elemből álló tömb lehetséges permutációinak száma is már

8! = 40320

ezért ennél akár csupán néhány elemmel nagyobb számosságú tömbbel tesztelni a programot azt ered­mé­nyez­heti, hogy jelentősen megnövekedhet a program futási ideje!

---

Új hozzászólás:
E-mail cím:	Erre a címre küldjük ki a hozzászólás jóvá- hagyásához szükséges linket. Az e-mail címet sehol nem tesszük közzé.
Név:	Ez a név fog megjelenni az Ön hozzászólásai mellett.
Mennyi tizenegy + nyolc? Számjegyekkel írja be!	Ez a robotok beírása elleni védelem miatt szükséges ellenőrzés.

© infojegyzet.hu, 2018. március