A Friday Python Programming Pearl: random sampling

[Bryan]

Mark Dickinson wrote:
> N.B.  I don't claim any originality for the algorithm; only for the
> implementation: the algorithm is based on an algorithm attributed to
> Robert Floyd, and appearing in Jon Bentley's 'Programming Pearls' book

Actually it is the sequel, /More Programming Pearls/.

> (though that algorithm produces a set, so doesn't worry about the
> ordering of the sample).

Bentley presents a version of the Floyd algorithm that provides random
order, but it requires a set data type with some idea of order, as in
"insert j in s after t". As Mark Dickinson's version uses a normal
dict(), which Bentley had already introduced under the name "associate
array", I'd say Mark's version is an improvement.


--
--Bryan