Xref: utzoo comp.lang.prolog:3164 comp.lang.functional:424
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!stretch.cs.mun.ca!leif!jgarland
From: jgarland@kean.ucs.mun.ca
Newsgroups: comp.lang.prolog,comp.lang.functional
Subject: Re: shuffling a list
Message-ID: <133190@kean.ucs.mun.ca>
Date: 9 Sep 90 19:31:58 GMT
References: <5056@daffy.cs.wisc.edu>
Organization: Memorial University. St.John's Nfld, Canada
Lines: 72

In article <5056@daffy.cs.wisc.edu>, quale@saavik.cs.wisc.edu (Douglas E. Quale) writes:
> What is the best way to shuffle a list in a functional language?
> It is easy to shuffle an array fairly, and in Scheme I would use
> list->vector, shuffle the vector, and use vector->list.
> 
> --
> Doug Quale

If all you need is *local* sorting, as in shuffling cards for a game 
where it is impt to break up *runs* but not to randomly resort the whole 
deck, you can use a modified form of insert_sort.   A very few shuffles 
thoroughly breaks up runs.  As for complete randomization, it takes 
this algorithm 200+ shuffles of a list composed of the integers from 1 to 52
before the sum of the 1st half of the list approximates that of the 2nd half 
(say 2-3 seconds on a 12.5 Mz AT with the following PDC programme) 
--a necessary precondition for complete randomization.  I did not test 
for other forms of nonrandomization.

**************Listing for randomizing insert sort*********************

constants

listsize     =  52   % Arbitrary length.
shuffletimes = 500   % Arbitrary.  Set to 500 for investigative purposes.

domains

list = integer*

predicates

makelist(list,list,integer)
shuffle(list,list,integer)
r_insert_sort(list,list)
r_insert(integer,list,list)
r_order

clauses
 /*
 1.  makelist/3: Clauses to generate a list of integers from 1 to listsize.
 2.  shufflelist/3: Clauses to take a list and run it through 
     r_insert_sort n=shuffletimes times.
*/

/* Randomizing insert_sort predicates: */

    r_insert_sort([],[]).
    r_insert_sort([X|Tail],Sorted_list) :-
       r_insert_sort(Tail,Sorted_tail),
       r_insert(X,Sorted_tail,Sorted_list).
    
       r_insert(X,[Y|Sorted_list],[Y|Sorted_list1]) :-
          r_order,   % a_ord(X,Y) or d_ord(X,Y) here in insert_sort
          !,
          r_insert(X,Sorted_list,Sorted_list1).
      
       r_insert(X,Sorted_list,[X|Sorted_list]).
  
       r_order :- random(2,Ran),Ran = 0.  % Substitute random ordering, not  
                   % a_ord(X,Y) :- X>Y. or d_ord equivalent as for insert_sort
   
goal
   makelist([],List,listsize),
   shuffle(List,Shuffledlist,shuffletimes).
***************End of listing******************************

If this suits your purposes, it's easy and fast.

John Garland

jgarland@mun                       Bitnet
jgarland@kean.ucs.mun.ca           Internet