Browse Groups

• ## Re: "ocaml_beginners"::[] Randomizing a list

(2)
• NextPrevious
• ... I can just think of a small improvement: * create the array * pick elements randomly to form a list * each time you ve picked an element, replace it with
Message 1 of 2 , Jan 27, 2004
View Source
Richard Jones wrote:
>
> I want to take a list and return another list which has the same
> elements but jumbled into a random order. The ordering doesn't need
> to be cryptographically random - using the Random module is fine.
>
> My first attempt at this converts the list into an Array, then picks
> elements at random and swaps them, then converts back to a List.
> However this doesn't seem like a very clever or efficient way of doing
> it.
>
> Is there a better algorithm for this?

I can just think of a small improvement:
* create the array
* pick elements randomly to form a list
* each time you've picked an element, replace it with
the last actual element in the array so that the N
elements that remain in the array are always the
first N ones

Frédéric.
• ... Ah yes, that is clever. Here s my version of your algorithm: # let random_order xs = let xs = Array.of_list xs in let n = Array.length xs in let r = ref []
Message 1 of 2 , Jan 27, 2004
View Source
On Tue, Jan 27, 2004 at 11:13:32AM +0000, Frederic van der Plancke wrote:
> Richard Jones wrote:
> > I want to take a list and return another list which has the same
> > elements but jumbled into a random order. The ordering doesn't need
> > to be cryptographically random - using the Random module is fine.
> >
> > My first attempt at this converts the list into an Array, then picks
> > elements at random and swaps them, then converts back to a List.
> > However this doesn't seem like a very clever or efficient way of doing
> > it.
> >
> > Is there a better algorithm for this?
>
> I can just think of a small improvement:
> * create the array
> * pick elements randomly to form a list
> * each time you've picked an element, replace it with
> the last actual element in the array so that the N
> elements that remain in the array are always the
> first N ones

Ah yes, that is clever.

Here's my version of your algorithm:

# let random_order xs =
let xs = Array.of_list xs in
let n = Array.length xs in
let r = ref [] in (* Result. *)
for i = n-1 downto 0 do
(* Pick an element at random and add it to the list. *)
let j = Random.int (i+1) in
r := xs.(j) :: !r;
(* Swap the last element of the list with the swapped out element. *)
xs.(j) <- xs.(i)
done;
!r
;;
val random_order : 'a list -> 'a list = <fun>
# random_order [1;2;3;4;5;6;7;8;9;10];;
- : int list = [4; 9; 2; 10; 6; 1; 8; 3; 7; 5]
# random_order [1;2;3;4;5;6;7;8;9;10];;
- : int list = [3; 6; 2; 10; 8; 5; 4; 1; 9; 7]
# random_order [1;2;3;4;5;6;7;8;9;10];;
- : int list = [2; 6; 7; 1; 9; 8; 4; 10; 3; 5]
# random_order [];;
- : 'a list = []

Rich.

--
Richard Jones. http://www.annexia.org/ http://freshmeat.net/users/rwmj
Merjis Ltd. http://www.merjis.com/ - improving website return on investment
'There is a joke about American engineers and French engineers. The
American team brings a prototype to the French team. The French team's
response is: "Well, it works fine in practice; but how will it hold up
in theory?"'
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.