OKlibrary  0.2.1.6
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)

Todo:
Connections
Todo:
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 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
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 7.2.1.3] should yield an appropriate algorithm.
7. An application example:
```block([it : itgen_lex_ksubsets(M,k)], while not itend_lex_ksubsets(it) do