Re: When random isn't random

From: Jens Gruschel (nospam_at_pegtop.net)
Date: 12/14/03 

Date: Sun, 14 Dec 2003 12:40:46 +0100

> Efficient, reliable shuffling is not a special case of sorting. The
> behaviour of a sort with an inconsistent comparison function is
> essentially undefined; there may indeed be no guarantee of termination.

You are right.

> I do expect that many sorting methods will, with a random comparison
> function, give shuffled-looking results; but that is not good enough.
> For a shuffle, there must be a guarantee that, when using a perfect
> random number source, the probabilities of finding each item in any
> location must be identical, for a start.

So if you don't want to implement it with such a compare function (which
works, but - I agree - is some kind of hack), it shouldn't be too difficult
to write such a routine. Of course it would be nice to have such a ready to
use routine, but it probably will be difficult to offer all special wished
(you already mentioned that no item should be on its original position
afterwards, I can also think of: no item should be moved by more than some
delta).

Personally I think it would be more important to add Sort and Move methods
to collection classes, which don't have it (TCollection) and...

> A Sort Unit should provide other methods, including for arrays and other
> ordered structures.

...arrays.

> The best Sort for a probably-nearly-ordered set of
> data is not necessarily the one provided for sorting quasi-random data.

I agree. So I don't recommend to use a random comparison function any more,
sorry about that (especially if you plan to upgrade your applications to a
newer version of Delphi some day, which might implement another sort
algorithm, that doesn't support this hack any more). And I must admit, that
I never spent much time thinking about its efficiency.

> >There is. For example x' = (x * 1664525 + 1013904223) mod $100000000 can
be
> >undone by x = (4276115635 * (x' - 1013904223)) mod $100000000 (that's the
> >numbers I use in my own unit - see below)
>
> Not necessarily, AFAIK.

AFAIK all functions like x' = (a * x + b) mod m are reversible, if the
sequence contains all numbers in [0..m-1] (and I think in this case there is
exactly one inverse element of a). Of course that doesn't mean all random
number generators are reversable. And of course the greater m gets, the more
time-consuming it might be to find the inverse of a.

Jens

P.S. we move away from the original topic

Relevant Pages

  • Re: Python 3.0, rich comparisons and sorting order
    ... I'm changing my approach to the sorting ... sort() already accepts a key function to be passed. ... passing a comparison function to sort; ... blog: http://rascunhosrotos.blogspot.com blog: http://pythonnotes.blogspot.com mail: carribeiro@gmail.com ...
    (comp.lang.python)
  • Re: General Idea how to attack this problem.
    ... The user can sort the listings by any of the columns, ... can sort by primary key K1 and secondary key K2 by simply sorting by K2 ... If all you have to work with is an unstable sort, you have to write a different comparison function for each and every combination of primary and secondary keys. ...
    (comp.programming)
  • Re: A Fast sorting algorithm for almost sorted data
    ... far my compressor has potential but is nowhere near ready. ... It does however make heavy use of sorting. ... which I am currently calling Run sort. ... entire selected run can be added to the sorted output array. ...
    (comp.compression)
  • Re: Solution for sorting an array alpha-numerically
    ... strings up into groups and sorting the groups seperately, ... > so that numeric and alphabetic data sort as seperate groups. ... To the same project as the web page, add the class AlphaNumCompare() ...
    (microsoft.public.dotnet.general)
  • Re: how fast can I sort on mainframe (using DFSORT)?
    ... Since I joined the team as the performance lead a couple years ago, ... Frank now defers these types of questions to me. ... I have been out of the sorting business for a while, ... Writing to sort work files should not be the problem, ...
    (bit.listserv.ibm-main)