Combination algorithm for arranging algorithms in STL

zhaozj2021-02-16  67

Combination.h

//combination.h #ifndef __COMBINATION_H__ #define __COMBINATION_H__ // Non recursive template function template bool next_combination (BidIt n_begin, BidIt n_end, BidIt r_begin, BidIt r_end) {bool boolmarked = false; BidIt r_marked; BidIt n_it1 = n_end ; --n_it1; bidit tmp_R_END = r_end; --tmp_r_end; bidit tmp_r_begin = r_begin; --TMP_R_BEGIN; for (bidit r_it1 = tmp_r_end; r_it1! = tmp_r_begin; --r_it1, - n_it1) {ix (* r_it1 == * n_it1) {if (r_it1! = r_begin) // to ensure not at the start of r sequence {boolmarked = true; r_marked = (- r_it1); r_it1; // address it back again continue;} else / / it means it is at the start the sequence, so return false return false;} else // if (* r_it1! = * n_it1) {// marked code if (boolmarked == true) {// for loop to find Which Marked is in the first sequence bidit n_marked; // mark in first sequence for (bidit n_it2 = n_egin; n_it2! = n_nd; n_it2) if (* r_marked == * n_it2) {n_marked = n_it2; break;} bidit n_it3 = n_marked; for (bidit r_it2 = r_marked; r_it2! = r_end; r_it2, n_it3) { * r_it2 = * n_it3;} return true;} for (bidit n_it4 = n_begin; n_it4! = n_end; n_it4) if (* r_it1 == * n_it4) {* r_it1 = * ( n_it4); return true; }}} return true; // will never reach here} // Non recursive template function template bool prev_combination (BidIt n_begin, BidIt n_end, BidIt r_begin, BidIt r_end) {bool boolsame = false; BidIt marked; // for r BidIt r_marked; BidIt n_marked; BidIt tmp_n_end = n_end; --tmp_n_end; BidIt tmp_n_begin = n_begin; --tmp_n_begin; BidIt r_it1 = r_end; --r_it1; for (BidIt n_it1 = tmp_n_end; n_it1 = tmp_n_begin!;

--N_IT1) {if (* r_it1 == * n_it1) {r_marked = r_it1; n_marked = n_it1; break;}} bidit n_it2 = n_nd; bidit tmp_r_end; bidit tmp_r_begin = r_begin; --TMP_R_BEGIN; For (bidit r_it2 = r_marked; r_it2! = tmp_r_begin; --r_it2, - n_it2) {if (* r_it2 == * n_it2) {if (r_it2 == r_begin && * r_it2! = * n_begin) {for (bidit n_it3 = n_begin; n_it3! = n_nd; n_it3) {if (* r_it2 == * n_it3) {marked = r_it2; * r_it2 = * (- n_it3); bidit n_it4 = n_end; --n_it4; for (bidit r_it3 = TMP_R_END; r_it3! = tmp_r_begin && r_it3! = marked; --r_it3, - n_it4 {* r_it3 = * n_it4;} return true;}}} else if (r_it2 == r_begin && * r_it2 == * n_begin) {RETURN FALSE ; // no more previous combination;}} else // if (* r_it2! = * n_it2) { r_it2; marked = r_it2; for (bidit n_it5 = n_begin; n_it5! = n_end; n_it5) {IF ( * r_it2 == * n_it5) {* r_it2 = * (- n_it5); bidit n_it6 = n_end; --n_it6; for (bidit r_it4 = tmp_r_end; r_it4! = tmp_r_begin && r_it4! = marked; --r_it4, - n_it6 ) {* r_it4 = * n_it6;} return true;}}}} Return false; // will never reach here, unless tem late function template void recursive_combination (RanIt nbegin, RanIt nend, int n_column, RanIt rbegin, RanIt rend, int r_column, int loop, Func func) {int r_size = rend-rbegin; int localloop = loop; INT local_n_column = n_column; // a Different Combination IS OUT IF (r_column> (r_size-1)) {FUNC (RBEGIN, REND); RETURN;} / for (int i = 0; i <= Loop; i) {Ranit it1 = rbegin; for (int CNT = 0; CNT

for (int cnt2 = 0; cnt2

usage:

Template Bool next_combination (bidit n_begin, bidit n_end, bidit r_begin, bidit r_end) Template BOOL prev_combination (bidit n_begin, bidit n_end, bidit r_begin, bidit r_end)

This even function corresponds to Next_Permutation and Prev_Prmutation in STL. Type BIDIT is a random iterator or a pointer. There are two containers with n and r. So obvious, n_begin, n_end is a range of N. r_begin, r_end is a range of R. n is a container that needs to be arranged. R is the output and initialization of the result. When the two functions of the first call are R, the front (after) N elements that initialize into n are initialized, such as the full alignment can be completed. example:

String n = "abcd"; string r = "ab"; do {cout << r << endl;} while (n.egin (), n.end (), r.begin (), R.End ())

In the next_combination, R needs to be initialized to n, and R in the prev_combination, R needs to be initialized into N-N-N elements.

转载请注明原文地址:https://www.9cbs.com/read-17355.html

New Post(0)