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

Permutáció

avagy az elemek lehetséges sorrendje

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ó): 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!


2019-07-18 23:20:06 Admin Köszönöm, ha Ön lesz az első, aki megírja ide véleményét, észrevételét, kérdését ezzel a lappal kapcsolatban.




Ú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 + négy?
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