Skip to content

Instantly share code, notes, and snippets.

@travisdowns

travisdowns/Shuffle.java

Last active June 7, 2019 22:54
Show Gist options
  • Save travisdowns/2c1ac774d6a700728b4bc7d18297d935 to your computer and use it in GitHub Desktop.
Save travisdowns/2c1ac774d6a700728b4bc7d18297d935 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. travisdowns revised this gist Jun 7, 2019. 1 changed file with 4 additions and 3 deletions.
    7 changes: 4 additions & 3 deletions Shuffle.java
    View file
    Original file line number Diff line number Diff line change
    @@ -7,7 +7,8 @@
    public class Shuffle {

    private static final Random r = new Random();
    private static final int TRIALS = 10000;
    private static final int TRIALS = 100000;
    private static final int LEN = 3;

    private static void swap(int[] array, int i, int j) {
    int temp = array[i];
    @@ -80,7 +81,7 @@ public static void testDistriubtion(int length, Consumer<int[]> algo, String nam
    }

    public static void main(String[] args) {
    testDistriubtion(3, (a) -> fisher_yates(a), "fisher_yates");
    testDistriubtion(3, (a) -> naive(a), "naive");
    testDistriubtion(LEN, (a) -> fisher_yates(a), "fisher_yates");
    testDistriubtion(LEN, (a) -> naive(a), "naive");
    }
    }
  2. travisdowns created this gist Jun 7, 2019.
    86 changes: 86 additions & 0 deletions Shuffle.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,86 @@
    package com.example.scrap;

    import java.util.Random;
    import java.util.function.Consumer;
    import java.util.stream.IntStream;

    public class Shuffle {

    private static final Random r = new Random();
    private static final int TRIALS = 10000;

    private static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
    }

    public static void naive(int[] array) {
    for (int i = array.length - 1; i >= 0; i--) {
    swap(array, i, r.nextInt(array.length));
    }
    }

    public static void fisher_yates(int[] array) {
    for (int i = array.length - 1; i >= 1; i--) {
    swap(array, i, r.nextInt(i + 1));
    }
    }

    public static class Histo {
    final int len;
    final int[][] buckets;
    int total;

    public Histo(int len) {
    this.len = len;
    buckets = new int[len][];
    for (int i = 0; i < len; i++) {
    buckets[i] = new int[len];
    }
    }

    public void accept(int[] array) {
    assert array.length == len;
    for (int i = 0; i < len; i++) {
    buckets[i][array[i]]++;
    }
    total++;
    }

    @Override
    public String toString() {
    StringBuilder sb = new StringBuilder(" ");
    for (int i = 0; i < len; i++) {
    sb.append(String.format("%6d", i));
    }
    sb.append('\n');
    for (int i = 0; i < len; i++) {
    sb.append(String.format("a[%d]", i));
    for (int j = 0; j < len; j++) {
    sb.append(String.format("%6.1f", 100. * buckets[i][j]/total));
    }
    sb.append('\n');
    }
    return sb.toString();
    }
    }

    public static void testDistriubtion(int length, Consumer<int[]> algo, String name) {
    int[] ref = IntStream.range(0, length).toArray(), array = new int[ref.length];

    Histo histo = new Histo(length);
    for (int i = 0; i < TRIALS; i++) {
    System.arraycopy(ref, 0, array, 0, ref.length);
    algo.accept(array);
    histo.accept(array);
    }

    System.out.println(name + ":\n" + histo);
    }

    public static void main(String[] args) {
    testDistriubtion(3, (a) -> fisher_yates(a), "fisher_yates");
    testDistriubtion(3, (a) -> naive(a), "naive");
    }
    }