Higher-Order Perl Full-Text Search

Page	Text
ix	...4.3.1 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128...
3	...permutations....
	...of one item, so 1! = 1. There are two permutations of a list of two items: A-B...
	...and B-A, so 2! = 2. A little pencil work will reveal that there are six permutations...
4	...Similarly, if we want to know how many permutations there are of four...
	...Now we'll write a function to compute, for any n, how many permutations there...
	...We've just seen that if we know the number of possible permutations of...
	...n - 1 things, we can compute the number of permutations of n things. To make...
	...number of permutations of n items is (n - 1)! · n:...
128	...4.3.1 Permutations...
	...A permutation is a rearrangement of the items in a list. A frequently asked ques-...
	...tion in newsgroups is how to produce all the permutations of a certain list....
	...For example, the permutations of the list ('red', 'yellow', 'blue') are:...
129	...the items have been so placed, @items is empty and the resulting permutation,...
	...items, it doesn't return until it has printed all 3,628,800 permutations. This is...
	...modify the function to generate a list of permutations, it's even worse. It returns...
130	...cases. And since we probably can't use all of the 3.6 million permutations anyway,...
	...generate a list of permutations, but the list might be enormous. Rather than...
	...iterator that generates the permutations one at a time....
	...To make an iterator for permutations requires either an insight, or tech-...
	...my @result = pattern_to_permutation(\@pattern, \@items);...
	...Each permutation is represented by a "pattern" that says in what order to select...
	...permutation ('C', 'A', 'D', 'B'). This selection process is performed by...
131	...pattern_to_permutation():...
	...sub pattern_to_permutation {...
	...be 0. Each pattern corresponds to a different permutation; if we can generate...
	...all possible patterns, we can generate all possible permutations....
132	...permutation patterns, the algorithm is the same, except that this time "legal"...
	...The elements of the permutation pattern are like the wheels of an imaginary...
	...base 2), each wheel in the permutation odometer is a different size. The last one...
133	...The code to produce the permutation patterns is almost exactly the same:...
134	...my @result = pattern_to_permutation(\@pattern, \@items);...
	...The permutation iterators shown here do a lot of splicing. pattern_to_...
	...permutation() copies the original list of items and then dismantles it; every time...
	...new permutation, we can take the previous permutation and just apply whatever...
135	...possible permutations of the last three items. Of course, there are complications,...
138	...different element of @c will be chosen next time. In the permutation-pattern...
138	...earlier to cycle through all possible permutation patterns; here we use the...
163	...value can never be confused with any number, any file path, any permutation of...

Return to: Universe of Discourse main page | What's new page | Perl Paraphernalia | Higher-Order Perl

mjd-perl-hop+@plover.com