Hogyan tudnám minél egyszerűbben és hatékonyabban leprogramozni az ismétléses permutációt?

Ha rákeresel, hogy multiset permutation, sok-sok pdf-et találsz a témában. Sok sikert a megértésükhöz, mert én nem értettem őket amikor előjött a téma.

A legEGYSZERŰBB megoldás, ha legenerálod az összes permutációt, és kiszűröd belőle az ismétlődéseket.

Ha C++-t használsz, akkor egyébként nagyon könnyű dolgod van, mert a next_permutation függvényt egy rendezett sorozatra hívogatva épp az ismétléses permutációt kapod.

Akkor az összes variáció kell vagy ismétléses permutáció?

Mind a kettőt rekurzívan meg lehet oldani. Az ismétléses permutációt különösen azzal ajánlom.

Az alapötlet a permutációnál, ahol csak különböző elemek vannak:

0 és 1 hosszú sorozatnak 1 féle permutációja van.

2 hosszú sorozatnak 2 féle. (ez evidens, még mind a 2 előállítása is)

3 hosszú sorozatnál úgy képezzük az összes permutációt hogy a legelső elemet levágva lefuttatjuk az összes permutációt (az utolsó 2 elemre), amikor megkaptuk a kimenetét sorról sorra akkor hozzáfűzzük a levágott tagot az első helyre, még 1x lefuttatjuk, de ekkor a 2. helyre rakjuk ezt a tagot végül a 3. helyre rakjuk, végül is egy for ciklus.

4 hosszú sorozatnál az első tagot levágjuk és lefuttatjuk 3 tagra az összes féleképp, a kapott kimenethez hozzáfűzzük a levágott tagot még egyszer lefuttatjuk és a második helyre fűzzük hozzá a kimethez stb stb for ciklussal végigmegyünk.

Vagyis N hosszú sorozatra ha N>2 visszavezetjük N-1 hosszú sorozatra és ezen hajtuk végre az összes permutációt, ezt is visszavezetjük ha a hossza több mint 2 egészen addig vezetjük vissza míg közvetlenül meg bírjuk oldani. Természetesen rekurzívan.

Az ismétléses permutációba meg az ismétlődő tagokat kell léptetni, pl X az ismétlődő tag _-al jelöltem azokat a tagokat melyek különböző tagok (képzelj oda bármilyen betűket melyek különbözőek)

XXXX___

XXX_X__

XXX__X_

XXX___X

XX_XX__

XX_X_X_

XX_X__X

... stb

Így léptetem, vagyis az utolsót léptetem a végéig utána az utolsó előttit egyel jobbra utána az utolsót.

Közbe meg közte lévő részt összefűzve meghívom az ismétlés nélküli permutációra, majd visszahelyettesítem. Ha nem csak az X fordul elő többször hanem pl az Y is akkor ugyanígy járunk el, az Y összes előfurdulását léptetgetük Y nélkül meghívjuk rá az ismétléses permutációt és annyiszor hívjuk meg innen ahány féleképpen Y előfordulhat.

Amúgy érteni kell nem megjegyezni. Amúgy meg vagy egyszerűbb vagy hatékonyabb én a hatékonyabb megoldást írtam le, hogy feleslegesen ne számoljon a gép akár tíz a sokadikonszor többet mint ahogy indokolt lenne.