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 : /* for loop over permutations in lexicographic order
16 : * This implements the algorithm L in D. Knuth "The Art Of Computer Programming"
17 : * Fascicle 2b */
18 :
19 : #include "pari.h"
20 : #include "paripriv.h"
21 :
22 : void
23 119 : forperm_init(forperm_t *T, GEN k)
24 : {
25 119 : switch (typ(k))
26 : {
27 70 : case t_INT:
28 70 : if (signe(k) < 0) pari_err_DOMAIN("forperm", "a", "<", gen_0, k);
29 63 : T->v = identity_perm(itou(k)); break;
30 28 : case t_VEC:
31 28 : T->v = vec_to_vecsmall(k); break;
32 14 : case t_VECSMALL:
33 14 : T->v = vecsmall_copy(k); break;
34 7 : default:
35 7 : pari_err_TYPE("forperm", k);
36 : return; /* LCOV_EXCL_LINE */
37 : }
38 105 : T->first = 1;
39 105 : T->k = lg(T->v) - 1;
40 : }
41 :
42 : GEN
43 2436 : forperm_next(forperm_t *T)
44 : {
45 2436 : long k = T->k, m1, m2, *p, *q;
46 2436 : GEN v = T->v;
47 :
48 2436 : if (T->first) { T->first = 0; return v; }
49 4312 : m1 = k-1; while (m1 > 0 && v[m1] >= v[m1+1]) m1--;
50 2331 : if (m1 <= 0) return NULL;
51 :
52 3339 : m2 = k; while (v[m1] >= v[m2]) m2--;
53 2226 : lswap(v[m1], v[m2]);
54 2226 : p = v + m1 + 1;
55 2226 : q = v + k;
56 3535 : while (p < q) { lswap(*p, *q); p++; q--; }
57 2226 : return v;
58 : }
59 :
60 : void
61 119 : forperm(void *E, long call(void *, GEN), GEN k)
62 : {
63 119 : pari_sp av = avma;
64 : forperm_t T;
65 : GEN v;
66 :
67 119 : forperm_init(&T, k);
68 2436 : while ((v = forperm_next(&T)))
69 2331 : if (call(E, v)) break;
70 105 : set_avma(av);
71 105 : }
72 :
73 : void
74 119 : forperm0(GEN k, GEN code)
75 : {
76 119 : push_lex(gen_0, code);
77 119 : forperm((void *)code, &gp_evalvoid, k);
78 105 : pop_lex(1);
79 105 : }
80 :
|
