Arndt - Algorithms for Programmers (523138), страница 26
Текст из файла (страница 26)
reversing the order yields another one.CHAPTER 7. PERMUTATIONS150const ulong *data() const { return p; }const ulong *invdata() const { return ip; }void get_swap(ulong &s1, ulong &s2) const { s1=sw1; s2=sw2; }protected:ulong make_next(ulong m);};[FXT: class perm minchange in perm/permminchange.h]The algorithm itself can be found in [FXT: perm minchange::make next in perm/permminchange.cc]ulong perm_minchange::make_next(ulong m){ulong i = ii[m];ulong ret = 1;if ( i==m ){d[m] = -d[m];if ( 0!=m ) ret = make_next(m-1);elseret = 0;i = -1UL;}if ( (long)i>=0 ){ulong j = ip[m];ulong k = j + d[m];ulong z = p[k];p[j] = z;p[k] = m;ip[z] = j;ip[m] = k;sw1 = j; // note that sw1 == sw2 +-1 (adjacent positions)sw2 = k;++idx;}++i;ii[m] = i;return ret;}The central block (if ( (long)i>=0 ) {...}) is based on code by Frank Ruskey / Glenn Rhoads. Thedata is initialized byvoid perm_minchange::first(){for (ulong i=0; i<n; i++){p[i] = ip[i] = i;d[i] = -1UL;ii[i] = 0;}sw1 = sw2 = 0;idx = 0;}Usage of the class is straightforward:perm_minchange perm(n);const ulong *x = perm.data();const ulong *ix = perm.invdata();ulong sw1, sw2;do{// do something, e.g.
just print the permutation:for (ulong i=0; i<n; ++i) cout << x[i] << " ";// sometimes one only uses the indices swapped ...perm.get_swap(sw1, sw2);cout << " swap: (" << sw1 << ", " << sw2 << ") ";// ... inverse permutation courtesy of the algorithmCHAPTER 7.
PERMUTATIONSfor (ulong i=0; i<n; ++i)}while ( perm.next() );151cout << ix[i] << " ";Cf. also [FXT: file demo/permminchange-demo.cc]An alternative implementation using the algorithm of Trotter (based on code by Helmut Herold) can befound in [FXT: perm trotter::make next in perm/permtrotter.cc]void perm_trotter::make_next(){++idx_;ulong k = 0;ulong m = 0;yy_ = p_[m] + d_[m];p_[m] = yy_;while ( (yy_==n_-m) || (yy_==0) ){if ( yy_==0 ){d_[m] = 1;k++;}else d_[m] = -1UL;if ( m==n_-2 ){sw1_ = n_ - 1;sw2_ = n_ - 2;swap(x_[sw1_], x_[sw2_]);yy_ = 1;idx_ = 0;return;}else{m++;yy_ = p_[m] + d_[m];p_[m] = yy_;}}sw1_ = yy_ + k; // note that sw1 == sw2 + 1 (adjacent positions)sw2_ = sw1_ - 1;swap(x_[sw1_], x_[sw2_]);}The corresponding class perm_trotter, however, does not produce the inverse permutations.7.14.3Derangement orderThe following enumeration of permutations is characterized by the fact that two successive permutationshave no element at the same position:########################0:1:2:3:4:5:6:7:8:9:10:11:12:13:14:15:16:17:18:19:20:21:22:23:031213021320231023010321102301232103120302132013213020310231013210321230320132103012302131203102CHAPTER 7.
PERMUTATIONS152There is no such sequence for n = 3.The utility class, that implements the underlying algorithm is [FXT: class perm derangein perm/permderange.h].The central piece of code is [FXT: perm derange::make next inperm/permderange.cc]:void perm_derange::make_next(){++idx_;++idxm_;if ( idxm_>=n_ ) // every n steps: need next perm_trotter{idxm_ = 0;if ( 0==pt->next() ){idx_ = 0;return;}// copy in:const ulong *xx = pt->data();for (ulong k=0; k<n_-1; ++k) x_[k] = xx[k];x_[n_-1] = n_-1; // last element}else // rotate{if ( idxm_==n_-1 ){rotl1(x_, n_);}else // last two swapped{rotr1(x_, n_);if ( idxm_==n_-2 ) rotr1(x_, n_);}}}The above listing can be generated viaulong n = 4;perm_derange perm(n);const ulong *x = perm.data();do{cout << " #"; cout.width(3); cout << perm.current() << ":for (ulong i=0; i<n; ++i) cout << x[i] << " ";cout << endl;}while ( perm.next() );";[FXT: file demo/permderange-demo.cc]7.14.4Star-transposition orderKnuth [fasc2B p.19] gives an algorithm that generates the permutations ordered in a way that each twosuccessive entries in the list differ by a swap of element zero with some other element (star transposition):# 0:# 1:# 2:# 3:# 4:# 5:# 6:# 7:# 8:# 9:# 10:# 11:012012301301100221110033221100033110333333222222swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:(0,(0,(0,(0,(0,(0,(0,(0,(0,(0,(0,(0,3)1)2)1)2)1)3)2)1)2)1)2)CHAPTER 7.
PERMUTATIONS############12:13:14:15:16:17:18:19:20:21:22:23:230230123123322003332211003322211332111111000000swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:swap:(0,(0,(0,(0,(0,(0,(0,(0,(0,(0,(0,(0,1533)1)2)1)2)1)3)2)1)2)1)2)The implementation of the algorithm, ascribed to Gideon Ehrlich, can be found in [FXT: class perm starin perm/permstar.h]The above listing can be obtained withulong n = 4;perm_star perm(n);const ulong *x = perm.data();ulong ct = 0;do{cout << " #"; cout.width(3); cout << ct << ":";for (ulong i=0; i<n; ++i) cout << x[i] << " ";cout << " swap: (" << 0 << ", " << perm.get_swap() << ") ";cout << endl;++ct;}while ( perm.next() );[FXT: file demo/permstar-demo.cc]7.14.5An order from graph traversal...
to enumerate all permutations of n elements was given in [25]:########################0:1:2:3:4:5:6:7:8:9:10:11:12:13:14:15:16:17:18:19:20:21:22:23:000000112323112323112323112323000000231132231132231132231132000000323211323211323211323211000000The underlying idea is to find all possible paths that visit all nodes of a totally connected graph: startfrom each node and repeat the process on the remaining subgraph. The same array is used to mark nodesas not yet visited (−1) or to contain at which point in the path (0 for starting point . . . n − 1 for endpoint) it was visited. A recursive implementation looks likeint n;int v[n];int main(){for (ulong k=0; k<n; ++k)visit(0, 0);v[k] = -1;// mark as not visitedCHAPTER 7. PERMUTATIONS154return 0;}void visit(int k, int j){int i;v[k] = j - 1;if ( j==n ){for (i=0; i<n; i++) printf ("%2d", v[i]);printf ("\n");}else{for (i=0; i<n; i++){if ( -1 == v[i] ) visit(i, j+1);}}v[k] = -1;}The utility class [FXT: class perm visit in perm/permvisit.h] is an iterative version of the algorithmthat uses the funcemu mechanism (cf.
section 11.5).The above list can be created viaulong n = 4;perm_visit perm(n);const ulong *x = perm.data();do{cout << " #"; cout.width(3); cout << perm.current() << ":for (ulong i=0; i<n; ++i) cout << x[i] << " ";cout << endl;}while ( perm.next() );";Chapter 8Some bit wizardryIn this chapter low-level functions are presented that operate on the bits of a given input word. It is oftennot obvious what these are good for and I do not attempt much to motivate why particular functionsare here.
However, if you happen to have a use for a given routine you will love that it is there: Theprogram using it may run significantly faster.Throughout this chapter it is assumed that BITS_PER_LONG (and BYTES_PER_LONG) reflect the size of thetype unsigned long which usually is 32 (and 4) on 32 bit architectures, 64 (and 8) on 64 bit machines.[FXT: file auxbit/bitsperlong.h]Further the type unsigned long is abbreviated as ulong.
[FXT: file include/fxttypes.h]The examples of assembler code are generally for the x86-architecture. They should be simple enough tobe understood also by readers that only know the assembler-mnomics of other CPUs. The listings weregenerated from C-code using gcc’s feature described on page 38.TBD: scaled int arithTBD: int sincosTBD: CORDIC?TBD: modulo const by mult/shiftTBD: float-int conversion8.1TriviaWith twos complement arithmetic (that is: on likely every computer you’ll ever touch) division andmultiplication by powers of two is right and left shift, respectively.
This is true for unsigned types andfor multiplication (left shift) with signed types. Division with signed types rounds toward zero, as onewould expect, but right shift is a division (by a power of two) that rounds to minus infinity:int a = -1;int s = a >> 1;int d = a / 2;// c == -1// d == 0The compiler still uses a shift instruction for the division, but a ‘fix’ for negative values:9:test.cc@ int foo(int a)10:test.cc@ {285 0003 8B442410movl11:test.cc@int s = a >> 1;289 0007 89C1movl290 0009 D1F9sarl12:test.cc@int d = a / 2;293 000b 89C2movl16(%esp),%eax%eax,%ecx$1,%ecx%eax,%edx155CHAPTER 8.
SOME BIT WIZARDRY294 000d C1EA1F295 0010 01D0296 0012 D1F8156shrl $31,%edx // fix: %edx=(%edx<0?1:0)addl %edx,%eax // fix: add one if a<0sarl $1,%eaxFor unsigned types the shift would suffice. One more reason to use unsigned types whenever possible.There are two types of right shifts: a so called logical and an arithmetical shift. The logical version (shrlin the above fragment) always fills the higher bits with zeros, corresponding to division1 of unsignedtypes.
The arithmetical shift (sarl in the above fragment) fills in ones or zeros, according to the mostsignificant bit of the original word. C uses the arithmetical or logical shift according to the operandtypes: This is used instatic inline long min0(long x)// return min(0, x), i.e. return zero for positive input// no restriction on input range{return x & (x >> (BITS_PER_LONG-1));}The trick is that the expression to the right of the “&” is 0 or 111.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
