1 /*
2     Copyright (C) 2011 Fredrik Johansson
3 
4     This file is part of FLINT.
5 
6     FLINT is free software: you can redistribute it and/or modify it under
7     the terms of the GNU Lesser General Public License (LGPL) as published
8     by the Free Software Foundation; either version 2.1 of the License, or
9     (at your option) any later version.  See <http://www.gnu.org/licenses/>.
10 */
11 
12 #include "perm.h"
13 
14 int
_perm_parity(const slong * vec,slong n)15 _perm_parity(const slong *vec, slong n)
16 {
17     slong i, k;
18     int * encountered;
19     int parity;
20     TMP_INIT;
21 
22     if (n <= 1)
23         return 0;
24 
25     TMP_START;
26 
27     parity = 0;
28     encountered = (int *) TMP_ALLOC(n*sizeof(int));
29 
30     for (i = 0; i < n; i++)
31        encountered[i] = 0;
32 
33     for (i = 0; i < n; i++)
34     {
35         if (encountered[i] != 0)
36         {
37             parity ^= 1;
38         }
39         else
40         {
41             k = i;
42             do
43             {
44                 k = vec[k];
45                 encountered[k] = 1;
46             }
47             while (k != i);
48         }
49     }
50 
51     TMP_END;
52 
53     return parity;
54 }
55