Arndt - Algorithms for Programmers (523138), страница 41
Текст из файла (страница 41)
SELECTED COMBINATORIAL ALGORITHMS239{public:ulong k_; // number of paren pairsulong n_; // ==2*kulong *x_; // (negated) positions where a close paren occurschar *str_; // string representation, e.g. "((())())()"public:paren2(ulong k){k_ = (k>1 ? k : 2); // not zero (empty) or one (trivial: "()")n_ = 2 * k_;x_ = new ulong[k_ + 1];x_[k_] = 999; // sentinelstr_ = new char[n_ + 1];str_[n_] = 0;first();}~paren2(){delete [] x_;delete [] str_;}};void first(){for (ulong i=0; i<k_; ++i) x_[i] = i;}void last(){for (ulong i=0; i<k_; ++i) x_[i] = 2*i;}ulong next() // return zero if previous paren was the last{ulong j = 0;if ( x_[1] == 2 ){// scan for low end == 010101:j = 2;while ( (j<=k_) && (x_[j]==2*j) ) ++j; // can touch sentinelif ( j==k_ ){first();return 0;}}// if ( k_==1 ) return 0; // uncomment to make algorithm work for k_==1// scan block:while ( 1 == (x_[j+1] - x_[j]) ) { ++j; }++x_[j]; // move edge element upfor (ulong i=0; i<j; ++i) x_[i] = i; // attach block at low endreturn 1;}const ulong * data() { return x_; }const char * string() // generate on demand{for (ulong j=0; j<n_; ++j) str_[j] = ’(’;for (ulong j=0; j<k_; ++j) str_[n_-1-x_[j]] = ’)’;return str_;}The number of valid combinations of n parenthesis pairs is¡2 n¢Cn=nn+1(11.1)as nicely explained in (chapter 7.5, example 4 on page 343 of) [13].
These are the Catalan numbers:CHAPTER 11. SELECTED COMBINATORIAL ALGORITHMSn12345678910111211.7240Cn1251442132429143048621679658786208012PartitionsAn integer x is the sum of the positive integers less or equal to itself in various ways (x = 4 in thisexample):4*2*0*1*0*11111+++++0*1*2*0*0*22222+++++0*0*0*1*0*33333+++++0*0*0*0*1*44444==========44444The left hand side expressions are called the partitions of the number x.
We want to attack a slightlymore general problem and find all partitions of a number x with respect to a set V = {v0 , v1 , . . . , vn−1 },Pn−1that is all decompositions of the form x = k=0 ck · vk .The utility class isclass partition{public:ulong ct_; // # of partitions found so farulong n_;// # of valuesulong i_;// level in iterative searchlong *pv_; // values into which to partitionulong *pc_; // multipliers for valuesulong pci_; // temporary for pc_[i_]long *r_;// restlong ri_;// temporary for r_[i_]long x_;// value to partitionpublic:partition(const ulong *pv, ulong n): n_(n==0?1:n){pv_ = new long[n_+1];for (ulong j=0; j<n_; ++j) pv_[j] = pv[j];pc_ = new ulong[n_+1];r_ = new long[n_+1];}~partition(){delete [] pv_;delete [] pc_;delete [] r_;}void init(ulong x); // reset stateulong next(); // generate next partitionulong next_func(ulong i); // auxulong count(ulong x); // count number of partitionsCHAPTER 11.
SELECTED COMBINATORIAL ALGORITHMS};241ulong count_func(ulong i); // auxvoid dump() const;int check(ulong i=0) const;[FXT: class partition in comb/partition.h]The algorithm to count the partitions is to assign to the first bucket a multiple c0 · p0 ≤ x of the firstset element p0 . If c0 · p0 = x we already found a partition, else if c0 · p0 < x solve the problem forx0 := x − c0 · p0 and V 0 := {v1 , v2 , . . . , vn−1 }.ulongpartition::count(ulong x)// count number of partitions{init(x);count_func(n_-1);return ct_;}ulongpartition::count_func(ulong i){if ( 0!=i ){while ( r_[i]>0 ){pc_[i-1] = 0;r_[i-1] = r_[i];count_func(i-1); // recursionr_[i] -= pv_[i];++pc_[i];}}else // recursion end{if ( 0!=r_[i] ){long d = r_[i] / pv_[i];r_[i] -= d * pv_[i];pc_[i] = d;}}if ( 0==r_[i] ) // valid partition found{// if ( whatever ) ++ct_; // restricted count++ct_;return 1;}else return 0;}The algorithm, when rewritten iteratively, can supply the partitions one by one:ulongpartition::next()// generate next partition{if ( i_>=n_ ) return n_;r_[i_] = ri_;pc_[i_] = pci_;i_ = next_func(i_);for (ulong j=0; j<i_; ++j)++i_;ri_ = r_[i_] - pv_[i_];pci_ = pc_[i_] + 1;return i_ - 1; // >=0}ulongpartition::next_func(ulong i)pc_[j] = r_[j] = 0;CHAPTER 11.
SELECTED COMBINATORIAL ALGORITHMS{}242start:if ( 0!=i ){while ( r_[i]>0 ){pc_[i-1] = 0;r_[i-1] = r_[i];--i; goto start;// iteration}}else // iteration end{if ( 0!=r_[i] ){long d = r_[i] / pv_[i];r_[i] -= d * pv_[i];pc_[i] = d;}}if ( 0==r_[i] ) // valid partition found{++ct_;return i;}++i;if ( i>=n_ ) return n_; // search finishedr_[i] -= pv_[i];++pc_[i];goto start; // iteration[FXT: file comb/partition.cc]The routines can easily adapted to the generation of partitions satisfying certain restrictions, e.g.
partitions into unequal parts (i.e. ci ≤ 1).Cf. [FXT: file demo/partition-demo.cc]11.8CompositionsThe compositions of n into at most k parts are the ordered tuples (x0 , x1 , . . . , xk−1 ) where x0 + x1 +. . . + xk−1 = n and 0 ≤ xi ≤ n. Order matters: one 3-composition of 4 is (0, 1, 2, 1), a different one is(2, 0, 1, 1).11.8.1Compositions in lexicographic orderFor the 4-compositions of 4 in lexicographic order are0:1:2:3:4:5:6:7:8:9:10:11:12:13:14:15:16:17:18:19:20:21:22:23:432103210210100321021010012340123012010012301201000001111222334000011122000000000000000111111111CHAPTER 11. SELECTED COMBINATORIAL ALGORITHMS24:25:26:27:28:29:30:31:32:33:34:02101001000001201001003000112001012222223334This is the output of [FXT: file demo/compositionlex-demo.cc].The corresponding utility class is [FXT: class composition lex in comb/compositionlex.h]:class composition_lex{public:ulong n_; // number of elements to choose fromulong *x_; // datapublic:composition_lex(ulong n){n_ = (n ? n : 1); // not zerox_ = new ulong[n_];first();}~composition_lex() { delete [] x_; }const ulong *data() const { return x_; }void first(){x_[0] = n_;for (ulong k=1; k<n_; ++k) x_[k] = 0;}void last(){for (ulong k=0; k<n_; ++k) x_[k] = 0;x_[n_-1] = n_;}ulong next()// Nijenhuis, Wilf{// return zero if current comp.
is last:if ( n_==x_[n_-1] ) return 0;ulong j = 0;while ( 0==x_[j] ) ++j;ulong v = x_[j]; // first nonzerox_[j] = 0;x_[0] = v - 1;++x_[j+1];return 1;}ulong prev(){// return zero if current comp. is first:if ( n_==x_[0] ) return 0;ulong v0 = x_[0];x_[0] = 0;ulong j = 1;while ( 0==x_[j] ) ++j;--x_[j];x_[j-1] = 1 + v0;return 1;}};243CHAPTER 11. SELECTED COMBINATORIAL ALGORITHMS11.8.2244Compositions from combinations¡¢There are 2 n−1n-compositions of n which indicates that there should be a connection to the combin¡¢nations of n out of 2 n − 1 items. In the following listing the (reversed) lex-order combinations 74 areopposed by the compositions of 4:1111...111.1..11.11..1.111...1111..111..1.11.1.1.1.11.1..111.1.11..11.1.1.11..11.11.1..111..1.111...1111.111...111.1..11.11..1.111..111..1.11.1.1.1.11.1.11..11.1.1.11.1..111.111...111.1..11.11..111..1.11.1.1.11..11.111...111.1..111..1.111...111143210321021010032102101002101001000012340123012010012301201001201001000000011112223340000111223000112001000000000000000011111111112222223334The entries in the compositions can be identified by the runs of consecutive bits in the combinations.One bit that follows each run of ones is considered as a separator.
This leads to the functionstatic inline void bit2composition(ulong w, ulong *x, ulong n){for (ulong k=0; k<n; ++k){ulong ct = 0;ulong b;do{b = w & 1;ct += b;w >>= 1;}while ( 0!=b );x[k] = ct;}}The given function enables us to use any routine that generates combinations to produce compositions.The minimal-change combinations (see section 11.3) give the following sequence of compositions:....1111...11.11...1111....111.1...1.111..11..11..11.11...11.1.1..1111....111.1...111..1..1.1.11..1.111...1.11.1..1..111.11...11.11..11..11..1.1[4[2[0[1[3[2[0[1[0[0[1[2[0[1[3[2[0[1024310210101320021000002224331111000000000000000000222]]]]]]]]]]]]]]]]]]##################01234567891011121314151617CHAPTER 11.
SELECTED COMBINATORIAL ALGORITHMS.11.11...11.1.1..11.1..1.1111....111.1...111..1..111...1.1.1..11.1.1.11..1.1.1.1.1.111...1.11.1..1.11..1.1..1.11.1..111..1..11.1.1...111[0[0[1[0[0[0[1[2[0[1[0[0[1[2[0[1[3010001002101013202110100111322000022243331111111111]]]]]]]]]]]]]]]]]#################2451819202122232425262728293031323334This is the output of [FXT: file demo/compositionalt-demo.cc].Note that the minimum-change property of the combinations does not lead to the equivalent for thecompositions.11.8.3Compositions in minimal-change orderThe modified idea to select from the radix-r Gray codes with r = n+1 those that are valid as composition(that is, the sum of digits is one) can be used for the generation of minimal-change compositions. Withn = 4, k = 4 one gets....1111...1.111...11.11...111.1...1111...1.111...1.11.1..1.1.11..1..111..11..11..11.1.1..11.11...111.1...111..1..1111...1.111...1.11.1..1.11..1.1.1..11.1.1.1.1.1.1.11..1..111..1..11.1.1..1.11.1...111.11...11.11..1.1.11..11..11.1.1..11.1..1.11.11...111.1...111..1..111...14321001232100100012100123210010001012343210012100010012321001210001000000111122233432211100000001121000000000000000001111111111222222333nnHowever, the brute-force¡2 n−1¢ scan of the Gray codes is horribly ineffective, as r = (n + 1) candidates arescanned for thecompositions.nTBD: fast algorithm for minchange-compositions11.9Numbers in lexicographic orderA generalization of the lexicographic ordering for binary words (given in section 8.10) for radix 3 (using4 digits and printing a dot for each zero) is.111..11...1....2 .
. .2 1 . .2 1 1 .. 1 . .. 1 1 .CHAPTER 11. SELECTED COMBINATORIAL ALGORITHMS1111111111111111111111111111111222222222........11222...111222..111222..12.1212..12.1212.12.12122222222222222222222222221111111222222222........11222...111222..111222..12.1212..12.1212.12.1212........................1111111222222222........11222...111222..111222..24612.1212..12.1212.12.1212The sequence can be generated by using a list of all 4-digit radix-3 numbers, replacing all trailing zeroes bya character that is sorted before all numbers (a dot works with ascii characters), replacing the remainingzeros by a character that is sorted after all numbers (a ‘z’ with ascii characters), and sorting the usualway.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
