include/flint/perm.h

0001 /*
0002     Copyright (C) 2011 Sebastian Pancratz
0003     Copyright (C) 2026 Ricardo Buring
0004     Copyright (C) 2026 Lars Göttgens
0005
0006     This file is part of FLINT.
0007
0008     FLINT is free software: you can redistribute it and/or modify it under
0009     the terms of the GNU Lesser General Public License (LGPL) as published
0010     by the Free Software Foundation; either version 3 of the License, or
0011     (at your option) any later version.  See <https://www.gnu.org/licenses/>.
0012 */
0013
0014 #ifndef PERM_H
0015 #define PERM_H
0016
0017 #ifdef PERM_INLINES_C
0018 #define PERM_INLINE
0019 #else
0020 #define PERM_INLINE static inline
0021 #endif
0022
0023
0024 #include "flint.h"
0025
0026 #ifdef __cplusplus
0027  extern "C" {
0028 #endif
0029
0030 /* Memory management *********************************************************/
0031
0032 PERM_INLINE slong * _perm_init(slong n)
0033 {
0034     slong i, *vec;
0035
0036     vec = (slong *) flint_malloc(n * sizeof(slong));
0037
0038     if (!vec)
0039     {
0040         flint_throw(FLINT_ERROR, "ERROR (_perm_init).\n\n");
0041     }
0042
0043     for (i = 0; i < n; i++)
0044         vec[i] = i;
0045
0046     return vec;
0047 }
0048
0049 PERM_INLINE void _perm_clear(slong * vec)
0050 {
0051     flint_free(vec);
0052 }
0053
0054 /* Assignment ****************************************************************/
0055
0056 PERM_INLINE slong _perm_equal(const slong *vec1, const slong *vec2, slong n)
0057 {
0058     slong i;
0059
0060     for (i = 0; i < n; i++)
0061         if (vec1[i] != vec2[i])
0062             return 0;
0063
0064     return 1;
0065 }
0066
0067 PERM_INLINE slong _perm_is_one(const slong *vec, slong n)
0068 {
0069     slong i;
0070
0071     for (i = 0; i < n; i++)
0072         if (vec[i] != i)
0073             return 0;
0074
0075     return 1;
0076 }
0077
0078 PERM_INLINE void _perm_set(slong *res, const slong *vec, slong n)
0079 {
0080     slong i;
0081
0082     for (i = 0; i < n; i++)
0083         res[i] = vec[i];
0084 }
0085
0086 PERM_INLINE void _perm_one(slong *vec, slong n)
0087 {
0088     slong i;
0089
0090     for (i = 0; i < n; i++)
0091         vec[i] = i;
0092 }
0093
0094 PERM_INLINE void
0095  _perm_inv(slong *res, const slong *vec, slong n)
0096 {
0097     slong i;
0098
0099     if (res == vec)
0100     {
0101         slong *t = (slong *) flint_malloc(n * sizeof(slong));
0102
0103         if (!t)
0104         {
0105             flint_throw(FLINT_ERROR, "ERROR (_perm_inv).\n\n");
0106         }
0107
0108         for (i = 0; i < n; i++)
0109             t[i] = vec[i];
0110         for (i = 0; i < n; i++)
0111             res[t[i]] = i;
0112
0113         flint_free(t);
0114     }
0115     else
0116     {
0117         for (i = 0; i < n; i++)
0118             res[vec[i]] = i;
0119     }
0120 }
0121
0122 /* Composition ***************************************************************/
0123
0124 // if p is encoded by vec1 and q is encoded by vec2, then p*q is encoded by res
0125 PERM_INLINE void
0126 _perm_compose(slong *res, const slong *vec1, const slong *vec2, slong n)
0127 {
0128     slong i;
0129
0130     if (res == vec1)
0131     {
0132         slong *t = (slong *) flint_malloc(n * sizeof(slong));
0133
0134         for (i = 0; i < n; i++)
0135             t[i] = vec1[i];
0136         for (i = 0; i < n; i++)
0137             res[i] = t[vec2[i]];
0138
0139         flint_free(t);
0140     }
0141     else
0142     {
0143         for (i = 0; i < n; i++)
0144             res[i] = vec1[vec2[i]];
0145     }
0146 }
0147
0148 // if a is encoded by vec1 and b is encoded by vec2, then (a^-1)*b is encoded by res
0149 PERM_INLINE void
0150 _perm_compose_inv1(slong *res, const slong *vec1, const slong *vec2, slong n)
0151 {
0152     slong i;
0153
0154     // FIXME: do this without allocating memory, if non-aliasing
0155     if (vec1 == vec2)
0156     {
0157         _perm_one(res, n);
0158     }
0159     if (res == vec2)
0160     {
0161         slong *t = (slong *) flint_malloc(n * sizeof(slong));
0162
0163         for (i = 0; i < n; i++)
0164             t[vec1[i]] = i;
0165         for (i = 0; i < n; i++)
0166             res[i] = t[vec2[i]];
0167
0168         flint_free(t);
0169     }
0170     else
0171     {
0172         _perm_inv(res, vec1, n);
0173         _perm_compose(res, res, vec2, n);
0174     }
0175 }
0176
0177 // if a is encoded by vec1 and b is encoded by vec2, then a*(b^-1) is encoded by res
0178 PERM_INLINE void
0179 _perm_compose_inv2(slong *res, const slong *vec1, const slong *vec2, slong n)
0180 {
0181     slong i;
0182
0183     if (vec1 == vec2)
0184     {
0185         _perm_one(res, n);
0186     }
0187     else if (res == vec1)
0188     {
0189         slong *t = (slong *) flint_malloc(n * sizeof(slong));
0190
0191         for (i = 0; i < n; i++)
0192             t[i] = vec1[i];
0193         for (i = 0; i < n; i++)
0194             res[vec2[i]] = t[i];
0195
0196         flint_free(t);
0197     }
0198     else if (res == vec2)
0199     {
0200         slong *t = (slong *) flint_malloc(n * sizeof(slong));
0201
0202         for (i = 0; i < n; i++)
0203             t[vec2[i]] = i;
0204         for (i = 0; i < n; i++)
0205             res[i] = vec1[t[i]];
0206
0207         flint_free(t);
0208     }
0209     else
0210     {
0211         for (i = 0; i < n; i++)
0212             res[vec2[i]] = vec1[i];
0213     }
0214 }
0215
0216 /* Randomisation *************************************************************/
0217
0218 int _perm_randtest(slong * vec, slong n, flint_rand_t state);
0219
0220 /* Parity ********************************************************************/
0221
0222 int _perm_parity(const slong * vec, slong n);
0223
0224 /* Iteration *****************************************************************/
0225
0226 PERM_INLINE int _perm_next_lex(slong *perm, slong n)
0227 {
0228     slong k = n-2;
0229     while (k >= 0 && perm[k] >= perm[k+1])
0230         k--;
0231     if (k < 0)
0232         return 0;
0233     slong l = n-1;
0234     while (l >= k && perm[k] >= perm[l])
0235         l--;
0236     FLINT_SWAP(slong, perm[k], perm[l]);
0237     slong i = k+1, j = n-1;
0238     while (i < j) {
0239         FLINT_SWAP(slong, perm[i], perm[j]);
0240         i++;
0241         j--;
0242     }
0243     return 1;
0244 }
0245
0246 PERM_INLINE int _perm_next_heap(slong *perm, slong n, slong *stack)
0247 {
0248     slong sp = 1;
0249     while (sp < n && stack[sp] >= sp)
0250         stack[sp++] = 0;
0251     if (sp == n) return 0;
0252     FLINT_SWAP(slong, perm[sp % 2 ? stack[sp] : 0], perm[sp]);
0253     stack[sp]++;
0254     return 1;
0255 }
0256
0257 #define _long_vec_print _Pragma("GCC error \"'_long_vec_print(vec, len)' is deprecated. Use 'flint_printf(\"%{slong*}\", vec, len)' instead.\"")
0258 #define _perm_print _Pragma("GCC error \"'_perm_print(vec, len)' is deprecated. Use 'flint_printf(\"%{slong*}\", vec, len)' instead.\"")
0259 #define _perm_set_one _Pragma("GCC error \"'_perm_set_one' is deprecated. Use '_perm_one' instead.\"")
0260
0261 #ifdef __cplusplus
0262 }
0263 #endif
0264
0265 #endif