Permutációk szorzása, inverz permutáció, permutációs csoport
[szerkesztés] Fordított permutáció
Tegyük fel, hogy a permutáció a p [i] tömbben van, majd az op [i] tömbben, miután az algoritmus végrehajtásra került, fordított permutációt tartalmaz.
Amikor egy permutációt reprezentálunk ciklusok formájában, az inverz permutáció könnyen előállítható a ciklusok összes széleinek invertálásával.
Így egy hatékonyabb algoritmus követi (a helybeli változat megadva):
Permutation csoport
A csoport olyan készlet, amelyen bináris művelet van, amely megfelel a következő tulajdonságoknak:- A megfelelő bináris művelet társíthatósága.
- Egy semleges elem létezése egy olyan művelet tekintetében, amely bármelyik számára
- Bármelyik számára létezik olyan inverz elem, amellyel