Note de curs, probleme algoritmică, 21 octombrie 2013

În acest curs am discutat despre problema 1024 - Permutations.

Cerința

Dându-se o permutare, să se calculeze ordinul acesteia (notat k), definit astfel: k minim, astfel încât P^k = permutarea identitate.

Soluția

(1) Se determină toate ciclurile elementare ale permutării date.

(2) Notând cu l₁, l₂, ..., l_n lungimile tuturor ciclurilor elementare se calculează k = CMMMC(l₁, l₂, ..., l_n).

Explicația intuitivă a soluției

Dacă permutarea dată se reduce la un singur ciclu elementar, atunci k = lungimea permutării.

P^0 = (1 2 3 4)
P^1 = (4 3 1 2)
P^2 = (2 1 4 3)
P^3 = (3 4 2 1)
P^4 = (1 2 3 4)

Dacă permutarea dată se reduce la mai multe cicluri elementare (cu lungimile l₁, l₂, ..., l_n), atunci fiecare din acestea coincid cu permutarea identică după aplicarea permutării de un multiplu de l₁ ori, de l₂ ori, ... respectiv de l_n ori.

Astfel, calculând cel mai mic multiplu comun al tuturor lungimilor, obținem k.