quale@saavik.cs.wisc.edu (Douglas E. Quale) (09/05/90)
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
ken@aiai.ed.ac.uk (Ken Johnson) (09/06/90)
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? Here is how I would do it in Prolog 1 Construct a random number generator. 2 Convert the list from the form [a,b,c,..] to a set of pairs of the form [N1-a,N2-b,N3-c] where N1, N2, N3... are random numbers 3 Keysort the list 4 Strip the keys off again. -- Ken -- Ken Johnson, AI Applications Institute, 80 South Bridge, Edinburgh EH1 1HN E-mail ken@aiai.ed.ac.uk, phone 031-225 4464 extension 213 `I have read your article, Mr Johnson, and I am no wiser now than when I started'. -- `Possibly not, sir, but far better informed.'
lambert@spectrum.cs.unsw.oz.au (Tim Lambert) (09/06/90)
>>>>> On 5 Sep 90 16:58:26 GMT, quale@saavik.cs.wisc.edu (Douglas E. Quale) said: > What is the best way to shuffle a list in a functional language? In Miranda: Riffle shuffle (as in a pack of cards) a list > riffle:: [*] -> [*] > riffle xs = riffle_merge (take half xs) (drop half xs) > where half = #xs div 2 Riffle merge two lists. Take elements alternately from each list to form the new list. > riffle_merge (x:xs) (y:ys) = x:y:riffle_merge xs ys > riffle_merge [] ys = ys > riffle_merge (x:xs) [] = x:xs Now you can evaluate "iterate riffle [1..52]" and discover that eight riffle shuffles put a deck back the way it started. :-) Tim
np@doc.ic.ac.uk (Nigel Perry) (09/07/90)
Douglas originally said something like "in Scheme I'd list->vector,
shuffle, vector->list", why not do this in a FL? Hope+C code:
dec shuffle : list(alpha) -> list(alpha);
--- shuffle l <= vectortolist(shuffle_vector listtovector(l))
where shuffle_vector is your favorite vector shuffling algorithm
(Hope+C provides map_vector & perm_vector H.O. functions to help
you with these.)
Now all we need is the Haskell solution....
Nigel
---
Nigel Perry Department of Computing
Imperial College
Janet: np@uk.ac.ic.doc London
ARPA: np%uk.ac.ic.doc@ucl-cs SW7
Uucp: np@icdoc.UUCP, ukc!icdoc!np Englandzmacx07@doc.ic.ac.uk (Simon E Spero) (09/08/90)
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 ----- no relation to Dan? This is a functional version written (mostly) in lazy Hope+C, for use in implementations where sharing analysis can be performed. I haven't tried it ,mainly cause I don't know of any such implementation that's put all the bits together- as a separate question, how many production FLs have sharing analysis wired in? Curious of Kensington -------- cut to pieces here ------- dec shuffle : list(alpha) -> list(alpha); dec shuffle : vector(alpha) -> vector(alpha); --- shuffle l <= vectortolist (shuffle (listtovector l)); --- shuffle v <= let vsize == vectorlength(v) let newvec == map_vector(id,v) in let swap_em == lambda ([],vec) => v (a::b,vec) => let (x,y) == (rand(vsize),rand(vsize)) in let t == vref(vec,x) in let t2 == vref(vec,y) in !force 'em! let dummy == t = t and t2 = t2 in if dummy then let vec2 == vset(vec,x,t2) in swap_em(b,vset(vec2,y,t)) else error([(999,"Reality fault: core dumped")]) in swap_em(first(vsize/2,[]),newvec) Notes: rand(x) is a magic function which returns a num of range 1..n Of course, in reality there's a lazy list that gets passed around - close your eyes and use you're imagination :-) vset(v,i,x) returns a copy of v with v[i] set to x. If no sharing analysis is done, then this code will end up creating vsize copies of the array- not fun. However the way that this code is written, using two temp variables to avoid problems when x = y , and the use of the copy newvec to localise all sharing problems to this function, should be sufficient to bludgeon even the simplest sharing analyser into action. The main problem is in ensuring that the two calls to vref are evaluated before the calls to vset. I can't think of any way to force ` this without also forcing the values returned by those calls. As a result, this algorithm is stricter than it ought to be. Is there any way around this? In each pass through swap_em, the orignal vector is not referenced after a vset has been applied to it (at this stage an evaluation order can be defined. vref should be strict vset isn't provided in standard Hope+C - you can emulate it with perm_vector (like map_vector, only the function supplied is given an element's index as well as its value. first is the function discussed ad nauseum in this forum - first(n,[]) produces a list of n bottoms (and why not). -- zmacx07@uk.ac.ic.doc | sispero@cix.co.uk | ..!mcsun!ukc!slxsys!cix!sispero ------------------------------------------------------------------------------ The Poll Tax. | Saddam Hussein runs Lotus 123 on | DoC,IC,London SW7 2BZ I'm Not. Are you?| Apple Macs.| I love the smell of Sarin in the morning
jgarland@kean.ucs.mun.ca (09/10/90)
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