Shuffle.java

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");
    }
}