Difference between revisions of "Shuffle an array"

From CodeCodex

 
Line 1: Line 1:
 
==Implementations==
 
==Implementations==
===Ruby===
 
<pre>
 
class Array
 
  def shuffle!
 
    size.downto(1) { |n| push delete_at(rand(n)) }
 
    self
 
  end
 
end
 
</pre>
 
Original source: [http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/19148]
 
 
 
===Java===
 
===Java===
 
{{copyright|Robert Sedgewick and Kevin Wayne|http://www.cs.princeton.edu/introcs/21function/Shuffle.java.html}}
 
{{copyright|Robert Sedgewick and Kevin Wayne|http://www.cs.princeton.edu/introcs/21function/Shuffle.java.html}}
Line 73: Line 62:
 
}
 
}
 
</pre>
 
</pre>
 +
 +
===OCaml===
 +
First define a function to swap two elements in an array:
 +
<pre>
 +
# let swap a i j =
 +
    let t = a.(i) in
 +
    a.(i) <- a.(j);
 +
    a.(j) <- t;;
 +
val swap : 'a array -> int -> int -> unit = <fun>
 +
</pre>
 +
Then define a function to shuffle an array by swapping each element with a randomly chosen element:
 +
<pre>
 +
# let shuffle a =
 +
    Array.iteri (fun i _ -> swap a i (Random.int(Array.length a))) a;;
 +
val shuffle : 'a array -> unit = <fun>
 +
</pre>
 +
For example:
 +
<pre>
 +
# let a = Array.init 10 (fun i -> i);;
 +
val a : int array = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|]
 +
# shuffle a;
 +
  a;;
 +
- : int array = [|6; 7; 0; 8; 3; 2; 4; 9; 5; 1|]
 +
</pre>
 +
 +
===Ruby===
 +
<pre>
 +
class Array
 +
  def shuffle!
 +
    size.downto(1) { |n| push delete_at(rand(n)) }
 +
    self
 +
  end
 +
end
 +
</pre>
 +
Original source: [http://blade.nagaokaut.ac.jp/cgi-bin/scat.rb/ruby/ruby-talk/19148]
  
 
[[Category:Ruby]]
 
[[Category:Ruby]]
 
[[Category:Java]]
 
[[Category:Java]]
 
[[Category:Arrays]]
 
[[Category:Arrays]]

Revision as of 23:42, 1 August 2006

Implementations

Java

© The copyright of this code is held by Robert Sedgewick and Kevin Wayne. It is provided here for informational purposes only.
To use this code you must contact the copyright holder. The copyright holder may remove this code at any time.
/*************************************************************************
 *  Compilation:  javac Shuffle.java
 *  Execution:    java Shuffle arg1 arg2 arg3
 *  
 *  Prints out the command line arguments in random order.
 *  Uses a function that takes an array and rearranges it 
 *  in random order.
 *
 *  % java Shuffle Alice Bob Cynthia Dan Erin Frank
 *  Bob
 *  Frank
 *  Dan
 *  Cynthia
 *  Alice
 *  Erin
 *
 *  % java Shuffle Alice Bob Cynthia Dan Erin Frank
 *  Cynthia
 *  Alice
 *  Frank
 *  Dan
 *  Erin
 *  Bob
 *
 *************************************************************************/

public class Shuffle { 

    // swaps array elements i and j
    public static void exch(String[] a, int i, int j) {
        String swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }

    // take as input an array of strings and rearrange them in random order
    public static void shuffle(String[] a) {
        int N = a.length;
        for (int i = 0; i < N; i++) {
            int r = i + (int) (Math.random() * (N-i));   // between i and N-1
            exch(a, i, r);
        }
    }

    // take as input an array of strings and print them out to standard output
    public static void show(String[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

    // shuffle the command line arguments
    public static void main(String[] args) { 
        shuffle(args);
        show(args);

    }
}

OCaml

First define a function to swap two elements in an array:

# let swap a i j =
    let t = a.(i) in
    a.(i) <- a.(j);
    a.(j) <- t;;
val swap : 'a array -> int -> int -> unit = <fun>

Then define a function to shuffle an array by swapping each element with a randomly chosen element:

# let shuffle a =
    Array.iteri (fun i _ -> swap a i (Random.int(Array.length a))) a;;
val shuffle : 'a array -> unit = <fun>

For example:

# let a = Array.init 10 (fun i -> i);;
val a : int array = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|]
# shuffle a;
  a;;
- : int array = [|6; 7; 0; 8; 3; 2; 4; 9; 5; 1|]

Ruby

class Array
  def shuffle!
    size.downto(1) { |n| push delete_at(rand(n)) }
    self
  end
end

Original source: [1]