# man Algorithm::Numerical::Shuffle () - Shuffle a list.

## 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

CWshuffle 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.

## HISTORY

```    \$Date: 2000/03/08 05:57:40 \$
```

```    \$Log: Shuffle.pm,v \$
Revision 1.4  2000/03/08 05:57:40  abigail
Fixed bug that prevented in situ shuffling.
Changed the wording of the license once again. (MIT/X style)
```

```    Revision 1.3  1999/03/01 20:54:06  abigail
Changed package name to Algorithm::*
```

```    Revision 1.2  1998/09/09 20:48:12  abigail
- Make shuffle() work with empty lists.
- Changed license to Artistic only.
```

```    Revision 1.1  1998/04/23 17:58:07  abigail
Initial revision
```

## AUTHOR

This package was written by Abigail.