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

Faktoriál
Počet kombinací
Generování všech permutací

Literatura

Lipski W. Kombinatoryka dla Programistow

Wydawnictwa Naukowo-techniczne, Warszawa, 1982

---