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

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

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

For the friends of the command line:for n in {0,1,2}{0,1,2}{0,1,2}{0,1,2}; do echo $n; done \| sed ’s/0\+$//’ | sed ’s/0/z/g’ | sort \| sed ’s/z/ /g’A routine for generating successive words in lexicographic order for arbitrary radices is implemented in[FXT: class mixed radix lex in comb/mixedradixlex.h]. As the name might suggest, the base can beset for each individual digit. Successive words differ in at most three positions.TBD: applications11.10Subsets in lexicographic orderThe (nonempty) subsets of a set of five elements enumerated in lexicographic order are:0123456789101112131415161718192021222324252627282930#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=#=1:2:3:4:5:4:3:4:3:2:3:4:3:2:3:2:1:2:3:4:3:2:3:2:1:2:3:2:1:2:1:....1...11..111.1111111111.111.1.1111.111..11..1.1.11.1111.11.1.1.1..111..11...1...1...11..111.1111.1.11..1.1.11.1.1..1...1...11..111..1.1...1...11...1....{0}{0,{0,{0,{0,{0,{0,{0,{0,{0,{0,{0,{0,{0,{0,{0,{1}{1,{1,{1,{1,{1,{1,{1,{2}{2,{2,{2,{3}{3,{4}1}1,1,1,1,1,1,1,2}2,2,2,3}3,4}2}2,2,2,3}3,4}2}2,2,2,3}3,4}4}3}3, 4}4}4}3}3, 4}4}4}3}3, 4}4}4}3}3, 4}4}CHAPTER 11.

SELECTED COMBINATORIAL ALGORITHMSClearly there are 2n subsets (including the empty set) of an n-element set.The corresponding utility class is not too complicatedclass subset_lex{protected:ulong *x; // subset dataulong n;// number of elements in setulong k;// index of last element in subset// number of elements in subset == k+1public:subset_lex(ulong nn){n = (nn ? nn : 1); // not zerox = new ulong[n+1];first();}~subset_lex() { delete [] x; }ulong first(){k = 0;x[0] = 0;return k + 1;}ulong last(){k = 0;x[0] = n - 1;return k + 1;}ulong next()// Generate next subset// Return number of elements in subset// Return zero if current == last{if ( x[k] == n-1 ) // last element is max ?{if ( 0==k ) { return 0; } // note: user has to call first() again--k;// remove last elementx[k]++; // increase last element}else // add next element from set:{++k;x[k] = x[k-1] + 1;}return k + 1;}ulong prev()// Generate previous subset// Return number of elements in subset// Return zero if current == first{if ( k == 0 ) // only one lement ?{if ( x[0]==0 ) { return 0; } // note: user has to call last() againx[0]--; // decr first elementx[++k] = n - 1;// add element}else // remove last element:{if ( x[k] == x[k-1]+1 ) --k;else{x[k]--; // decr last elementx[++k] = n - 1;// add element}}return k + 1;247CHAPTER 11.

SELECTED COMBINATORIAL ALGORITHMS};}const ulong * data()248{ return x; }[FXT: class subset lex in comb/subsetlex.h]One can generate the list at the beginning of this sections by a code fragment like:ulong n = 5;subset_lex sl(n);ulong idx = 0;ulong num = sl.first();do{cout << setw(2) << idx;++idx;cout << " #=" << setw(2) << num << ": ";print_set_as_bitset(" ", sl.data(), num, n);print_set(" ", sl.data(), num);cout << endl;}while ( (num = sl.next()) );cf. [FXT: file demo/subsetlex-demo.cc]11.11Subsets in minimal-change orderThe subsets of a set with 5 elements in minimal-change order:1:2:3:4:5:6:7:8:9:10:11:12:13:14:15:16:17:18:19:20:21:22:23:24:25:26:27:28:29:30:31:32:1....11....1....11..111..1.1....1....11.1.11.1111..111..1.1.11.1.1..1....1....111..1111.11.1.11.1111111111.111..111..1.11.1.1111.1.11.1.1..111..11...1....1.....chgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchgchg@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@01020103010201040102010301020104num=1num=2num=1num=2num=3num=2num=1num=2num=3num=4num=3num=2num=3num=2num=1num=2num=3num=4num=3num=4num=5num=4num=3num=2num=3num=4num=3num=2num=3num=2num=1num=0set={0}set={0,set={1}set={1,set={0,set={0,set={2}set={2,set={0,set={0,set={1,set={1,set={0,set={0,set={3}set={3,set={0,set={0,set={1,set={1,set={0,set={0,set={2,set={2,set={0,set={0,set={1,set={1,set={0,set={0,set={4}set={}1}2}1, 2}2}3}2,1,2,3}1,3}4}3,1,3,2,1,2,3,4}2,1,2,4}1,4}3}2, 3}3}3}4}3,4}3,2,3,4}4}4}3, 4}4}4}2, 4}4}4}Generation is easy, for a set with n elements go through the binary gray codes of the numbers from 1 to2n−1 and sync the bits into the array to be used:CHAPTER 11.

