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 -- http://mail.python.org/mailman/listinfo/python-list
