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

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

Expand Messages
  • Frederic van der Plancke
    ... 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
    • 0 Attachment
      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.
    • 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 2 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.