Subsets.hpp File Reference

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)

Iteration through lexicographical order
  • State-free 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 : l-1,
      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,l-i))))
        else (i : i-1, prev : x))$
    This algorithm is essentially the same as algorithm L in [Knuth, Vol. 4, Fascicle 3, Section].
  • 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
    1. The following needs updating according to ComputerAlgebra/Combinatorics/Lisp/Enumeration/plans/general.hpp.
    2. "itgen_lex_ksubsets(M,k) yields an iterator "it" "pointing" to the first element.
    3. "iteval_lex_ksubsets(it)" yields the element.
    4. "itend_lex_ksubsets(it) = it[1]" returns true iff it points "past the end".
    5. "itadv_lex_ksubsets(it)" advances a valid iterator (pointing to an element) one step, based on a shallow copy of it.
    6. Algorithm T in [Knuth, Vol. 4, Fascicle 3, Section] should yield an appropriate algorithm.
    7. 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));
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).
Enumerating all k-subsets in Gray-code 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.