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
|
