1Function: _forsubset_init
2Class: gp2c_internal
3Help: Initialize forsubset_t
4Description:
5 (forsubset,small):void            forallsubset_init(&$1, $2)
6 (forsubset,gen):void              forsubset_init(&$1, $2)
7
8Function: _forsubset_next
9Class: gp2c_internal
10Help: Compute the next subset
11Description:
12 (forsubset):vecsmall              forsubset_next(&$1)
13
14Function: forsubset
15Section: programming/control
16C-Name: forsubset0
17Prototype: vGVI
18Iterator:
19 (gen,gen)         (forsubset, _forsubset_init, _forsubset_next)
20Wrapper: (,vG,,)
21Help: forsubset(nk, s, seq): if nk is an integer n, the sequence is evaluated,
22  s going through all subsets of {1, 2, ..., n}; if nk is a pair [n,k]
23  of integers s goes through k-subsets of {1, 2, ..., n}.
24  The order is lexicographic among subsets of the same size and smaller
25  subsets come first.
26Doc: if \var{nk} is a nonnegative integer $n$, evaluates \kbd{seq}, where
27 the formal variable $s$ goes through all subsets of $\{1, 2, \ldots, n\}$;
28 if \var{nk} is a pair $[n,k]$ of integers, $s$ goes through subsets
29 of size $k$ of $\{1, 2, \ldots, n\}$. In both cases $s$ goes through subsets
30 in lexicographic order among subsets of the same size and smaller subsets
31 come first.
32 \bprog
33 ? forsubset([5,3], s, print(s))
34 Vecsmall([1, 2, 3])
35 Vecsmall([1, 2, 4])
36 Vecsmall([1, 2, 5])
37 Vecsmall([1, 3, 4])
38 Vecsmall([1, 3, 5])
39 Vecsmall([1, 4, 5])
40 Vecsmall([2, 3, 4])
41 Vecsmall([2, 3, 5])
42 Vecsmall([2, 4, 5])
43 Vecsmall([3, 4, 5])
44 @eprog
45
46 \bprog
47 ? forsubset(3, s, print(s))
48 Vecsmall([])
49 Vecsmall([1])
50 Vecsmall([2])
51 Vecsmall([3])
52 Vecsmall([1, 2])
53 Vecsmall([1, 3])
54 Vecsmall([2, 3])
55 Vecsmall([1, 2, 3])
56 @eprog\noindent The running time is proportional to the number
57 of subsets enumerated, respectively $2^n$ and \kbd{binomial}$(n,k)$:
58 \bprog
59 ? c = 0; forsubset([40,35],s,c++); c
60 time = 128 ms.
61 %4 = 658008
62 ? binomial(40,35)
63 %5 = 658008
64 @eprog
65