1 /* permutation/permutation.c
2 *
3 * Copyright (C) 1996, 1997, 1998, 1999, 2000, 2007 Brian Gough
4 *
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.
9 *
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.
14 *
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.
18 */
19
20 #include <config.h>
21 #include <gsl/gsl_errno.h>
22 #include <gsl/gsl_permutation.h>
23
24 size_t
gsl_permutation_size(const gsl_permutation * p)25 gsl_permutation_size (const gsl_permutation * p)
26 {
27 return p->size ;
28 }
29
30 size_t *
gsl_permutation_data(const gsl_permutation * p)31 gsl_permutation_data (const gsl_permutation * p)
32 {
33 return p->data ;
34 }
35
36 int
gsl_permutation_swap(gsl_permutation * p,const size_t i,const size_t j)37 gsl_permutation_swap (gsl_permutation * p, const size_t i, const size_t j)
38 {
39 const size_t size = p->size ;
40
41 if (i >= size)
42 {
43 GSL_ERROR("first index is out of range", GSL_EINVAL);
44 }
45
46 if (j >= size)
47 {
48 GSL_ERROR("second index is out of range", GSL_EINVAL);
49 }
50
51 if (i != j)
52 {
53 size_t tmp = p->data[i];
54 p->data[i] = p->data[j];
55 p->data[j] = tmp;
56 }
57
58 return GSL_SUCCESS;
59 }
60
61
62 int
gsl_permutation_valid(const gsl_permutation * p)63 gsl_permutation_valid (const gsl_permutation * p)
64 {
65 const size_t size = p->size ;
66
67 size_t i, j ;
68
69 for (i = 0; i < size; i++)
70 {
71 if (p->data[i] >= size)
72 {
73 GSL_ERROR("permutation index outside range", GSL_FAILURE) ;
74 }
75
76 for (j = 0; j < i; j++)
77 {
78 if (p->data[i] == p->data[j])
79 {
80 GSL_ERROR("duplicate permutation index", GSL_FAILURE) ;
81 }
82 }
83 }
84
85 return GSL_SUCCESS;
86 }
87
88 void
gsl_permutation_reverse(gsl_permutation * p)89 gsl_permutation_reverse (gsl_permutation * p)
90 {
91 const size_t size = p->size ;
92
93 size_t i ;
94
95 for (i = 0; i < (size / 2); i++)
96 {
97 size_t j = size - i - 1;
98
99 size_t tmp = p->data[i] ;
100 p->data[i] = p->data[j] ;
101 p->data[j] = tmp ;
102 }
103 }
104
105 int
gsl_permutation_inverse(gsl_permutation * inv,const gsl_permutation * p)106 gsl_permutation_inverse (gsl_permutation * inv, const gsl_permutation * p)
107 {
108 const size_t size = p->size ;
109
110 size_t i ;
111
112 if (inv->size != size)
113 {
114 GSL_ERROR("permutation lengths are not equal", GSL_EBADLEN);
115 }
116
117 for (i = 0; i < size; i++)
118 {
119 inv->data[p->data[i]] = i ;
120 }
121
122 return GSL_SUCCESS ;
123 }
124
125 int
gsl_permutation_next(gsl_permutation * p)126 gsl_permutation_next (gsl_permutation * p)
127 {
128 /* Replaces p with the next permutation (in the standard lexicographical
129 * ordering). Returns GSL_FAILURE if there is no next permutation.
130 */
131 const size_t size = p->size;
132 size_t i, j, k;
133
134 if (size < 2)
135 {
136 return GSL_FAILURE;
137 }
138
139 i = size - 2;
140
141 while ((p->data[i] > p->data[i+1]) && (i != 0))
142 {
143 i--;
144 }
145
146 if ((i == 0) && (p->data[0] > p->data[1]))
147 {
148 return GSL_FAILURE;
149 }
150
151 k = i + 1;
152
153 for (j = i + 2; j < size; j++ )
154 {
155 if ((p->data[j] > p->data[i]) && (p->data[j] < p->data[k]))
156 {
157 k = j;
158 }
159 }
160
161 /* swap i and k */
162
163 {
164 size_t tmp = p->data[i];
165 p->data[i] = p->data[k];
166 p->data[k] = tmp;
167 }
168
169 for (j = i + 1; j <= ((size + i) / 2); j++)
170 {
171 size_t tmp = p->data[j];
172 p->data[j] = p->data[size + i - j];
173 p->data[size + i - j] = tmp;
174 }
175
176 return GSL_SUCCESS;
177 }
178
179 int
gsl_permutation_prev(gsl_permutation * p)180 gsl_permutation_prev (gsl_permutation * p)
181 {
182 const size_t size = p->size;
183 size_t i, j, k;
184
185 if (size < 2)
186 {
187 return GSL_FAILURE;
188 }
189
190 i = size - 2;
191
192 while ((p->data[i] < p->data[i+1]) && (i != 0))
193 {
194 i--;
195 }
196
197 if ((i == 0) && (p->data[0] < p->data[1]))
198 {
199 return GSL_FAILURE;
200 }
201
202 k = i + 1;
203
204 for (j = i + 2; j < size; j++ )
205 {
206 if ((p->data[j] < p->data[i]) && (p->data[j] > p->data[k]))
207 {
208 k = j;
209 }
210 }
211
212 /* swap i and k */
213
214 {
215 size_t tmp = p->data[i];
216 p->data[i] = p->data[k];
217 p->data[k] = tmp;
218 }
219
220 for (j = i + 1; j <= ((size + i) / 2); j++)
221 {
222 size_t tmp = p->data[j];
223 p->data[j] = p->data[size + i - j];
224 p->data[size + i - j] = tmp;
225 }
226
227 return GSL_SUCCESS;
228 }
229
230 int
gsl_permutation_mul(gsl_permutation * p,const gsl_permutation * pa,const gsl_permutation * pb)231 gsl_permutation_mul (gsl_permutation * p, const gsl_permutation * pa, const gsl_permutation * pb)
232 {
233 size_t i;
234 const size_t size = p->size;
235
236 if (pa->size != size)
237 {
238 GSL_ERROR("size of result does not match size of pa", GSL_EINVAL);
239 }
240
241 if (pb->size != size)
242 {
243 GSL_ERROR("size of result does not match size of pb", GSL_EINVAL);
244 }
245
246 for (i = 0; i < size; i++)
247 {
248 p->data[i] = pb->data[pa->data[i]];
249 }
250
251 return GSL_SUCCESS;
252 }
253 int
gsl_permutation_memcpy(gsl_permutation * dest,const gsl_permutation * src)254 gsl_permutation_memcpy (gsl_permutation * dest,
255 const gsl_permutation * src)
256 {
257 const size_t src_size = src->size;
258 const size_t dest_size = dest->size;
259
260 if (src_size != dest_size)
261 {
262 GSL_ERROR ("permutation lengths are not equal", GSL_EBADLEN);
263 }
264
265 {
266 size_t j;
267
268 for (j = 0; j < src_size; j++)
269 {
270 dest->data[j] = src->data[j];
271 }
272 }
273
274 return GSL_SUCCESS;
275 }
276