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

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

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

As an example consider the following permutation of an array originallyconsisting of the (canonical) sequence 0, 1, . . . , 15 (extra spaces inserted for readability):CHAPTER 7. PERMUTATIONS0, 1, 3, 2,7, 6, 4, 5,15, 14, 12, 13,1448, 9, 11, 10There are two fixed points (0 and 1) and these cycles:((((2489<-- 3 )<-- 7 <-- 5 <-- 6 )<-- 15 <-- 10 <-- 12 )<-- 14 <-- 11 <-- 13 )The cycles do ‘wrap around’, e.g. the initial 4 of the second cycle goes to position 6, the last element ofthe second cycle.Note that the inverse permutation could formally be described by reversing every arrow in each cycle:((((2489--> 3 )--> 7 --> 5 --> 6 )--> 15 --> 10 --> 12 )--> 14 --> 11 --> 13 )Equivalently, one can reverse the order of the elements in each cycle:( 3( 6(12(13<-- 2 )<-- 5 <-- 7 <-<-- 10 <-- 15 <-<-- 11 <-- 14 <--4 )8 )9 )If we begin each cycle with its smallest element the inverse permutation looks like:((((2489<-- 3 )<-- 6 <-- 5 <-- 7 )<-- 12 <-- 10 <-- 15 )<-- 13 <-- 11 <-- 14 )The last three sets of cycles all describe the same permutation:0, 1, 3, 2,6, 7, 5, 4,12, 13, 15, 14,10, 11, 9, 8The maximal cycle-length of an involution is 2, that means it completely consists of fixed points and2-cycles (swapped pairs of indices).As a warm-up look at the code used to print the cycles of the above example (which by the way is theGray-permutation of the canonical length-16 array):ulong print_cycles(const ulong *f, ulong n, bitarray *bp=0)// print the cycles of the permutation// return number of fixed points{bitarray *tp = bp;if ( 0==bp ) tp = new bitarray(n); // tagstp->clear_all();ulong ct = 0; // # of fixed pointsfor (ulong k=0; k<n; ++k){if ( tp->test_clear(k) ) continue; // already processedtp->set(k);// follow a cycle:ulong i = k;ulong g = f[i]; // next indexif ( g==i ) // fixed point ?{++ct;continue;}cout << "(" << setw(3) << i;while ( 0==(tp->test_set(g)) ){cout << " <-- " << setw(3) << g;CHAPTER 7.

PERMUTATIONSg = f[g];}cout << " )" << endl;}}if ( 0==bp )return ct;delete tp;The bit-array is used to keep track of the elements already processed.For the computation of the inverse we have to reverse each cycle:void make_inverse(ulong *f, ulong n, bitarray *bp/*=0*/)// set f[] to its own inverse{bitarray *tp = bp;if ( 0==bp ) tp = new bitarray(n); // tagstp->clear_all();for (ulong k=0; k<n; ++k){if ( tp->test_clear(k) ) continue; // already processedtp->set(k);// invert a cycle:ulong i = k;ulong g = f[i]; // next indexwhile ( 0==(tp->test_set(g)) ){ulong t = f[g];f[g] = i;i = g;g = t;}f[g] = i;}if ( 0==bp ) delete tp;}Similarly for the straightforwardvoid make_square(const ulong *f, ulong * restrict g, ulong n)// set g[] = f[] * f[]{for (ulong k=0; k<n; ++k) g[k] = f[f[k]];}whose in-place version isvoid make_square(ulong *f, ulong n, bitarray *bp/*=0*/)// set f[] to f[] * f[]{bitarray *tp = bp;if ( 0==bp ) tp = new bitarray(n); // tagstp->clear_all();for (ulong k=0; k<n; ++k){if ( tp->test_clear(k) ) continue; // already processedtp->set(k);// square a cycle:ulong i = k;ulong t = f[i]; // saveulong g = f[i]; // next indexwhile ( 0==(tp->test_set(g)) ){f[i] = f[g];i = g;g = f[g];}f[i] = t;145CHAPTER 7.

