Arndt - Algorithms for Programmers (523138), страница 39

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 39)

Thereby it is useful in situations where linked lists might come to mind. Linked lists have thedisadvantage of the additional data (next- and previous -pointers) proportional to the total size togetherwith the inherent book keeping. Moreover, linked lists that use a call to the systems memory-allocatorfor the insertion of additional entries often suffer from severe performance problems.Here we go [FXT: class rarray in ds/rarray.h]:template <typename Type>class rarray// array that grows in adjustable steps when necessary// rarray := "Resizing array"//// all operations maintain the relative order between elements{public:Type *x_; // dataulong s_; // sizeulong n_; // position of next write, top entry @ n-1ulong gq_; // grow gq elements if necessary, 0 for "don’t grow"CHAPTER 10.

DATA STRUCTURES223public:explicit rarray(ulong n, ulong growq=0){s_ = n;x_ = new Type[s_];n_ = 0; // rarray is emptygq_ = growq;}~rarray() { delete [] x_; }private:rarray & operator = (const rarray &);// forbiddenpublic:Type * data() { return x_; }ulong n() const// Return number of entries{ return n_; }ulong size() const// Return number of allocated entries{ return s_; }ulong append(const Type & z)// Return size of rarray, zero on rarray overflow{if ( n_ >= s_ ){if ( 0==gq_ ) return 0; // overflowgrow();}x_[n_] = z;++n_;return s_;}ulong remove_last(){ulong ret = n_;if ( n_!=0 ) --n_;return ret;}ulong prepend(const Type & z)// Return size of rarray, zero on rarray overflow{if ( n_ >= s_ ){if ( 0==gq_ ) return 0; // overflowgrow();}for (ulong k=n_; k!=0; --k) x_[k] = x_[k-1]; // shift rightx_[0] = z;++n_;return s_;}ulong remove_first()// returns how many elements were there before remove// zero indicates error{ulong ret = n_;if ( n_!=0 ) --n_;for (ulong k=0; k<n_; ++k) x_[k] = x_[k+1]; // shift leftreturn ret;}ulong search(const Type& x, ulong k=0) const{for ( ; k<n_; ++k) if ( x_[k]==x ) return k;return s_;}CHAPTER 10.

DATA STRUCTURES224void sort() { ::quick_sort(x_, n_); }void uniq() { sort(); ::uniq(x_, n_); }ulong insert_at(const Type & v, ulong j)// Return size of rarray// Return zero on error: (rarray overflow or access beyond range)// (i.e. no action unless 0<=j<=n_){if ( j >= n_ ) return 0; // beyond boundsif ( n_ >= s_ ){if ( 0==gq_ ) return 0; // overflowgrow();}for (ulong k=n_; k!=j; --k) x_[k] = x_[k-1];x_[j] = v;++n_;return s_;}ulong remove_at(ulong j)// returns how many elements were there before remove// zero indicates error{ulong ret = n_;if ( j>=n_ ) return 0;--n_;for (ulong k=j; k<n_; ++k) x_[k] = x_[k+1];return ret;}private:void grow(){ulong ns = s_ + gq_; // new sizeType *nx = new Type[ns];copy(x_, nx, s_);delete [] x_;x_ = nx;s_ = ns;}};Note that while the operations append() and remove last() are O(1), the equivalent tasks manipulationthe start of the array, prepend() and remove first(), are O(n) where n is the number of entries.A simple demo in [FXT: file demo/rarray-demo.cc] prints:append ( 1)prepend( 2)append ( 3)prepend( 4)append ( 5)prepend( 6)append ( 7)remove_lastremove_firstprepend( 8)remove_lastremove_firstappend ( 9)remove_lastremove_firstprepend(10)remove_lastremove_firstappend (11)remove_lastremove_firstprepend(12)remove_lastremove_firstappend (13)remove_last12244666488444210102221121213-- 1 1 32 12 14 24 24 22 14 24 22 12 12 11 32 12 11 1 111 - 1 - - - - -331113113333-#=1#=2#=3#=45 3 53 53 55 3 53 - 9 - - - - - - - - - - - - - -7--#=5#=6#=7#=6#=5#=6#=5#=4#=5#=4#=3#=4#=3#=2#=3#=2#=1#=2#=1#=0#=1#=0CHAPTER 10.

DATA STRUCTURESremove_first- (rarray was empty)prepend(14)14 remove_last- remove_first- (rarray was empty)append (15)15 -10.8225------#=0------#=1#=0#=0------#=1Ordered resizable arraySometimes it is desirable to maintain the order of elements in an array during insertion and deletion.The utility class providing the operations on an ordered (resizable) array is [FXT: class ordered rarrayin ds/orderedrarray.h]:template <typename Type>class ordered_rarray : private rarray<Type>// rarray that maintains ascending order of elements//// private inheritance to hide those functions that// might destroy the order{public:explicit ordered_rarray(ulong n, ulong growq=0): rarray<Type>(n, growq){;}~ordered_rarray() {;}private:ordered_rarray & operator = (const ordered_rarray &);// forbiddenpublic:using rarray<Type>::n;using rarray<Type>::data;using rarray<Type>::size;using rarray<Type>::remove_last;using rarray<Type>::remove_first;using rarray<Type>::remove_at;ulong search(const Type & v) const// Return index of first element in that is == v// Return ~0 if there is no such element{ return ::bsearch(x_, n_, v); }ulong search_ge(const Type & v) const// Return index of first element in that is >= v// Return ~0 if there is no such element{ return ::bsearch_ge<Type>(x_, n_, v); }ulong insert(const Type & v)// Insert v so that ascending order is kept.// Return size, zero on rarray overflow.{if ( 0==n_ ) { return append(v); }ulong j = search_ge(v);if ( j>=n_ ) return append(v);elsereturn rarray<Type>::insert_at(v, j);}ulong insert_uniq(const Type & v)// Insert v so that ascending order is kept.// Don’t insert if element already in array.// Return size, zero on rarray overflow.{if ( 0==n_ ) { return append(v); }ulong j = search_ge(v);if ( j>=n_ ) return append(v);else{if ( x_[j] = v ) return 0;return rarray<Type>::insert_at(v, j);CHAPTER 10.

DATA STRUCTURES};}226}If insert uniq() is used exclusively for insertion, the class can be used for ordered sets without repetitions.The demo in [FXT: file demo/orderedrarray-demo.cc] prints:insert( 0)0 - - #=1insert( 0)0 0 - #=2insert( 2)0 0 2 #=3insert( 1)0 0 1 2#=4insert( 3)0 0 1 2 3 insert( 2)0 0 1 2 2 3insert( 5)0 0 1 2 2 3remove @ 30 0 1 2 3 5remove @ 30 0 1 3 5 insert( 2)0 0 1 2 3 5remove @ 30 0 1 3 5 remove @ 20 0 3 5 - insert( 7)0 0 3 5 7 remove @ 20 0 5 7 - remove @ 20 0 7 - - insert( 3)0 0 3 7 - remove @ 20 0 7 - - remove @ 10 7 - - - insert( 8)0 7 8 - - remove @ 10 8 - - - remove @ 10 - - - - insert( 4)0 4 - - - remove @ 10 - - - - remove @ 0- - - - - insert(10)10 - - - - remove @ 0- - - - - remove @ 0- - - - - (ordered_rarray was empty)insert( 4)4 - - - - remove @ 0- - - - - remove @ 0- - - - - (ordered_rarray was empty)insert(12)12 - - - - -10.95--#=5#=6#=7#=6#=5#=6#=5#=4#=5#=4#=3#=4#=3#=2#=3#=2#=1#=2#=1#=0#=1#=0#=0--#=1#=0#=0--#=1Resizable setA data structure for sets that, for the sake of O(1) deletion, does not maintain the relative order of itsentries can be implemented as [FXT: class rset in ds/rset.h]template <typename Type>class rset// set that grows in adjustable steps when necessary// rset := "Resizing set"{public:Type *x_; // dataulong s_; // sizeulong n_; // position of next write, top entry @ n-1ulong gq_; // grow gq elements if necessary, 0 for "don’t grow"public:explicit rset(ulong n, ulong growq=0){s_ = n;x_ = new Type[s_];n_ = 0; // rset is emptygq_ = growq;}~rset() { delete [] x_; }private:rset & operator = (const rset &);public:Type * data() { return x_; }ulong n() const// forbiddenCHAPTER 10.

