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

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic.

mail