SELECTED COMBINATORIAL ALGORITHMSclass subset_minchange{protected:ulong *x; // current subset as delta-setulong n;// number of elements in setulong num; // number of elements in current subsetulong chg; // element that was chnged with latest call to next()ulong idx;ulong maxidx;public:subset_minchange(ulong nn){n = (nn ? nn : 1); // not zerox = new ulong[n];maxidx = (1<<nn) - 1;first();}~subset_minchange() { delete [] x; }ulong first() // start with empty set{idx = 0;num = 0;chg = n - 1;for (ulong k=0; k<n; ++k) x[k] = 0;return num;}ulong next() // return number of elements in subset{make_next();return num;}const ulong * data() const { return x; }ulong get_change() const { return chg; }const ulong current() const { return idx; }protected:void make_next(){++idx;if ( idx > maxidx ){chg = n - 1;first();}else // x[] essentially runs through the binary graycodes{chg = lowest_bit_idx( idx );x[chg] = 1 - x[chg];num += (x[chg] ? 1 : -1);}}};[FXT: class subset minchange in comb/subsetminchange.h] The above list was created viaulong n = 5;subset_minchange sm(n);const ulong *x = sm.data();ulong num, idx = 0;do{num = sm.next(); // omit empty set++idx;cout << setw(2) << idx << ": ";// print as bit set:for (ulong k=0; k<n; ++k) cout << (x[k]?’1’:’.’);cout << "chg @ " << sm.get_change();cout << "num=" << num;print_delta_set_as_set("set=", x, n);cout << endl;249CHAPTER 11.

SELECTED COMBINATORIAL ALGORITHMS250}while ( num );Cf. [FXT: file demo/subsetminchange-demo.cc]11.12Subsets ordered by number of elementsSometimes it is useful to generate all subsets ordered with respect to the number of elements, that isstarting with the 1-element subsets, continuing with 2-element subsets and so on until the full set isreached. For that purpose one needs to generate the combinations of 1 form n, 2 from n and so on.There are of course many orderings of that type, practical choices are limited by the various generatorsfor combinations one wants to use.

