GENEROVÁNÍ VŠECH PERMUTACÍ

PROBLÉM
Nechť N je přirozené číslo takové, že N>=2. Vygenerujte všech FACT(N) permutací množiny {1,...,N}.

Pozn.:
FACT označuje faktoriál

IMPLEMENTACE
Jednotka: vnitřní podprogram
 
Parametr: přirozené číslo N>=2
 
Výsledek: podprogram zobrazí všechny permutace
 

PERMUTATION: procedure
parse arg N
C. = 1; Pr. = 1
do J = 1 to N; P.J = J; end
C.N = 0
say DISPLAY(N)
J = 1
do while J < N
  X = 0
  do J = 1 while C.J = N - J + 1
    Pr.J = \Pr.J; C.J = 1
    if Pr.J then X = X + 1
  end
  if J < N
    then do
      if Pr.J then K = C.J + X
              else K = N - J + 1 - C.J + X
      Kp1 = K + 1; W = P.K
      P.K = P.Kp1; P.Kp1 = W
      say DISPLAY(N)
      C.J = C.J + 1
    end
end
return
 
DISPLAY: procedure expose P.
parse arg N
Permutation = P.N
do J = N - 1 to 1 by -1
  Permutation = P.J Permutation
end
return Permutation
 

 

PŘÍKLAD

 

N = 3; call PERMUTATION N
exit
PERMUTATION: procedure
...

 

vypíše na obrazovku:

 

1 2 3
2 1 3
2 3 1
3 2 1
3 1 2
1 3 2

 

Další příklad
Viz Technika: Testovací data

SOUVISLOSTI
Faktoriál
Počet kombinací
Náhodná permutace
Generování všech K-prvkových podmnožin

Literatura
Lipski W. Kombinatoryka dla Programistow
Wydawnictwa Naukowo-techniczne, Warszawa, 1982


Obálka Obsah Index Hlavní stránka

změněno 30. července 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.