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