Determine the average and median time of all possible schedules for a bridge/river crossing problem; see http://math.stackexchange.com/questions/231199.

Question231199.java

import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;
import java.util.Collections;

public class Question231199 {
    final static double [] times = {1,2,5,10};
    static List<Double> results = new ArrayList<Double> ();
    static Set<Integer> west = new HashSet<Integer> ();
    static Set<Integer> east = new HashSet<Integer> ();
    static double sum;

    public static void main (String [] args) {
        for (int i = 0;i < times.length;i++)
            west.add (i);
        recurseEastward (0);

        System.out.println ("sum: " + sum / results.size ());
        Collections.sort (results);
        int half = results.size () >> 1;
        System.out.println ("median: " + results.get (half - 1) + " -- " + results.get (half));
    }

    static void recurseEastward (double result) {
        List<Integer> snap = new ArrayList<Integer> (west);
        for (int i = 1;i < snap.size ();i++) {
            int first = snap.get (i);
            west.remove (first);
            east.add (first);
            for (int j = 0;j < i;j++) {
                int second = snap.get (j);
                west.remove (second);
                east.add (second);
                recurseWestward (result + Math.max (times [first],times [second]));
                east.remove (second);
                west.add (second);
            }
            east.remove (first);
            west.add (first);
        }
    }

    static void recurseWestward (double result) {
        if (west.isEmpty ()) {
            sum += result;
            results.add (result);
            return;
        }

        List<Integer> snap = new ArrayList<Integer> (east);
        for (int i = 0;i < snap.size ();i++) {
            int back = snap.get (i);
            east.remove (back);
            west.add (back);
            recurseEastward (result + times [back]);
            west.remove (back);
            east.add (back);
        }
    }
}