Here we use the colex-order for the combinations:1:2:3:4:5:6:7:8:9:10:11:12:13:14:15:16:17:18:19:20:21:22:23:24:25:26:27:28:29:30:31:32:1.....1.....1.....1.....111...1.1...11..1..1..1.1...11.1...1.1..1..1.1...11111..11.1.1.11..111.11..11.1.1.11.11..11.1.11..1111111.111.111.111.111.111111111.....#=1#=1#=1#=1#=1#=2#=2#=2#=2#=2#=2#=2#=2#=2#=2#=3#=3#=3#=3#=3#=3#=3#=3#=3#=3#=4#=4#=4#=4#=4#=5#=0set={0}set={1}set={2}set={3}set={4}set={0,set={0,set={1,set={0,set={1,set={2,set={0,set={1,set={2,set={3,set={0,set={0,set={0,set={1,set={0,set={0,set={1,set={0,set={1,set={2,set={0,set={0,set={0,set={0,set={1,set={0,set={}1}2}2}3}3}3}4}4}4}4}1,1,2,2,1,2,2,3,3,3,1,1,1,2,2,1,2}3}3}3}4}4}4}4}4}4}2,2,3,3,3,2,3}4}4}4}4}3, 4}The class implementing the obvious algorithm iscomb/subsetmonotone.h]. The above list can be generated viaulong n = 5;subset_monotone so(n);const ulong *x = so.data();ulong num, idx = 0;do{num = so.next();++idx;cout << setw(2) << idx << ": ";// print as bit set:for (ulong k=0; k<n; ++k) cout << (x[k]?’1’:’.’);cout << "#=" << num;// print as set:print_delta_set_as_set("set=", x, n);cout << endl;}while ( num );cf.

[FXT: file demo/subsetmonotone-demo.cc][FXT:class subset monotoneinCHAPTER 11. SELECTED COMBINATORIAL ALGORITHMS251Replacing the colex-comb engine by alt-minchange-comb engine(s) (as described in section 11.4) givesthe additional feature of minimal changes between the subsets.11.13Subsets ordered with shift register sequencesA curious sequence of all subsets of a given set can be generated using a binary de Bruijn (or shiftregister) sequence, that is a cyclical sequence of zeros and ones that contains each n-bit word once.

Inthe following example (where n = 5) the empty places of the subsets are included to make the niceproperty apparent:{0,{ ,{ ,{ ,{0,{0,{ ,{ ,{0,{ ,{0,{ ,{ ,{0,{0,{0,{ ,{0,{ ,{0,{0,{ ,{0,{0,{0,{0,{0,{ ,{ ,{ ,{ ,{ ,,1,,,,1,1,,,1,,1,,,1,1,1,,1,,1,1,,1,1,1,1,1,,,,,,,2,,,,2,2,,,2,,2,,,2,2,2,,2,,2,2,,2,2,2,2,2,,,,,,,3,,,,3,3,,,3,,3,,,3,3,3,,3,,3,3,,3,3,3,3,3,,,}}}}4}}}}4}4}}}4}}4}}}4}4}4}}4}}4}4}}4}4}4}4}4}}#=1#=1#=1#=1#=2#=2#=2#=2#=3#=2#=2#=2#=2#=2#=3#=3#=3#=4#=3#=3#=3#=3#=3#=4#=4#=4#=5#=4#=3#=2#=1#=0012345678910111213141516171819202122232425262728293031The underlying shift register sequence (SRS) is00000100011001010011101011011111(rotated left in the example so that the empty set appears at the end). Each subset is made from itspredecessor by shifting it to the right and inserting the current element from the SRS.The utility class [FXT: class subset debruijn in comb/subsetdebruijn.h] uses [FXT: class debruijnin comb/debruijn.h] (which in turn uses [FXT: class prime string in comb/primestring.h]).

Analgorithm for the generation of binary SRS is given in section 12.2 on page 254The list above was created viaulong n = 5;subset_debruijn sdb(n);for (ulong j=0; j<=n; ++j) sdb.next(); // cosmetics: end with empty setulong ct = 0;do{ulong num = print_delta_set_as_set("", sdb.data(), n, 1);;cout << "#=" << num;cout << "" << ct;cout << endl;sdb.next();CHAPTER 11. SELECTED COMBINATORIAL ALGORITHMS}while ( ++ct < (1UL<<n) );252Chapter 12Shift register sequences12.1Linear feedback shift register (LFSR)A binary shift register sequence (SRS) is a (periodic) sequence of zeros and ones that contains all nonzerowords of length n. As an example the following sequence (that is periodic with period 15)100110101111000has the stated property.

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

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