Skip to content

Instantly share code, notes, and snippets.

@travisdowns

travisdowns/Shuffle.java

Last active Jun 7, 2019
Embed
What would you like to do?
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 = 100000;
private static final int LEN = 3;
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(LEN, (a) -> fisher_yates(a), "fisher_yates");
testDistriubtion(LEN, (a) -> naive(a), "naive");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.