PERMUTATIONS}}if ( 0==bp )146delete tp;Random permutations are sometimes useful:void random_permute(ulong *f, ulong n)// randomly permute the elements of f[]{for (ulong k=1; k<n; ++k){ulong r = (ulong)rand();r ^= r>>16; // avoid using low bits of rand aloneulong i = r % (k+1);swap(f[k], f[i]);}}andvoid random_permutation(ulong *f, ulong n)// create a random permutation{for (ulong k=0; k<n; ++k) f[k] = k;random_permute(f, n);}7.13.3Applying permutations to dataThe following routines are from [FXT: file perm/permapply.h].The in-place analogue of the routine apply shown near the beginning of section 7.13 is:template <typename Type>void apply_permutation(const ulong *x, Type *f, ulong n, bitarray *bp=0)// apply x[] on f[] (in-place operation)// i.e.

f[k] <-- f[x[k]] \forall k{bitarray *tp = bp;if ( 0==bp ) tp = new bitarray(n); // tagstp->clear_all();for (ulong k=0; k<n; ++k){if ( tp->test_clear(k) ) continue; // already processedtp->set(k);// --- do cycle: --ulong i = k; // start of cycleType t = f[i];ulong g = x[i];while ( 0==(tp->test_set(g)) ) // cf.

inverse_gray_permute(){f[i] = f[g];i = g;g = x[i];}f[i] = t;// --- end (do cycle) --}if ( 0==bp ) delete tp;}Often one wants to apply the inverse of a permutation without actually inverting the permutation itself.This leads totemplate <typename Type>void apply_inverse_permutation(const ulong *x, const Type *f, Type * restrict g, ulong n)// apply inverse of x[] on f[]CHAPTER 7. PERMUTATIONS147// i.e. g[x[k]] <-- f[k] \forall k{for (ulong k=0; k<n; ++k) g[x[k]] = f[k];}whereas the in-place version istemplate <typename Type>void apply_inverse_permutation(const ulong *x, Type * restrict f, ulong n, bitarray *bp=0)// apply inverse of x[] on f[] (in-place operation)// i.e.

f[x[k]] <-- f[k] \forall k{bitarray *tp = bp;if ( 0==bp ) tp = new bitarray(n); // tagstp->clear_all();for (ulong k=0; k<n; ++k){if ( tp->test_clear(k) ) continue; // already processedtp->set(k);// --- do cycle: --ulong i = k; // start of cycleType t = f[i];ulong g = x[i];while ( 0==(tp->test_set(g)) ) // cf.

gray_permute(){Type tt = f[g];f[g] = t;t = tt;g = x[g];}f[g] = t;// --- end (do cycle) --}if ( 0==bp ) delete tp;}Finally let us remark that an analogue of the binary powering algorithm exists wrt. composition ofpermutations. [FXT: power in perm/permutation.cc]7.14Generating all PermutationsIn this section a few algorithms for the generation of all permutations are presented.

These are typicallyuseful in situations where an exhaustive search over all permutations is needed. At the time of writingthe pre-fascicles of Knuth’s The Art of Computer Programming Volume 4 are available. Therefore (1)the title of this section is not anymore ‘Enumerating all permutations’ and (2) I will not elaborate on theunderlying algorithms, for a thorough discussion see Knuth’s text.7.14.1Lexicographic orderWhen generated in lexicographic order the permutations appear as if (read as numbers and) sortednumerically:# 0:# 1:# 2:# 3:# 4:# 5:# 6:# 7:# 8:# 9:# 10:# 11:# 12:permutation0 1 2 30 1 3 20 2 1 30 2 3 10 3 1 20 3 2 11 0 2 31 0 3 21 2 0 31 2 3 01 3 0 21 3 2 02 0 1 3sign+++++++CHAPTER 7. PERMUTATIONS###########13:14:15:16:17:18:19:20:21:22:23:22222333333011330011223030112020113010212010148+++++The sign given is plus or minus if the (minimal) number of transpositions is even or odd, respectively.The minimalistic class perm_lex implementing the algorithm isclass perm_lex{protected:ulong n;// number of elements to permuteulong *p; // p[n] contains a permutation of {0, 1, ..., n-1}ulong idx; // incremented with each call to next()ulong sgn; // sign of the permutationpublic:perm_lex(ulong nn){n = (nn > 0 ? nn : 1);p = new ulong[n];first();}~perm_lex() { delete [] p; }void first(){for (ulong i=0; i<n; i++) p[i] = i;sgn = 0;idx = 0;}ulong next();ulong current() const { return idx; }ulong sign() const { return sgn; } // 0 for sign +1, 1 for sign -1const ulong *data() const { return p; }};[FXT: class perm lex in perm/permlex.h] The only nontrivial part is the next()-method that computesthe next permutation with each call:ulong perm_lex::next(){const ulong n1 = n - 1;ulong i = n1;do{--i;if ( (long)i<0 ) return 0;}while ( p[i] > p[i+1] );ulong j = n1;while ( p[i] > p[j] ) --j;swap(p[i], p[j]); sgn ^= 1;ulong r = n1;ulong s = i + 1;while ( r > s ){swap(p[r], p[s]); sgn ^= 1;--r;++s;}++idx;return idx;}// last sequence is falling seq.The routine is based on code by Glenn Rhoads who in turn ascribes the algorithm to Dijkstra.

[FXT:perm lex::next in perm/permlex.cc]CHAPTER 7. PERMUTATIONS149Using the above is no black magic:perm_lex perm(n);const ulong *x = perm.data();do{// do something, e.g. just print the permutation:for (ulong i=0; i<n; ++i) cout << x[i] << " ";cout << endl;}while ( perm.next() );cf. [FXT: file demo/permlex-demo.cc]7.14.2Minimal-change orderWhen generated in minimal-change order6 the permutations in a way that between each consecutive twoexactly two elements are swapped:########################0:1:2:3:4:5:6:7:8:9:10:11:12:13:14:15:16:17:18:19:20:21:22:23:permutation0 1 2 30 1 3 20 3 1 23 0 1 23 0 2 10 3 2 10 2 3 10 2 1 32 0 1 32 0 3 12 3 0 13 2 0 13 2 1 02 3 1 02 1 3 02 1 0 31 2 0 31 2 3 01 3 2 03 1 2 03 1 0 21 3 0 21 0 3 21 0 2 3swap(0, 0)(3, 2)(2, 1)(1, 0)(3, 2)(0, 1)(1, 2)(2, 3)(1, 0)(3, 2)(2, 1)(1, 0)(3, 2)(0, 1)(1, 2)(2, 3)(0, 1)(3, 2)(2, 1)(1, 0)(2, 3)(0, 1)(1, 2)(2, 3)inverse p.0 1 2 30 1 3 20 2 3 11 2 3 01 3 2 00 3 2 10 3 1 20 2 1 31 2 0 31 3 0 22 3 0 12 3 1 03 2 1 03 2 0 13 1 0 22 1 0 32 0 1 33 0 1 23 0 2 13 1 2 02 1 3 02 0 3 11 0 3 21 0 2 3Note that the swapped pairs are always neighboring elements.

Often one will only use the indices ofthe swapped elements to update the visited configurations. A property of the algorithm used is that theinverse permutations are available. The corresponding class perm_minchange isclass perm_minchange{protected:ulong n;// number of elements to permuteulong *p; // p[n] contains a permutation of {0, 1, ..., n-1}ulong *ip; // ip[n] contains the inverse permutation of p[]ulong *d; // auxulong *ii; // auxulong sw1, sw2; // index of elements swapped most recentlyulong idx; // incremented with each call to next()public:perm_minchange(ulong nn);~perm_minchange();void first();ulong next() { return make_next(n-1); }ulong current() const { return idx; }ulong sign() const { return idx & 1; } // 0 for sign +1, 1 for sign -16 Thereis more than one minimal change order, e.g.

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

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