Arndt - Algorithms for Programmers (523138), страница 40
Текст из файла (страница 40)
SELECTED COMBINATORIAL ALGORITHMS};232return 1;}const ulong * data() { return x_; }friend ostream & operator << (ostream &os, const comb_colex &x);[FXT: class comb colex in comb/combcolex.h]For the connection between lex-order and colex-order see section 8.8Usage is completely analogue to that of the class comb lex, cf. [FXT: file demo/combcolex-demo.cc].11.3Combinations in minimal-change orderThe combinations of three elements out of six in minimal-change order are...111..11.1..111...1.11.11..1.11.1..111...1.1.1.1.11..1..1111...111..1.11.1..111...1.1..11.1.1.1.11..1..1.11..11.1...11[[[[[[[[[[[[[[[[[[[[001001201001230120101221333221444433322123334444445555555555]]]]]]]]]]]]]]]]]]]]swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:(0,(3,(1,(2,(4,(1,(2,(3,(1,(2,(5,(1,(2,(3,(4,(1,(2,(3,(1,(0,0)1)0)0)1)0)1)0)0)0)1)0)1)2)0)0)1)0)0)2)####################012345678910111213141516171819The algorithm used in the utility class [FXT: class comb minchange in comb/combminchange.h] is basedon inlined versions of the routines that were explained in the corresponding bit-magic section (8.13).class comb_minchange{public:ulong n_; // number of elements to choose fromulong k_; // number of elements of subsetsulong igc_bits_;ulong bits_;ulong igc_last_;ulong igc_first_;ulong sw1_, sw2_;ulong *x_;public:comb_minchange(ulong n, ulong k){n_ = (n ? n : 1); // not zerok_ = (k ? k : 1); // not zerox_ = new ulong[k_];igc_last_ = igc_last_comb(k_, n_);igc_first_ = first_sequency(k_);first();}~comb_minchange(){delete [] x_;}CHAPTER 11.
SELECTED COMBINATORIAL ALGORITHMSconst ulong * data()};const{ return x_; }ulong first(){igc_bits_ = igc_first_;bits_ = gray_code( igc_last_ ); // to get sw1_, sw2_ rightsync_x();return bits_;}ulong last(){igc_bits_ = igc_last_;bits_ = gray_code( igc_first_ ); // to get sw1_, sw2_ rightsync_x();return bits_;}ulong next() // return zero if current comb is the last{if ( igc_bits_ == igc_last_ ) return 0;ulong gy, y, i = 2;do{y = igc_bits_ + i;gy = gray_code( y );i <<= 1;}while ( bit_count( gy ) != k_ );igc_bits_ = y;sync_x();return bits_;}ulong prev() // return zero if current comb is the first{if ( igc_bits_ == igc_first_ ) return 0;ulong gy, y, i = 2;do{y = igc_bits_ - i;gy = gray_code( y );i <<= 1;}while ( bit_count( gy ) != k_ );igc_bits_ = y;sync_x();return bits_;}void sync_x() // aux// Sync bits into array and// set sw1_ and sw2_{ulong tbits = gray_code( igc_bits_ );ulong sw = bits_ ^ tbits;bits_ = tbits;ulong xi = 0, bi = 0;while ( bi < n_ ){if ( tbits & 1 ) x_[xi++] = bi;++bi;tbits >>= 1;}sw1_ = 0;while ( 0==(sw&1) ) { sw >>= 1; ++sw1_; }sw2_ = sw1_;do { sw >>= 1; ++sw2_; } while ( 0==(sw&1) );}friend ostream & operator << (ostream &os, const comb_minchange &x);The listing at the beginning of this section can be generated via code like:233CHAPTER 11.
SELECTED COMBINATORIAL ALGORITHMS234ulong ct = 0, n = 6, k = 3;comb_minchange comb(n, k);comb.first();do{for (long k=n-1; k>=0; --k) cout << ((bits>>k)&1 ? ’1’ : ’.’);cout << "[ " << comb << " ] ";cout << " swap: (" << comb.sw1_ << ", " << comb.sw2_ << ") ";cout << " #" << setw(3) << ct;++ct;cout << endl;}while ( comb.next() );cf. [FXT: file demo/combminchange-demo.cc].11.4Combinations in alternative minimal-change orderThere is more than one minimal-change order. Consider the sequence of bit-sets generated in section8.13: alternative orderings that have the minimal-change property are e.g.
described by 1) the sequencewith each word reversed or, more general 2) every permutation of the bits 3) the sequence with its bitsnegated 4) cyclical rotations of (1) . . . (3)¡¢Here we use the negated and bit-reversed sequence for n−kin order to generate the combinationsn¡k ¢corresponding to n :n = 6 k = 3:...111[.1..11[1...11[..1.11[.11..1[1.1..1[11...1[.1.1.1[1..1.1[..11.1[.111..[1.11..[11.1..[111...[.11.1.[1.1.1.[11..1.[.1.11.[1..11.[..111.[000000000022231111111111334222334433422224534554534555455453]]]]]]]]]]]]]]]]]]]]swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:(3,(4,(5,(5,(4,(5,(4,(5,(5,(5,(4,(5,(4,(3,(5,(5,(4,(5,(5,(5,0)2)4)3)1)4)3)2)4)3)0)4)3)2)1)4)3)2)4)3)####################012345678910111213141516171819The interesting feature is that the last combination is identical to the first shifted left by one.
This makesit easy to generate the subsets of a set with n elements in monotonic min-change order by concatenatingthe sequences for k = 1, 2, . . . , n.The usage of the utility class [FXT: class comb alt minchange in comb/combaltminchange.h] is identical to that of the ”standard” min-change order.The above listing can be produced viaulong n = 6, k = 3, ct = 0;comb_alt_minchange comb(n, k);comb.first();do{ulong bits = revbin( ~comb.bits_, n); // reversed and negatedcout << "";for (long k=n-1; k>=0; --k) cout << ((bits>>k)&1 ? ’1’ : ’.’);cout << "[ " << comb << " ] ";CHAPTER 11.
SELECTED COMBINATORIAL ALGORITHMS235cout << " swap: (" << comb.sw1_ << ", " << comb.sw2_ << ") ";cout << " #" << setw(3) << ct;++ct;cout << endl;}while ( comb.next() );11.5Offline functions: funcemuSometimes it is possible to find recursive algorithm for solving some problem that is not easily solvediteratively. However the recursive implementations might produce the results in midst of its calling graph.When a utility class providing a the results one by one with some next call is required there is an apparentproblem: There is only one stack available for function calls1 . We do not have offline functions.As an example consider the following recursive code2int n = 4;int v[n];int main(){paren(0, 0);return 0;}void paren(long i, long s){long k, t;if ( i<n ){for (k=0; k<=i-s; ++k){a[i-1] = k;t = s + a[i-1];q[t + i] = ’(’;paren(i + 1, t); // recursionq[t + i] = ’)’;}}else{a[i-1] = n - s;Visit(); // next set of parens available}}that generates following output (the different ways to group four pairs of parenthesis):(((())))((()()))((())())((()))()(()(()))(()()())(()())()(())(())(())()()()((()))()(()())()(())()()()(())()()()()A reasonable way to create offline functions3 is to rewrite the function as a state engine and utilize aclass [FXT: class funcemu in aux0/funcemu.h] that provides two stacks, one for local variables and onefor the state of the function:1 Truefor the majority of the programming languages.by Glenn Rhoads3 A similar mechanism is called coroutines in languages that offer it.2 givenCHAPTER 11.
SELECTED COMBINATORIAL ALGORITHMS236template <typename Type>class funcemu{public:ulong tp_; // sTate stack Pointerulong dp_; // Data stack Pointerulong *t_; // sTate stackType *d_; // Data stackpublic:funcemu(ulong maxdepth, ulong ndata){t_ = new ulong[maxdepth];d_ = new Type[ndata];init();}~funcemu(){delete [] d_;delete [] t_;}void init() { dp_=0; tp_=0; }void stpush(ulong x) { t_[tp_++] = x; }ulong stpeek() const { return t_[tp_-1]; }void stpeek(ulong &x) { x = t_[tp_-1]; }void stpoke(ulong x) { t_[tp_-1] = x; }void stpop() { --tp_; }void stpop(ulong ct) { tp_-=ct; }void stnext() { ++t_[tp_-1]; }void stnext(ulong x) { t_[tp_-1] = x; }bool more() const { return (0!=dp_); }void push(Type x) { d_[dp_++] = x; }void push(Type x, Type y) { push(x); push(y); }void push(Type x, Type y, Type z) { push(x); push(y); push(z); }void push(Type x, Type y, Type z, Type u){ push(x); push(y); push(z); push(u); }void peek(Type &x) { x = d_[dp_-1]; }void peek(Type &x, Type &y){ y = d_[dp_-1]; x = d_[dp_-2]; }void peek(Type &x, Type &y, Type &z){ z = d_[dp_-1]; y = d_[dp_-2]; x = d_[dp_-3]; }void peek(Type &x, Type &y, Type &z, Type &u){ u = d_[dp_-1]; z = d_[dp_-2]; y = d_[dp_-3]; x = d_[dp_-4]; }void poke(Type x) { d_[dp_-1] = x; }void poke(Type x, Type y){ d_[dp_-1] = y; d_[dp_-2] = x; }void poke(Type x, Type y, Type z){ d_[dp_-1] = z; d_[dp_-2] = y; d_[dp_-3] = x; }void poke(Type x, Type y, Type z, Type u){ d_[dp_-1] = u; d_[dp_-2] = z; d_[dp_-3] = y; d_[dp_-4] = x; }void pop(ulong ct=1) { dp_-=ct; }};Rewriting the function in question (as part of a utility class, [FXT: file comb/paren.h] and [FXT: filecomb/paren.cc]) only requires the understanding of the language, not of the algorithm.
The process isstraight forward but needs a bit of concentration, #defines are actually useful to slightly beautify thecode:#define PAREN0 // initial state#define RETURN 20//args=(i, s)(k, t)=locals#define EMU_CALL(func, i, s, k, t) fe_->stpush(func);paren::next_recursion(){int i, s; // argsint k, t; // localsredo:fe_->push(i, s, k, t);CHAPTER 11. SELECTED COMBINATORIAL ALGORITHMS}237fe_->peek(i, s, k, t);loop:switch ( fe_->stpeek() ){case 0:if ( i>=n ){x[i-1] = n - s;fe_->stnext( RETURN ); return 1;}fe_->stnext();case 1:if ( k>i-s ) // loop end ?{break; // shortcut: nothing to do at end}fe_->stnext();case 2: // start of loop bodyx[i-1] = k;t = s + x[i-1];str[t+i] = ’(’; // OPEN_CHAR;fe_->poke(i, s, k, t); fe_->stnext();EMU_CALL( PAREN, i+1, t, 0, 0 );goto redo;case 3:str[t+i] = ’)’; // CLOSE_CHAR;++k;if ( k>i-s ) // loop end ?{break; // shortcut: nothing to do at end}fe_->stpoke(2); goto loop; // shortcut: back to loop bodydefault: ;}fe_->pop(4); fe_->stpop(); // emu_return to callerif ( fe_->more() ) goto redo;return 0; // return from top level emu_callThe constructor initializes the funcemu and pushes the needed variables and parameters on the datastack and the initial state on the state stack:paren::paren(int nn){n = (nn>0 ? nn : 1);x = new int[n];str = new char[2*n+1];for (int i=0; i<2*n; ++i) str[i] = ’)’;str[2*n] = 0;fe_ = new funcemu<int>(n+1, 4*(n+1));//i, s, k, tEMU_CALL( PAREN, 0, 0, 0, 0 );idx = 0;q = next_recursion();}The EMU_CALL actually only initializes the data for the state engine, the following call to next_recursionthen lets the thing run.The method next of the paren class lets the offline function advance until the next result is available:int paren::next(){if ( 0==q ) return 0;else{q = next_recursion();CHAPTER 11.
SELECTED COMBINATORIAL ALGORITHMS}}return238( q ? ++idx : 0 );Performance wise the funcemu-rewritten functions are close to the original (state engines are fast and theoperations within funcemu are cheap).The shown method can also applied when the recursive algorithm consists of more than one function bymerging the functions into one state engine.The presented mechanism is also useful for unmaintainable code insanely cluttered with goto statements.Further, investigating the contents of the data stack can be of help in the search of a iterative solution.11.6ParenthesisAn iterative scheme to generate all valid ways to group parenthesis can be comes from a modified versionof the combinations in co-lexicographic order (see section 11.2). For n = 5 pairs the possible combinationsare (the right column has a one where a closing parenthesis occurs, else a dot):((((()))))(((()())))(((())()))(((()))())(((())))()((()(())))((()()()))((()())())((()()))()((())(()))((())()())((())())()((()))(())((()))()()(()((())))(()(()()))(()(())())(()(()))()(()()(()))(()()()())(()()())()(()())(())(()())()()(())((()))(())(()())(())(())()(())()(())(())()()()()(((())))()((()()))()((())())()((()))()()(()(()))()(()()())()(()())()()(())(())()(())()()()()((()))()()(()())()()(())()()()()(())()()()()().....11111....1.1111....11.111....111.11....1111.1...1..1111...1.1.111...1.11.11...1.111.1...11..111...11.1.11...11.11.1...111..11...111.1.1..1...1111..1..1.111..1..11.11..1..111.1..1.1..111..1.1.1.11..1.1.11.1..1.11..11..1.11.1.1..11...111..11..1.11..11..11.1..11.1..11..11.1.1.1.1....1111.1...1.111.1...11.11.1...111.1.1..1..111.1..1.1.11.1..1.11.1.1..11..11.1..11.1.1.1.1...111.1.1..1.11.1.1..11.1.1.1.1..11.1.1.1.1.1##########################################01234567891011121314151617181920212223242526272829303132333435363738394041Observe that whenever a repeated pattern of .1 is at the right end the next combination is generated bygathering these ones and the block of ones to its left, moving the leftmost one position to the left and allthe others as a block to the right end (see the transitions from #13 to #14 or #36 to #37).The code of the resulting utility class [FXT: class paren2 in comb/paren2.h] is concise and fast:class paren2// parentheses by a modified comb_colex procedureCHAPTER 11.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
