Line data Source code
1 : /* Copyright (C) 2017 The PARI group.
2 :
3 : This file is part of the PARI/GP package.
4 :
5 : PARI/GP is free software; you can redistribute it and/or modify it under the
6 : terms of the GNU General Public License as published by the Free Software
7 : Foundation; either version 2 of the License, or (at your option) any later
8 : version. It is distributed in the hope that it will be useful, but WITHOUT
9 : ANY WARRANTY WHATSOEVER.
10 :
11 : Check the License for details. You should have received a copy of it, along
12 : with the package; see the file 'COPYING'. If not, write to the Free Software
13 : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
14 :
15 : #include "pari.h"
16 : #include "paripriv.h"
17 :
18 : void
19 546 : forksubset_init(forsubset_t *T, long n, long k)
20 : {
21 546 : T->all = 0;
22 546 : T->first = 1;
23 546 : if (n < 0) n = 0;
24 546 : T->n = n;
25 546 : if (k < 0) k = n+1; /* impossible value */
26 546 : T->k = k;
27 546 : T->v = identity_perm(k);
28 546 : }
29 :
30 : void
31 77 : forallsubset_init(forsubset_t *T, long n)
32 : {
33 77 : T->all = 1;
34 77 : T->first = 1;
35 77 : if (n < 0) n = 0;
36 77 : T->n = n;
37 77 : T->k = 0;
38 77 : T->v = vecsmalltrunc_init(n + 1);
39 77 : }
40 :
41 : static GEN
42 2611 : forksubset_next(forsubset_t *T)
43 : {
44 2611 : GEN v = T->v;
45 2611 : long i, n = T->n, k = T->k;
46 :
47 2611 : if (T->first) { T->first = 0; return (k >= 0 && k <= n) ? v: NULL; }
48 1988 : if (k <= 0 || k >= n) return NULL;
49 :
50 1778 : if (v[k] < n) { v[k]++; return v; }
51 1029 : for (i = k - 1; i >= 1 && v[i+1] == v[i] + 1; i--);
52 686 : if (i == 0) return NULL;
53 :
54 497 : v[i]++;
55 1134 : for (; i < k; i++) v[i+1] = v[i] + 1;
56 497 : return v;
57 : }
58 : static GEN
59 875 : forallsubset_next(forsubset_t *T)
60 : {
61 : long i;
62 :
63 875 : if (forksubset_next(T)) return T->v;
64 245 : else if (T->k < T->n)
65 : {
66 168 : (T->k)++;
67 168 : setlg(T->v, T->k+1);
68 588 : for (i = 1; i <= T->k; i++) (T->v)[i] = i;
69 168 : return T->v;
70 : }
71 77 : return NULL;
72 : }
73 : GEN
74 2611 : forsubset_next(forsubset_t *T)
75 2611 : { return T->all? forallsubset_next(T): forksubset_next(T); }
76 : void
77 630 : forsubset_init(forsubset_t *T, GEN nk)
78 : {
79 630 : switch(typ(nk))
80 : {
81 77 : case t_INT: forallsubset_init(T, itos(nk)); return;
82 546 : case t_VEC:
83 546 : if (lg(nk) == 3)
84 : {
85 546 : GEN n = gel(nk,1), k = gel(nk,2);
86 546 : if (typ(n) == t_INT && typ(k) == t_INT)
87 546 : return forksubset_init(T, itos(n),itos(k));
88 : }
89 : default:
90 7 : pari_err_TYPE("forsubset", nk);
91 : }
92 : }
93 : void
94 266 : forsubset0(GEN nk, GEN code)
95 : {
96 266 : pari_sp av = avma;
97 : forsubset_t T;
98 266 : void *E = (void*)code;
99 : GEN v;
100 266 : push_lex(gen_0, code);
101 266 : forsubset_init(&T, nk);
102 1505 : while ((v = forsubset_next(&T)))
103 1246 : if (gp_evalvoid(E, v)) break;
104 259 : pop_lex(1); set_avma(av);
105 259 : }
|
