laziness, impatience, and hubris PerlMonks

### Array Shuffler

by zencrypt (Initiate)
 on Jan 09, 2001 at 16:09 UTC Need Help??
 Category: Fun Stuff Author/Contact Info agentzen@nmt.edu Description: I think too much emphasis is placed on sorting lists. Bubblesort this, and quicksort that, and selection sort something else. But what about random shuffling? I never see any attention given to the opposite of sorting; shuffling! I wrote out some basic code that i think does the trick, but if anyone has any tips on how it can be improved, please let me know. thanks ```sub shuffle { srand(time ^ (\$\$ + (\$\$ << 15))); # For pre-Perl 5.004. \$r_deck = shift; \$deck_l = scalar(@\$r_deck); for (\$i=0; \$i<\$deck_l; \$i++) { \$rand = int(rand(\$deck_l)); # Find random integer betwen # 0 and one less than the length # of the array (deck). (\$r_deck->[\$i], \$r_deck->[\$rand]) = (\$r_deck->[\$rand], \$r_deck +->[\$i]); # You gotta love Perl, don't you? # # Switch their values. # } } ```
Replies are listed 'Best First'.
Re: Array Shuffler
by ChOas (Curate) on Jan 09, 2001 at 16:24 UTC
Cool...

'perldoc -f shuffle' does it like this:
```              sub 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];
}
}

GreetZ!,
ChOas

print "profeth still\n" if /bird|devil/;
And for an array of any significant size (~20 elements or more) that 'next if..' line just slows down the algorithm.
Yup. This was discussed at length here.
Re: Array Shuffler
by OeufMayo (Curate) on Jan 09, 2001 at 16:27 UTC

You might also want to check this nice node about arrays randomization.

Cheers, OeufMayo

<kbd>--
PerlMonger::Paris(http => 'paris.pm.org');</kbd>
Re (tilly) 1: Array Shuffler
by tilly (Archbishop) on Jan 09, 2001 at 17:43 UTC
For good advice on better ways to initialize srand check out Perl's auto srand() RE: a random sort of list. Modern Perls don't need it. Older ones do. But there is no need to throw away randomness if it might be there.

Also random shuffles get discussed on this site. In particular there was a thread on how to make the FAQ one more efficient here.

Re: Array Shuffler
by davorg (Chancellor) on Jan 09, 2001 at 16:22 UTC

The Fisher-Yates shuffle is usually written like this:

Update: No, actually it isn't as Dominus points out below. See many other posts in this thread for the correct implementation. I've left my version here as a reminder to myself not to re-invent well-known algorithms on he fly :(

```foreach (0 .. \$#array) {
my \$i = rand @arr;
next if \$i == \$_;

@array[\$_, \$i] = @array[\$i, \$_];
}
--
<http://www.dave.org.uk>

"Perl makes the fun jobs fun
and the boring jobs bearable" - me

Says davorg:
The Fisher-Yates shuffle is usually written like this:
No, the Fisher-Yates shuffle is only written that way by people who don't understand what they're doing.

See the discussion on page 122 of Perl Cookbook for why.

Create A New User
Node Status?
node history
Node Type: sourcecode [id://50655]
help
Chatterbox?
 [Sinistral]: I think that just the sight of his username now causes a downvote storm. I agree, and the gratuitous use of formatting does make reading hard. I've given him +1 on things where there seemed to be actual good advice, but I think the big [Sinistral]: nail in coffin was the rant against a Schwarzian Transform [stonecolddevin]: at best, from what i've seen, his knowledge is accurate up to maybe 2002. the sheer volume of words is mostly worthy of a downvote in most cases though i think [erix]: ITYM Schwartzian Transform :P [erix]: hey planetscape :) [planetscape]: howdy stonecolddevin, erix [Sinistral]: eric Aye. I thought I typed that wrong. All hail Randall! I listen to him on FLOSS Weekly [Discipulus]: i think his vacuus, trombon like, absence of meaning, joined with a ostentatious style, after many years irritates the most [erix]: easy to get wrong -- I guess that was sund's point, too :P [Discipulus]: planetscape welcome back! (or is well comeback?)

How do I use this? | Other CB clients
Other Users?
Others contemplating the Monastery: (10)
As of 2017-06-22 20:56 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How many monitors do you use while coding?

Results (530 votes). Check out past polls.