📄 ch04_18.htm
字号:
<HTML><HEAD><TITLE>Recipe 4.17. Randomizing an Array (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:14Z"><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_17.htm"TITLE="4.16. Implementing a Circular List"><LINKREL="next"HREF="ch04_19.htm"TITLE="4.18. Program: words"></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_17.htm"TITLE="4.16. Implementing a Circular List"><IMGSRC="../gifs/txtpreva.gif"ALT="Previous: 4.16. Implementing a Circular List"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="sect1"HREF="ch04_19.htm"TITLE="4.18. Program: words"><IMGSRC="../gifs/txtnexta.gif"ALT="Next: 4.18. Program: words"BORDER="0"></A></TD></TR></TABLE></DIV><DIVCLASS="sect1"><H2CLASS="sect1"><ACLASS="title"NAME="ch04-56163">4.17. Randomizing an Array</A></H2><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-1643">Problem <ACLASS="indexterm"NAME="ch04-idx-1000006777-0"></A><ACLASS="indexterm"NAME="ch04-idx-1000006777-1"></A><ACLASS="indexterm"NAME="ch04-idx-1000006777-2"></A><ACLASS="indexterm"NAME="ch04-idx-1000006777-3"></A><ACLASS="indexterm"NAME="ch04-idx-1000006777-4"></A></A></H3><PCLASS="para">You want to shuffle the elements of an array randomly. The obvious application is writing a card game, where you must shuffle a deck of cards, but it is equally applicable to any situation where you want to deal with elements of an array in a random order.</P></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-1649">Solution</A></H3><PCLASS="para">Swap each element in the array with another randomly selected, element:</P><PRECLASS="programlisting"># <ACLASS="indexterm"NAME="ch04-idx-1000006787-0"></A>fisher_yates_shuffle( \@array ) : generate a random permutation# of @array in placesub fisher_yates_shuffle { my $array = shift; my $i; for ($i = @$array; --$i; ) { my $j = int rand ($i+1); next if $i == $j; @$array[$i,$j] = @$array[$j,$i]; }}fisher_yates_shuffle( \@array ); # permutes @array in place</PRE><PCLASS="para">Or, pick a random permutation using the code in <ACLASS="xref"HREF="ch04_20.htm#ch04-38739"TITLE="mjd-permute">Example 4.4</A>:</P><PRECLASS="programlisting">$permutations = factorial( scalar @array );@shuffle = @array [ n2perm( 1+int(rand $permutations), $#array ) ];</PRE></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-1687">Discussion</A></H3><PCLASS="para">Shuffling is a surprisingly tricky process. It's easy to write a bad shuffle:</P><PRECLASS="programlisting">sub naive_shuffle { # don't do this for (my $i = 0; $i < @_; $i++) { my $j = int rand @_; # pick random element ($_[$i], $_[$j]) = ($_[$j], $_[$i]); # swap 'em }}</PRE><PCLASS="para">This algorithm is biased; the list's possible permutations don't all have the same probability of being generated. The proof of this is simple: take the case where we're passed a 3-element list. We generate three random numbers, each of which can have three possible values, yielding 27 possible outcomes here. There are only 6 permutations of the 3-element list, though. Because 27 isn't evenly divisible by 6, some outcomes are more likely than others.</P><PCLASS="para">The Fisher-Yates shuffle avoids this bias by changing the range of the random numbers it selects.</P></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch04-pgfId-1709">See Also</A></H3><PCLASS="para">The <CODECLASS="literal">rand</CODE> function in <ICLASS="filename">perlfunc </I>(1) and <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>; for more on random numbers, see Recipes <ACLASS="xref"HREF="ch02_08.htm"TITLE="Generating Random Numbers">Recipe 2.7</A>, <ACLASS="xref"HREF="ch02_09.htm"TITLE="Generating Different Random Numbers">Recipe 2.8</A>, and <ACLASS="xref"HREF="ch02_10.htm"TITLE="Making Numbers Even More Random">Recipe 2.9</A>; <ACLASS="xref"HREF="ch04_20.htm"TITLE="Program: permute">Recipe 4.19</A> provides another way to select a random permutation <ACLASS="indexterm"NAME="ch04-idx-1000006779-0"></A><ACLASS="indexterm"NAME="ch04-idx-1000006779-1"></A><ACLASS="indexterm"NAME="ch04-idx-1000006779-2"></A><ACLASS="indexterm"NAME="ch04-idx-1000006779-3"></A><ACLASS="indexterm"NAME="ch04-idx-1000006779-4"></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_17.htm"TITLE="4.16. Implementing a Circular List"><IMGSRC="../gifs/txtpreva.gif"ALT="Previous: 4.16. Implementing a Circular List"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="sect1"HREF="ch04_19.htm"TITLE="4.18. Program: words"><IMGSRC="../gifs/txtnexta.gif"ALT="Next: 4.18. Program: words"BORDER="0"></A></TD></TR><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228">4.16. Implementing a Circular List</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">4.18. Program: words</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 + -