DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0//EN"> Generovani vsech K-prvkovych podmnozin

 

GENEROVÁNÍ VŠECH K-PRVKOVÝCH PODMNOŽIN

PROBLÉM
Vygenerovat všechny K-prvkové podmnožiny množiny {1,...,N} v lexikografickém uspořádání. Počet těchto podmnožin je roven číslu NCOMB(N,K)

IMPLEMENTACE
Jednotka: vnitřní podprogram
 
Parametry: nezáporná celá čísla N,K; 0<=K<=N
 
Výsledek: Podprogram vypíše na obrazovku posloupnost indexů všech K-prvkových podmnožin v lexikografickém uspořádání
 

GENSUB: procedure
parse arg N, K
do J = 1 to K; A.J = J; end
P = 1
do while P >= 1
  SubSet = A.K
  do J = K - 1 to 1 by -1
    SubSet = A.J SubSet
  end
  say SubSet
  if A.K = N then P = P - 1; else P = K
  if P >= 1 then
      do J = K to P by -1
        A.J = A.P + J - P + 1
      end
end
return

 

PŘÍKLAD

N = 6; K = 5; call GENSUB N, K
exit
GENSUB: procedure
...

zobrazí:

1 2 3 4 5
1 2 3 4 6
1 2 3 5 6
1 2 4 5 6
1 3 4 5 6
2 3 4 5 6

 

SOUVISLOSTI

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


Obálka Obsah Index Hlavní stránka

změněno 6. srpna 2001
Copyright © 2000-2001 Vladimír Zábrodský, RNDr.