DATA STRUCTURES227// Return number of entries{ return n_; }ulong size() const// Return number of allocated entries{ return s_; }ulong insert(const Type & z)// Insert element v (append v).// Return size of rset, zero on rset overflow{if ( n_ >= s_ ){if ( 0==gq_ ) return 0; // overflowgrow();}x_[n_] = z;++n_;return s_;}ulong search(const Type & x, ulong k=0) const{for ( ; k<n_; ++k) if ( x_[k]==x ) return k;return s_;}void sort()void uniq(){ ::quick_sort(x_, n_); }{ sort(); ::uniq(x_, n_); }ulong remove_at(ulong j)// returns how many elements were there before remove// zero indicates error{ulong ret = n_;if ( j>=n_ ) return 0;--n_;x_[j] = x_[n_];return ret;}ulong remove(const Type & z){ulong j = search(z);if ( j<n_ ) remove_at(j);return j;}private:void grow(){ulong ns = s_ + gq_; // new sizeType *nx = new Type[ns];copy(x_, nx, s_);delete [] x_;x_ = nx;s_ = ns;}};The output of [FXT: file demo/rset-demo.cc] demonstrates how deleted elements are simply swappedwith the last entry:insert (11)insert ( 2)insert (13)insert ( 4)insert (15)insert ( 6)insert (17)remove_at( 3)remove_at( 3)insert ( 8)remove_at( 3)remove_at( 2)insert (19)11111111111111111111111111222222222222- #=1- #=213 #=313 4#=413 4 15 - 13 4 15 6 13 4 15 6 1713 17 15 6 13 6 15 - 13 6 15 8 13 8 15 - 15 8 - - 15 8 19 - --#=5#=6#=7#=6#=5#=6#=5#=4#=5CHAPTER 10.

