File indexing completed on 2023-03-17 11:15:57
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011 #ifndef __COMBINATION_H__
0012 #define __COMBINATION_H__
0013
0014 namespace stdcomb {
0015
0016
0017 template <class BidIt>
0018
0019 inline bool next_combination(BidIt n_begin, BidIt n_end, BidIt r_begin, BidIt r_end) {
0020 bool boolmarked = false;
0021 BidIt r_marked;
0022
0023 BidIt n_it1 = n_end;
0024 --n_it1;
0025
0026 BidIt tmp_r_end = r_end;
0027 --tmp_r_end;
0028
0029 for (BidIt r_it1 = tmp_r_end; r_it1 != r_begin || r_it1 == r_begin; --r_it1, --n_it1) {
0030 if (*r_it1 == *n_it1) {
0031 if (r_it1 != r_begin)
0032 {
0033 boolmarked = true;
0034 r_marked = (--r_it1);
0035 ++r_it1;
0036 continue;
0037 } else
0038 return false;
0039 } else
0040 {
0041
0042 if (boolmarked == true) {
0043
0044 BidIt n_marked;
0045 for (BidIt n_it2 = n_begin; n_it2 != n_end; ++n_it2)
0046 if (*r_marked == *n_it2) {
0047 n_marked = n_it2;
0048 break;
0049 }
0050
0051 BidIt n_it3 = ++n_marked;
0052 for (BidIt r_it2 = r_marked; r_it2 != r_end; ++r_it2, ++n_it3) {
0053 *r_it2 = *n_it3;
0054 }
0055 return true;
0056 }
0057 for (BidIt n_it4 = n_begin; n_it4 != n_end; ++n_it4)
0058 if (*r_it1 == *n_it4) {
0059 *r_it1 = *(++n_it4);
0060 return true;
0061 }
0062 }
0063 }
0064
0065 return true;
0066 }
0067
0068
0069 template <class BidIt, class Prediate>
0070
0071 inline bool next_combination(BidIt n_begin, BidIt n_end, BidIt r_begin, BidIt r_end, Prediate Equal) {
0072 bool boolmarked = false;
0073 BidIt r_marked;
0074
0075 BidIt n_it1 = n_end;
0076 --n_it1;
0077
0078 BidIt tmp_r_end = r_end;
0079 --tmp_r_end;
0080
0081 for (BidIt r_it1 = tmp_r_end; r_it1 != r_begin || r_it1 == r_begin; --r_it1, --n_it1) {
0082 if (Equal(*r_it1, *n_it1)) {
0083 if (r_it1 != r_begin)
0084 {
0085 boolmarked = true;
0086 r_marked = (--r_it1);
0087 ++r_it1;
0088 continue;
0089 } else
0090 return false;
0091 } else
0092 {
0093
0094 if (boolmarked == true) {
0095
0096 BidIt n_marked;
0097 for (BidIt n_it2 = n_begin; n_it2 != n_end; ++n_it2)
0098 if (Equal(*r_marked, *n_it2)) {
0099 n_marked = n_it2;
0100 break;
0101 }
0102
0103 BidIt n_it3 = ++n_marked;
0104 for (BidIt r_it2 = r_marked; r_it2 != r_end; ++r_it2, ++n_it3) {
0105 *r_it2 = *n_it3;
0106 }
0107 return true;
0108 }
0109 for (BidIt n_it4 = n_begin; n_it4 != n_end; ++n_it4)
0110 if (Equal(*r_it1, *n_it4)) {
0111 *r_it1 = *(++n_it4);
0112 return true;
0113 }
0114 }
0115 }
0116
0117 return true;
0118 }
0119
0120
0121 template <class BidIt>
0122
0123 inline bool prev_combination(BidIt n_begin, BidIt n_end, BidIt r_begin, BidIt r_end) {
0124 BidIt marked;
0125 BidIt r_marked;
0126 BidIt n_marked;
0127
0128 BidIt tmp_n_end = n_end;
0129 --tmp_n_end;
0130
0131 BidIt r_it1 = r_end;
0132 --r_it1;
0133
0134 for (BidIt n_it1 = tmp_n_end; n_it1 != n_begin || n_it1 == n_begin; --n_it1) {
0135 if (*r_it1 == *n_it1) {
0136 r_marked = r_it1;
0137 n_marked = n_it1;
0138 break;
0139 }
0140 }
0141
0142 BidIt n_it2 = n_marked;
0143
0144 BidIt tmp_r_end = r_end;
0145 --tmp_r_end;
0146
0147 for (BidIt r_it2 = r_marked; r_it2 != r_begin || r_it2 == r_begin; --r_it2, --n_it2) {
0148 if (*r_it2 == *n_it2) {
0149 if (r_it2 == r_begin && !(*r_it2 == *n_begin)) {
0150 for (BidIt n_it3 = n_begin; n_it3 != n_end; ++n_it3) {
0151 if (*r_it2 == *n_it3) {
0152 marked = r_it2;
0153 *r_it2 = *(--n_it3);
0154
0155 BidIt n_it4 = n_end;
0156 --n_it4;
0157 for (BidIt r_it3 = tmp_r_end; (r_it3 != r_begin || r_it3 == r_begin) && r_it3 != marked;
0158 --r_it3, --n_it4) {
0159 *r_it3 = *n_it4;
0160 }
0161 return true;
0162 }
0163 }
0164 } else if (r_it2 == r_begin && *r_it2 == *n_begin) {
0165 return false;
0166 }
0167 } else
0168 {
0169 ++r_it2;
0170 marked = r_it2;
0171 for (BidIt n_it5 = n_begin; n_it5 != n_end; ++n_it5) {
0172 if (*r_it2 == *n_it5) {
0173 *r_it2 = *(--n_it5);
0174
0175 BidIt n_it6 = n_end;
0176 --n_it6;
0177 for (BidIt r_it4 = tmp_r_end; (r_it4 != r_begin || r_it4 == r_begin) && r_it4 != marked; --r_it4, --n_it6) {
0178 *r_it4 = *n_it6;
0179 }
0180 return true;
0181 }
0182 }
0183 }
0184 }
0185 return false;
0186 }
0187
0188
0189 template <class BidIt, class Prediate>
0190
0191 inline bool prev_combination(BidIt n_begin, BidIt n_end, BidIt r_begin, BidIt r_end, Prediate Equal) {
0192 BidIt marked;
0193 BidIt r_marked;
0194 BidIt n_marked;
0195
0196 BidIt tmp_n_end = n_end;
0197 --tmp_n_end;
0198
0199 BidIt r_it1 = r_end;
0200 --r_it1;
0201
0202 for (BidIt n_it1 = tmp_n_end; n_it1 != n_begin || n_it1 == n_begin; --n_it1) {
0203 if (Equal(*r_it1, *n_it1)) {
0204 r_marked = r_it1;
0205 n_marked = n_it1;
0206 break;
0207 }
0208 }
0209
0210 BidIt n_it2 = n_marked;
0211
0212 BidIt tmp_r_end = r_end;
0213 --tmp_r_end;
0214
0215 for (BidIt r_it2 = r_marked; r_it2 != r_begin || r_it2 == r_begin; --r_it2, --n_it2) {
0216 if (Equal(*r_it2, *n_it2)) {
0217 if (r_it2 == r_begin && !Equal(*r_it2, *n_begin)) {
0218 for (BidIt n_it3 = n_begin; n_it3 != n_end; ++n_it3) {
0219 if (Equal(*r_it2, *n_it3)) {
0220 marked = r_it2;
0221 *r_it2 = *(--n_it3);
0222
0223 BidIt n_it4 = n_end;
0224 --n_it4;
0225 for (BidIt r_it3 = tmp_r_end; (r_it3 != r_begin || r_it3 == r_begin) && r_it3 != marked;
0226 --r_it3, --n_it4) {
0227 *r_it3 = *n_it4;
0228 }
0229 return true;
0230 }
0231 }
0232 } else if (r_it2 == r_begin && Equal(*r_it2, *n_begin)) {
0233 return false;
0234 }
0235 } else
0236 {
0237 ++r_it2;
0238 marked = r_it2;
0239 for (BidIt n_it5 = n_begin; n_it5 != n_end; ++n_it5) {
0240 if (Equal(*r_it2, *n_it5)) {
0241 *r_it2 = *(--n_it5);
0242
0243 BidIt n_it6 = n_end;
0244 --n_it6;
0245 for (BidIt r_it4 = tmp_r_end; (r_it4 != r_begin || r_it4 == r_begin) && r_it4 != marked; --r_it4, --n_it6) {
0246 *r_it4 = *n_it6;
0247 }
0248 return true;
0249 }
0250 }
0251 }
0252 }
0253 return false;
0254 }
0255
0256
0257 template <class RanIt, class Func>
0258
0259 void recursive_combination(
0260 RanIt nbegin, RanIt nend, int n_column, RanIt rbegin, RanIt rend, int r_column, int loop, Func func) {
0261 int r_size = rend - rbegin;
0262
0263 int localloop = loop;
0264 int local_n_column = n_column;
0265
0266
0267 if (r_column > (r_size - 1)) {
0268 func(rbegin, rend);
0269 return;
0270 }
0271
0272
0273 for (int i = 0; i <= loop; ++i) {
0274 RanIt it1 = rbegin;
0275 for (int cnt = 0; cnt < r_column; ++cnt) {
0276 ++it1;
0277 }
0278
0279 RanIt it2 = nbegin;
0280 for (int cnt2 = 0; cnt2 < n_column + i; ++cnt2) {
0281 ++it2;
0282 }
0283
0284 *it1 = *it2;
0285
0286 ++local_n_column;
0287
0288 recursive_combination(nbegin, nend, local_n_column, rbegin, rend, r_column + 1, localloop, func);
0289 --localloop;
0290 }
0291 }
0292
0293 }
0294
0295 #endif