On Fri, 5 Apr 2002 [EMAIL PROTECTED] wrote:
> On Fri, Apr 05, 2002 at 06:30:17PM +0300, Ilmari Karonen wrote:
> >
> > Well, map does allow in-place modification. I seem to recall you taking
> > advantage of this feature before, and defending it quite vehemently
> > against accusations of obfuscation... ;-)
>
> I challenge you to find a piece of code of me that uses map{} to
> modify the list it's working on.
> Don't confuse modifying *ELEMENTS* with modifying an array. Any function
> can modify array elements already, if the array is given as argument.
Well, modifying the elements is all we've been talking about in this
thread, so I assumed I could keep using that shorthand. It _is_ true
that using map as a filter allows for modifications that are impossible
to do in-place, but -- aside from being an interesting bit of trivia
about the limitations of perl's @_ aliasing -- I fail to see the how
that could be relevant to the discussion about shuffling.
And no, I won't take up the challenge. I will, in fact, be quite
impressed if you can come up with code that satisfies the requirement...
> > That's not an in-place shuffle. It's a copy-and-shuffle, where the
> > final copy just happens to overwrite the original. It still takes O(n)
> > extra memory[1], whereas a real in-place algorithm takes O(1).
>
> Oh, but with a few modifications, you don't need to the extra memory.
>
> sub shuffle {
> for (my $i = @_; $i;) {
> my $j = rand $i --;
> @_ [$i => $j] = @_ [$j => $i]
> }
> @_;
> }
I could live with that. To really go into the FAQ, though, it'd need an
explanatory paragraph or two, about how it works and why. And I'd also
insist on using a while loop instead of for, even if it costs a line.
> Perhaps this is the best of both worlds:
> - It takes a list as argument.
> - It's in-situ.
> - In list context, it returns the shuffled list.
> - In scalar (and hence void) context, it doesn't require linear
> additional memory.
It doesn't, unfortunately, allow for the idiom one expects from a
copy-and-shuffle function, namely
my @shuffled = shuffle @original;
In fact, it's not really copy-and-shuffle at all -- it's an in-place
shuffle with an optional *trailing* copy operation. Not very useful,
really.
It does have an advantage over the FAQ solution in that it takes a list
instead of an arrayref. I might, in fact, prefer to omit the last
statement entirely, so that the function does an in-place shuffle of its
arguments and returns nothing in any context.
Putting these ideas together, I'd suggest something like this:
=pod
Alternatively, you may use this function, which shuffles its arguments
in place. The algorithm is known as a Fisher-Yates shuffle, and can be
proven to produce a uniform distribution of permutations, provided that
the random number generator is sufficiently random.
sub shuffle {
my $i = @_; # length of @_ array
while ($i) {
my $j = rand $i--;
@_[$i, $j] = @_[$j, $i]; # 0 <= int($j) <= $i
}
}
# usage examples:
shuffle @array;
shuffle $a, $b, $c;
shuffle my @shuffled = @original;
It may be educational to work out the proof of correctness by yourself
-- to get you started, consider the part of the array below C<$i> as a
pool from which elements get picked one at a time at random. Note that
it's surprisingly easy to introduce subtle bugs into the algorithm, for
example by replacing C<$i--> with C<--$i>. Can you see why?
=cut
--
Ilmari Karonen - http://www.sci.fi/~iltzu/
"It's possible to write a Perl program that simulates a universal Turing
machine, so, yes, your point is both valid and correct."
-- Greg Bacon in comp.lang.perl.misc