DATA STRUCTURESremove_at( 2)11remove_at( 2)11insert (10)11remove_at( 2)11remove_at( 1)11insert (21)11remove_at( 1)11remove_at( 1)11insert (12)11remove_at( 1)11remove_at( 0)insert (23)23remove_at( 0)remove_at( 0)(rset was empty)insert (14)14remove_at( 0)remove_at( 0)(rset was empty)insert (25)252 19 82 8 2 8 102 10 10 - 10 21 21 - - - 12 - - - - - - - - - - - -228----#=4#=3#=4#=3#=2#=3#=2#=1#=2#=1#=0#=1#=0#=0-------#=1#=0#=0-------#=1Chapter 11Selected combinatorial algorithmsThis chapter presents selected combinatorial algorithms.

The generation of combinations, subsets, partitions, and pairings of parentheses (as example for the use of ‘funcemu’) are treated here. Permutationsare treated in a separate chapter because of the not so combinatorial viewpoint taken with most of thematerial (especially the specific examples like the revbin-permutation) there.11.1Combinations in lexicographic orderThe combinations of three elements out of six in lexicographic order are[[[[[[[[[[[[[[[[[[[[000000000011111122231111222334222334334423453454553454554555]]]]]]]]]]]]]]]]]]]]...111..1.11.1..111...11..11.1.1.1.11..1.1.11..11.1..111...1..111..1.11.1..11..11.1.1.1.1.11..1..111..1.11..11.1..111...####################012345678910111213141516171819A bit of contemplation (staring at the ”.1”-strings might help) leads to the code implementing a simpleutility class that supplies the methods first(), last(), next() and prev():class comb_lex{public:ulong n_;ulong k_;ulong *x_;public:comb_lex(ulong n, ulong k){n_ = (n ? n : 1); // not zerok_ = (k ? k : 1); // not zerox_ = new ulong[k_];first();229CHAPTER 11.

