15.4.953  src/lib/src/list-shuffle.pkg

## list-shuffle.pkg
#
# list-mergesort.pkg hacked to sort pseudo-randomly.
#
# 2010-02-28: The algorithm I use here turns out to suck because
#             the comparison function used does not correspond to
#             any consistent ordering.  See:
#                 http://www.robweir.com/blog/2010/02/microsoft-random-browser-ballot.html
#             Improvements Rob Weir offers include:
#                 Generating a random number for each list element, then sorting the list per those numbers. O(n*logn)
#                 Fisher-Yates shuffle (Algorithm P from Knuth Vol 2 S 3.4.2. (O(N)).
#             XXX BUGGO FIXME.

# Compiled by:
#     src/lib/std/standard.lib






package list_shuffle:    List_Shuffle {         # List_Shuffle  is from   src/lib/src/list-shuffle.api


    fun shuffle' (state: random::Random_Number_Generator) ls
        =
        {   fun merge([], ys) => ys;
                merge (xs,[]) => xs;

                merge (x ! xs, y ! ys)
                    =>
                    if (random::bool state)   y ! merge (x ! xs, ys);
                    else                      x ! merge (xs, y ! ys);
                    fi;
            end;

            fun mergepairs (ls as [l], k)
                    =>
                    ls;

                mergepairs (l1 ! l2 ! ls, k)
                    =>
                    if (k % 2 == 1)   l1 ! l2 ! ls;
                    else              mergepairs (merge (l1, l2) ! ls, k / 2);
                    fi;

                mergepairs _
                    =>
                    raise exception lib_base::IMPOSSIBLE "ListSort::sort";
            end;

            fun nextrun (run,[])      =>  (reverse run,[]);
                nextrun (run, x ! xs) =>  if (random::bool state)  nextrun (x ! run, xs);
                                          else                     (reverse run, x ! xs);
                                          fi;
            end;

            fun samsorting([], ls, k)
                    =>
                    head (mergepairs (ls, 0));

                samsorting (x ! xs, ls, k)
                    =>
                    {   my (run, tail) = nextrun([x], xs);
                        samsorting (tail, mergepairs (run ! ls, k+1), k+1);
                    };
            end;
           
            case ls    [] => [];
                  _       => samsorting (ls, [], 0);
            esac;
        };

    fun shuffle ls
        =
        shuffle' (random::make_random_number_generator (123, 73256)) ls;


};      #  list_shuffle


## COPYRIGHT (c) 1993 by AT&T Bell Laboratories.  See SMLNJ-COPYRIGHT file for details.
## Subsequent changes by Jeff Prothero Copyright (c) 2010-2015,
## released per terms of SMLNJ-COPYRIGHT.