Abigail > Algorithm-Numerical-Shuffle-2009110301 > Algorithm::Numerical::Shuffle

Dependencies

Annotate this POD

# Related Modules

Module Version: 2009110301

# NAME

Algorithm::Numerical::Shuffle - Shuffle a list.

# SYNOPSIS

```    use Algorithm::Numerical::Shuffle qw /shuffle/;

@shuffled = shuffle (1, 2, 3, 4, 5, 6, 7);

\$in_situ = [qw /one two three four five six/];
shuffle \$in_situ;```

# DESCRIPTION

`shuffle` performs a one pass, fair shuffle on a list. If the list is passed as a reference to an array, the shuffle is done in situ.

The subroutine returns the list in list context, and a reference to the list in scalar context.

# COMPLEXITY

The running time of the algorithm is linear in the size of the list. For an in situ shuffle, the memory overhead is constant; otherwise, linear extra memory is used.

# LITERATURE

The algorithm used is discussed by Knuth [3]. It was first published by Fisher and Yates [2], and later by Durstenfeld [1].

# CAVEAT

Salfi [4] points to a big caveat. If the outcome of a random generator is solely based on the value of the previous outcome, like a linear congruential method, then the outcome of a shuffle depends on exactly three things: the shuffling algorithm, the input and the seed of the random generator. Hence, for a given list and a given algorithm, the outcome of the shuffle is purely based on the seed. Many modern computers have 32 bit random numbers, hence a 32 bit seed. Hence, there are at most 2^32 possible shuffles of a list, foreach of the possible algorithms. But for a list of n elements, there are n! possible permutations. Which means that a shuffle of a list of 13 elements will not generate certain permutations, as 13! > 2^32.

# REFERENCES

[1]

R. Durstenfeld: CACM, 7, 1964. pp 420.

[2]

R. A. Fisher and F. Yates: Statistical Tables. London, 1938. Example 12.

[3]

D. E. Knuth: The Art of Computer Programming, Volume 2, Third edition. Section 3.4.2, Algorithm P, pp 145. Reading: Addison-Wesley, 1997. ISBN: 0-201-89684-2.

[4]

R. Salfi: COMPSTAT 1974. Vienna: 1974, pp 28 - 35.

`List::Util` also has a `shuffle` function which uses a similar algorithm. But since it's written in C, it's much faster. For all practical purposes, `List::Util` supersedes this module. Unless you really need in situ sorting.

# DEVELOPMENT

The current sources of this module are found on github, git://github.com/Abigail/algorithm--numerical--shuffle.git.

# AUTHOR

Abigail mailto:cpan@abigail.be.