2 * Copyright (C) 2013 Andrea Mazzoleni
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 2 of the License, or
7 * (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
15 #ifndef __RAID_COMBO_H
16 #define __RAID_COMBO_H
21 * Get the first permutation with repetition of r of n elements.
23 * Typical use is with permutation_next() in the form :
26 * permutation_first(R, N, i);
28 * code using i[0], i[1], ..., i[R-1]
29 * } while (permutation_next(R, N, i));
31 * It's equivalent at the code :
33 * for(i[0]=0;i[0]<N;++i[0])
34 * for(i[1]=0;i[1]<N;++i[1])
36 * for(i[R-2]=0;i[R-2]<N;++i[R-2])
37 * for(i[R-1]=0;i[R-1]<N;++i[R-1])
38 * code using i[0], i[1], ..., i[R-1]
40 static __always_inline void permutation_first(int r, int n, int *c)
44 (void)n; /* unused, but kept for clarity */
45 assert(0 < r && r <= n);
47 for (i = 0; i < r; ++i)
52 * Get the next permutation with repetition of r of n elements.
53 * Return ==0 when finished.
55 static __always_inline int permutation_next(int r, int n, int *c)
57 int i = r - 1; /* present position */
60 /* next element at position i */
63 /* if the position has reached the max */
66 /* if we are at the first level, we have finished */
70 /* increase the previous position */
77 /* initialize all the next positions, if any */
87 * Get the first combination without repetition of r of n elements.
89 * Typical use is with combination_next() in the form :
92 * combination_first(R, N, i);
94 * code using i[0], i[1], ..., i[R-1]
95 * } while (combination_next(R, N, i));
97 * It's equivalent at the code :
99 * for(i[0]=0;i[0]<N-(R-1);++i[0])
100 * for(i[1]=i[0]+1;i[1]<N-(R-2);++i[1])
102 * for(i[R-2]=i[R-3]+1;i[R-2]<N-1;++i[R-2])
103 * for(i[R-1]=i[R-2]+1;i[R-1]<N;++i[R-1])
104 * code using i[0], i[1], ..., i[R-1]
106 static __always_inline void combination_first(int r, int n, int *c)
110 (void)n; /* unused, but kept for clarity */
111 assert(0 < r && r <= n);
113 for (i = 0; i < r; ++i)
118 * Get the next combination without repetition of r of n elements.
119 * Return ==0 when finished.
121 static __always_inline int combination_next(int r, int n, int *c)
123 int i = r - 1; /* present position */
124 int h = n; /* high limit for this position */
127 /* next element at position i */
130 /* if the position has reached the max */
133 /* if we are at the first level, we have finished */
137 /* increase the previous position */
145 /* initialize all the next positions, if any */
147 /* each position start at the next value of the previous one */