Generation of all subsets with K elements

PROBLEM
Generation of all subsets with K elements from a set {1,...,N} in lexicographic order. The number of this subsets, i.e. the number of combinations is NCOMB(N,K)

IMPLEMENTATION
Unit: internal subroutine

Parameters: nonnegative integers N,K; 0<=K<=N

Result: Subroutine displays on the screen sequences of indexes all subsets with K elements in lexicographical order

 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

EXAMPLE OF USE

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

displays on the screen:

 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

CONNECTIONS

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

 cover contents index main page