SELECTED COMBINATORIAL ALGORITHMS}~comb_lex()};{ delete [] x_; }void first(){for (ulong k=0; k<k_; ++k) x_[k] = k;}void last(){for (ulong i=0; i<k_; ++i) x_[i] = n_ - k_ + i;}ulong next() // return zero if previous comb was the last{if ( x_[0] == n_ - k_ ) { first(); return 0; }ulong j = k_ - 1;// trivial if highest element != highest possible value:if ( x_[j] < (n_-1) ) { ++x_[j]; return 1; }// find highest falling edge:while ( 1 == (x_[j] - x_[j-1]) ) { --j; }// move lowest element of highest block up:ulong z = ++x_[j-1];// ... and attach rest of block:while ( j < k_ ) { x_[j] = ++z; ++j; }return 1;}ulong prev() // return zero if current comb is the first{if ( x_[k_-1] == k_-1 ) { last(); return 0; }// find highest falling edge:ulong j = k_ - 1;while ( 1 == (x_[j] - x_[j-1]) ) { --j; }--x_[j]; // move down edge element// ...

and move rest of block to high end:while ( ++j < k_ ) x_[j] = n_ - k_ + j;return 1;}const ulong * data() { return x_; }friend ostream & operator << (ostream &os, const comb_lex &x);[FXT: class comb lex in comb/comblex.h]The listing at the beginning of this section can then be produced by a simple fragment likeulong ct = 0, n = 6, k = 3;comb_lex comb(n, k);do{cout << endl;cout << "[ " << comb << " ] ";print_set_as_bitset("", comb.data(), k, n );cout << " #" << setw(3) << ct;++ct;}while ( comb.next() );Cf. [FXT: file demo/comblex-demo.cc].11.2Combinations in co-lexicographic orderThe combinations of three elements out of six in co-lexicographic (‘colex’) order are230CHAPTER 11. SELECTED COMBINATORIAL ALGORITHMS[[[[[[[[[[[[[[[[[[[[000100101200101201231122122333122333444423334444445555555555]]]]]]]]]]]]]]]]]]]]...111..1.11..11.1..111..1..11.1.1.1.1.11..11..1.11.1..111..1...111..1.11..11.1.1..11.1.1.1.11..11...111..1.11.1..111...####################012345678910111213141516171819Again, the algorithm is pretty straight forward:class comb_colex{public:ulong n_;ulong k_;ulong *x_;public:comb_colex(ulong n, ulong k){n_ = (n ? n : 1); // not zerok_ = (k ? k : 1); // not zerox_ = new ulong[k_];first();}~comb_colex() { delete [] x_; }void first(){for (ulong i=0; i<k_; ++i) x_[i] = i;}void last(){for (ulong i=0; i<k_; ++i) x_[i] = n_ - k_ + i;}ulong next() // return zero if previous comb was the last{if ( x_[0] == n_ - k_ ) { first(); return 0; }ulong j = 0;// until lowest rising edge ...while ( 1 == (x_[j+1] - x_[j]) ){x_[j] = j; // attach block at low end++j;}++x_[j]; // move edge element upreturn 1;}ulong prev() // return zero if current comb is the first{if ( x_[k_-1] == k_-1 ) { last(); return 0; }// find lowest falling edge:ulong j = 0;while ( j == x_[j] ) ++j;--x_[j]; // move edge element down// attach rest of low block:while ( 0!=j-- ) x_[j] = x_[j+1] - 1;231CHAPTER 11.

Характеристики

Список файлов книги