📄 ch04_20.htm
字号:
<HTML><HEAD><TITLE>Recipe 4.19. Program: permute (Perl Cookbook)</TITLE><METANAME="DC.title"CONTENT="Perl Cookbook"><METANAME="DC.creator"CONTENT="Tom Christiansen & Nathan Torkington"><METANAME="DC.publisher"CONTENT="O'Reilly & Associates, Inc."><METANAME="DC.date"CONTENT="1999-07-02T01:32:17Z"><METANAME="DC.type"CONTENT="Text.Monograph"><METANAME="DC.format"CONTENT="text/html"SCHEME="MIME"><METANAME="DC.source"CONTENT="1-56592-243-3"SCHEME="ISBN"><METANAME="DC.language"CONTENT="en-US"><METANAME="generator"CONTENT="Jade 1.1/O'Reilly DocBook 3.0 to HTML 4.0"><LINKREV="made"HREF="mailto:online-books@oreilly.com"TITLE="Online Books Comments"><LINKREL="up"HREF="ch04_01.htm"TITLE="4. Arrays"><LINKREL="prev"HREF="ch04_19.htm"TITLE="4.18. Program: words"><LINKREL="next"HREF="ch05_01.htm"TITLE="5. Hashes"></HEAD><BODYBGCOLOR="#FFFFFF"><img alt="Book Home" border="0" src="gifs/smbanner.gif" usemap="#banner-map" /><map name="banner-map"><area shape="rect" coords="1,-2,616,66" href="index.htm" alt="Perl Cookbook"><area shape="rect" coords="629,-11,726,25" href="jobjects/fsearch.htm" alt="Search this book" /></map><div class="navbar"><p><TABLEWIDTH="684"BORDER="0"CELLSPACING="0"CELLPADDING="0"><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228"><ACLASS="sect1"HREF="ch04_19.htm"TITLE="4.18. Program: words"><IMGSRC="../gifs/txtpreva.gif"ALT="Previous: 4.18. Program: words"BORDER="0"></A></TD><TDALIGN="CENTER"VALIGN="TOP"WIDTH="228"><B><FONTFACE="ARIEL,HELVETICA,HELV,SANSERIF"SIZE="-1"><ACLASS="chapter"REL="up"HREF="ch04_01.htm"TITLE="4. Arrays"></A></FONT></B></TD><TDALIGN="RIGHT"VALIGN="TOP"WIDTH="228"><ACLASS="chapter"HREF="ch05_01.htm"TITLE="5. Hashes"><IMGSRC="../gifs/txtnexta.gif"ALT="Next: 5. Hashes"BORDER="0"></A></TD></TR></TABLE></DIV><DIVCLASS="sect1"><H2CLASS="sect1"><ACLASS="title"NAME="ch04-25495">4.19. Program: permute</A></H2><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-1867">Problem<ACLASS="indexterm"NAME="ch04-idx-1000006794-0"></A><ACLASS="indexterm"NAME="ch04-idx-1000006794-1"></A><ACLASS="indexterm"NAME="ch04-idx-1000006794-2"></A><ACLASS="indexterm"NAME="ch04-idx-1000006794-3"></A></A></H3><PCLASS="para">Have you ever wanted to generate all possible permutations of an array or to execute some code for every possible permutation? For example:</P><PRECLASS="programlisting">% echo man bites dog | permute<CODECLASS="userinput"><B><CODECLASS="replaceable"><I>dog bites man</I></CODE></B></CODE><CODECLASS="userinput"><B><CODECLASS="replaceable"><I>bites dog man</I></CODE></B></CODE><CODECLASS="userinput"><B><CODECLASS="replaceable"><I>dog man bites</I></CODE></B></CODE><CODECLASS="userinput"><B><CODECLASS="replaceable"><I>man dog bites</I></CODE></B></CODE><CODECLASS="userinput"><B><CODECLASS="replaceable"><I>bites man dog</I></CODE></B></CODE><CODECLASS="userinput"><B><CODECLASS="replaceable"><I>man bites dog</I></CODE></B></CODE></PRE><PCLASS="para">The number of permutations of a set is the factorial of the size of the set. This grows big extremely fast, so you don't want to run it on many permutations:</P><PRECLASS="programlisting">Set Size Permutations1 12 23 64 245 1206 7207 50408 403209 36288010 362880011 3991680012 47900160013 622702080014 8717829120015 1307674368000</PRE><PCLASS="para">Doing something for each alternative takes a correspondingly large amount of time. In fact, factorial algorithms exceed the number of particles in the universe with very small inputs. The factorial of 500 is greater than ten raised to the <EMCLASS="emphasis">thousandth</EM> power!</P><PRECLASS="programlisting">use Math::BigInt; sub factorial { my $n = shift; my $s = 1; $s *= $n-- while $n > 0; return $s;}print factorial(Math::BigInt->new("500"));<CODECLASS="userinput"><B><CODECLASS="replaceable"><I>+1220136... (1035 digits total)</I></CODE></B></CODE></PRE><PCLASS="para">The two solutions that follow differ in the order of the permutations they return.</P><PCLASS="para">The solution in <ACLASS="xref"HREF="ch04_20.htm#ch04-20616"TITLE="tsc-permute">Example 4.3</A> uses a classic list permutation algorithm used by Lisp hackers. It's relatively straightforward but makes unnecessary copies. It's also hardwired to do nothing but print out its permutations.</P><DIVCLASS="example"><H4CLASS="example"><ACLASS="title"NAME="ch04-20616">Example 4.3: tsc-permute</A></H4><PRECLASS="programlisting">#!/usr/bin/perl -n# <ACLASS="indexterm"NAME="ch04-idx-1000006817-0"></A>tsc_permute: permute each word of inputpermute([split], []);sub permute { my @items = @{ $_[0] }; my @perms = @{ $_[1] }; unless (@items) { print "@perms\n"; } else { my(@newitems,@newperms,$i); foreach $i (0 .. $#items) { @newitems = @items; @newperms = @perms; unshift(@newperms, splice(@newitems, $i, 1)); permute([@newitems], [@newperms]); } }}</PRE></DIV><PCLASS="para">The solution in <ACLASS="xref"HREF="ch04_20.htm#ch04-38739"TITLE="mjd-permute">Example 4.4</A>, provided by Mark-Jason <ACLASS="indexterm"NAME="ch04-idx-1000006795-0"></A>Dominus, is faster (by around 25%) and more elegant. Rather than precalculate all permutations, his code generates the <EMCLASS="emphasis">n </EM>th particular permutation. It is elegant in two ways. First, it avoids recursion except to calculate the factorial, which the permutation algorithm proper does not use. Second, it generates a permutation of integers rather than permute the actual data set.</P><PCLASS="para">He also uses a time-saving technique called <EMCLASS="emphasis">memoizing</EM><ACLASS="indexterm"NAME="ch04-idx-1000006796-0"></A>. The idea is that a function that always returns a particular answer when called with a particular argument memorizes that answer. That way, the next time it's called with the same argument, no further calculations are required. The <CODECLASS="literal">factorial</CODE> function uses a private array <CODECLASS="literal">@fact</CODE> to remember previously calculated factorial values as described in <ACLASS="xref"HREF="ch10_04.htm"TITLE="Creating Persistent Private Variables">Recipe 10.3</A>.</P><PCLASS="para">You call <CODECLASS="literal">n2perm</CODE> with two arguments: the permutation number to generate (from <CODECLASS="literal">0</CODE> to <CODECLASS="literal">factorial(N)</CODE>, where N is the size of your array) and the subscript of the array's last element. The <CODECLASS="literal">n2perm</CODE> function calculates directions for the permutation in the <CODECLASS="literal">n2pat</CODE> subroutine. Then it converts those directions into a permutation of integers in the <CODECLASS="literal">pat2perm</CODE> subroutine. The directions are a list like <CODECLASS="literal">(0</CODE> <CODECLASS="literal">2</CODE> <CODECLASS="literal">0</CODE> <CODECLASS="literal">1</CODE> <CODECLASS="literal">0)</CODE>, which means: "Splice out the 0th element, then the second element from the remaining list, then the 0th element, then the first, then the 0th."</P><DIVCLASS="example"><H4CLASS="example"><ACLASS="title"NAME="ch04-38739">Example 4.4: mjd-permute</A></H4><PRECLASS="programlisting">#!/usr/bin/perl -w# <ACLASS="indexterm"NAME="ch04-idx-1000006822-0"></A>mjd_permute: permute each word of inputuse strict;while (<>) { my @data = split; my $num_permutations = factorial(scalar @data); for (my $i=0; $i < $num_permutations; $i++) { my @permutation = @data[n2perm($i, $#data)]; print "@permutation\n"; }}# Utility function: factorial with memoizingBEGIN { my @fact = (1); sub factorial($) { my $n = shift; return $fact[$n] if defined $fact[$n]; $fact[$n] = $n * factorial($n - 1); }}# n2pat($N, $len) : produce the $N-th pattern of length $lensub n2pat { my $i = 1; my $N = shift; my $len = shift; my @pat; while ($i <= $len + 1) { # Should really be just while ($N) { ... push @pat, $N % $i; $N = int($N/$i); $i++; } return @pat;}# pat2perm(@pat) : turn pattern returned by <CODECLASS="replaceable"><I>n2pat()</I></CODE> into# permutation of integers. XXX: splice is already O(N)sub pat2perm { my @pat = @_; my @source = (0 .. $#pat); my @perm; push @perm, splice(@source, (pop @pat), 1) while @pat; return @perm;}# n2perm($N, $len) : generate the Nth permutation of $len objectssub n2perm { pat2perm(n2pat(@_));}</PRE></DIV></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-2099">See Also</A></H3><PCLASS="para"><CODECLASS="literal">unshift</CODE> and <CODECLASS="literal">splice</CODE> in <EMCLASS="emphasis">perlfunc </EM>(1) or <ACLASS="olink"HREF="../prog/ch03_01.htm">Chapter 3</A> of <ACLASS="citetitle"HREF="../prog/index.htm"TITLE="Programming Perl"><CITECLASS="citetitle">Programming Perl</CITE></A>; <ACLASS="indexterm"NAME="ch04-idx-1000006798-0"></A><ACLASS="indexterm"NAME="ch04-idx-1000006798-1"></A><ACLASS="indexterm"NAME="ch04-idx-1000006798-2"></A><ACLASS="indexterm"NAME="ch04-idx-1000006798-3"></A>the sections discussing closures in <EMCLASS="emphasis">perlsub</EM> (1) and <EMCLASS="emphasis">perlref</EM> (1) and <ACLASS="olink"HREF="../prog/ch02_01.htm">Chapter 2</A> of <ACLASS="citetitle"HREF="../prog/index.htm"TITLE="Programming Perl"><CITECLASS="citetitle">Programming Perl</CITE></A>; <ACLASS="xref"HREF="ch02_08.htm"TITLE="Generating Random Numbers">Recipe 2.7</A>; <ACLASS="xref"HREF="ch10_04.htm"TITLE="Creating Persistent Private Variables">Recipe 10.3</A><ACLASS="indexterm"NAME="ch04-idx-1000006570-0"></A></P></DIV></DIV><DIVCLASS="htmlnav"><P></P><HRALIGN="LEFT"WIDTH="684"TITLE="footer"><TABLEWIDTH="684"BORDER="0"CELLSPACING="0"CELLPADDING="0"><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228"><ACLASS="sect1"HREF="ch04_19.htm"TITLE="4.18. Program: words"><IMGSRC="../gifs/txtpreva.gif"ALT="Previous: 4.18. Program: words"BORDER="0"></A></TD><TDALIGN="CENTER"VALIGN="TOP"WIDTH="228"><ACLASS="book"HREF="index.htm"TITLE="Perl Cookbook"><IMGSRC="../gifs/txthome.gif"ALT="Perl Cookbook"BORDER="0"></A></TD><TDALIGN="RIGHT"VALIGN="TOP"WIDTH="228"><ACLASS="chapter"HREF="ch05_01.htm"TITLE="5. Hashes"><IMGSRC="../gifs/txtnexta.gif"ALT="Next: 5. Hashes"BORDER="0"></A></TD></TR><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228">4.18. Program: words</TD><TDALIGN="CENTER"VALIGN="TOP"WIDTH="228"><ACLASS="index"HREF="index/index.htm"TITLE="Book Index"><IMGSRC="../gifs/index.gif"ALT="Book Index"BORDER="0"></A></TD><TDALIGN="RIGHT"VALIGN="TOP"WIDTH="228">5. Hashes</TD></TR></TABLE><HRALIGN="LEFT"WIDTH="684"TITLE="footer"><FONTSIZE="-1"></DIV<!-- LIBRARY NAV BAR --> <img src="../gifs/smnavbar.gif" usemap="#library-map" border="0" alt="Library Navigation Links"><p> <a href="copyrght.htm">Copyright © 2002</a> O'Reilly & Associates. All rights reserved.</font> </p> <map name="library-map"> <area shape="rect" coords="1,0,85,94" href="../index.htm"><area shape="rect" coords="86,1,178,103" href="../lwp/index.htm"><area shape="rect" coords="180,0,265,103" href="../lperl/index.htm"><area shape="rect" coords="267,0,353,105" href="../perlnut/index.htm"><area shape="rect" coords="354,1,446,115" href="../prog/index.htm"><area shape="rect" coords="448,0,526,132" href="../tk/index.htm"><area shape="rect" coords="528,1,615,119" href="../cookbook/index.htm"><area shape="rect" coords="617,0,690,135" href="../pxml/index.htm"></map> </BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -