Plans regarding enumerating subsets (all, or only specific ones)
More...
Go to the source code of this file.
Detailed Description
Plans regarding enumerating subsets (all, or only specific ones)
 Todo:
 Connections
 Todo:
 Iteration through lexicographical order

Statefree iteration for lexicographical order is given as follows:
first_lex_ksubsets(n,k) := setn(k)$
next_lex_ksubsets(S,n) := block(
[L : listify(S), l : length(S), i, prev : n+1],
i : l1,
for x in reverse(L) do
if x+1 < prev then
return(if i = 1 then done else
setify(append(take_elements(i,L), create_list(x+k,k,1,li))))
else (i : i1, prev : x))$
This algorithm is essentially the same as algorithm L in [Knuth, Vol. 4, Fascicle 3, Section 7.2.1.3].

Compare function Combinatorics::choose_next in General/Combinatorics.hpp.

Usage example:
block([x : first_lex_ksubsets(6,3)],
while x#done do (print(x), x : next_lex_ksubsets(x,6)));

Colexicographical order: XXX

(General) Iteration for lexicographical order XXX

The following needs updating according to ComputerAlgebra/Combinatorics/Lisp/Enumeration/plans/general.hpp.

"itgen_lex_ksubsets(M,k) yields an iterator "it" "pointing" to the first element.

"iteval_lex_ksubsets(it)" yields the element.

"itend_lex_ksubsets(it) = it[1]" returns true iff it points "past the
end".

"itadv_lex_ksubsets(it)" advances a valid iterator (pointing to an element) one step, based on a shallow copy of it.

Algorithm T in [Knuth, Vol. 4, Fascicle 3, Section 7.2.1.3] should yield an appropriate algorithm.

An application example:
block([it : itgen_lex_ksubsets(M,k)], while not itend_lex_ksubsets(it) do
print(iteval_lex_ksubsets(it)), itadv_lex_ksubsets(it));
 Todo:
 Improving colexicographical unranking

unrank_colex_ksubsets(x,n,k) does not really depend on n, it is only a large enough start value needed for L.

It would be better if from x and k we could compute a good value n (and thus it wouldn't be needed as input).

The smallest n is given by the condition x <= binomial(n,k).
 Todo:
 Enumerating all ksubsets in Graycode manner

The point here is that only one element is changed at a time (when proceeding to the successor).

There should be a standard, recursive way of achieving such an order.
Definition in file Subsets.hpp.