Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • Richard Jones
    ... 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
    • 0 Attachment
      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.