1 /* permutation/permutation.c
3 * Copyright (C) 1996, 1997, 1998, 1999, 2000, 2007 Brian Gough
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 3 of the License, or (at
8 * your option) any later version.
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * General Public License for more details.
15 * You should have received a copy of the GNU General Public License
16 * along with this program; if not, write to the Free Software
17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
21 #include <gsl/gsl_errno.h>
22 #include <gsl/gsl_permutation.h>
25 gsl_permutation_size (const gsl_permutation * p)
31 gsl_permutation_data (const gsl_permutation * p)
36 #ifndef HIDE_INLINE_STATIC
38 gsl_permutation_get (const gsl_permutation * p, const size_t i)
42 if (i >= p->size) /* size_t is unsigned, can't be negative */
44 GSL_ERROR_VAL ("index out of range", GSL_EINVAL, 0);
53 gsl_permutation_swap (gsl_permutation * p, const size_t i, const size_t j)
55 const size_t size = p->size ;
59 GSL_ERROR("first index is out of range", GSL_EINVAL);
64 GSL_ERROR("second index is out of range", GSL_EINVAL);
69 size_t tmp = p->data[i];
70 p->data[i] = p->data[j];
79 gsl_permutation_valid (const gsl_permutation * p)
81 const size_t size = p->size ;
85 for (i = 0; i < size; i++)
87 if (p->data[i] >= size)
89 GSL_ERROR("permutation index outside range", GSL_FAILURE) ;
92 for (j = 0; j < i; j++)
94 if (p->data[i] == p->data[j])
96 GSL_ERROR("duplicate permutation index", GSL_FAILURE) ;
105 gsl_permutation_reverse (gsl_permutation * p)
107 const size_t size = p->size ;
111 for (i = 0; i < (size / 2); i++)
113 size_t j = size - i - 1;
115 size_t tmp = p->data[i] ;
116 p->data[i] = p->data[j] ;
122 gsl_permutation_inverse (gsl_permutation * inv, const gsl_permutation * p)
124 const size_t size = p->size ;
128 if (inv->size != size)
130 GSL_ERROR("permutation lengths are not equal", GSL_EBADLEN);
133 for (i = 0; i < size; i++)
135 inv->data[p->data[i]] = i ;
142 gsl_permutation_next (gsl_permutation * p)
144 /* Replaces p with the next permutation (in the standard lexicographical
145 * ordering). Returns GSL_FAILURE if there is no next permutation.
147 const size_t size = p->size;
157 while ((p->data[i] > p->data[i+1]) && (i != 0))
162 if ((i == 0) && (p->data[0] > p->data[1]))
169 for (j = i + 2; j < size; j++ )
171 if ((p->data[j] > p->data[i]) && (p->data[j] < p->data[k]))
180 size_t tmp = p->data[i];
181 p->data[i] = p->data[k];
185 for (j = i + 1; j <= ((size + i) / 2); j++)
187 size_t tmp = p->data[j];
188 p->data[j] = p->data[size + i - j];
189 p->data[size + i - j] = tmp;
196 gsl_permutation_prev (gsl_permutation * p)
198 const size_t size = p->size;
208 while ((p->data[i] < p->data[i+1]) && (i != 0))
213 if ((i == 0) && (p->data[0] < p->data[1]))
220 for (j = i + 2; j < size; j++ )
222 if ((p->data[j] < p->data[i]) && (p->data[j] > p->data[k]))
231 size_t tmp = p->data[i];
232 p->data[i] = p->data[k];
236 for (j = i + 1; j <= ((size + i) / 2); j++)
238 size_t tmp = p->data[j];
239 p->data[j] = p->data[size + i - j];
240 p->data[size + i - j] = tmp;
247 gsl_permutation_mul (gsl_permutation * p, const gsl_permutation * pa, const gsl_permutation * pb)
250 const size_t size = p->size;
252 if (pa->size != size)
254 GSL_ERROR("size of result does not match size of pa", GSL_EINVAL);
257 if (pb->size != size)
259 GSL_ERROR("size of result does not match size of pb", GSL_EINVAL);
262 for (i = 0; i < size; i++)
264 p->data[i] = pb->data[pa->data[i]];
270 gsl_permutation_memcpy (gsl_permutation * dest,
271 const gsl_permutation * src)
273 const size_t src_size = src->size;
274 const size_t dest_size = dest->size;
276 if (src_size != dest_size)
278 GSL_ERROR ("permutation lengths are not equal", GSL_EBADLEN);
284 for (j = 0; j < src_size; j++)
286 dest->data[j] = src->data[j];