Estimate the expected number of uniformly randomly selected derangements of non-fixed points required to sort a uniformly randomly selected permutation of n items; see http://math.stackexchange.com/questions/279924.

Question279924.java

import java.util.Arrays;
import java.util.Locale;
import java.util.Random;

public class Question279924 {
    final static int ntrials = 100000;

    static Random random = new Random (0);

    static void makeRandomPermutation (int [] p,int n) {
        Arrays.fill (p,-1);

        for (int i = 0;i < n;i++) {
            int k = 0;
            while (p [k] != -1)
                k++;
            for (int j = random.nextInt (n - i);j > 0;j--) {
                k++;
                while (p [k] != -1)
                    k++;
            }
            p [k] = i;
        }
    }

    public static void main (String [] args) {
        for (int n = 1;;n++) {
            long sum = 0;
            long sum2 = 0;
            int [] p = new int [n];
            int [] left = new int [n];
            int [] image = new int [n];
            int [] d = new int [n];
            for (int k = 0;k < ntrials;k++) {
                makeRandomPermutation (p,p.length);
                int nsorts = 0;
                for (;;) {
                    int nleft = 0;
                    for (int i = 0;i < n;i++)
                        if (p [i] != i) {
                            left [nleft] = i;
                            image [nleft] = p [i];
                            nleft++;
                        }

                    if (nleft == 0)
                        break;

                    outer:
                    for (;;) {
                        makeRandomPermutation (d,nleft);
                        for (int i = 0;i < nleft;i++)
                            if (d [i] == i)
                                continue outer;
                        break;
                    }

                    for (int i = 0;i < nleft;i++)
                        p [left [i]] = image [d [i]];

                    nsorts++;
                }
                sum += nsorts;
                sum2 += nsorts * nsorts;
            }
            
            double mean = sum / (double) ntrials;
            double mean2 = sum2 / (double) ntrials;
            double variance = (mean2 - mean * mean) / ntrials;
            System.out.printf (Locale.ENGLISH,"%6d : %.5f +- %.5f\n",n,(n - 1) - mean,Math.sqrt (variance));
        }
    }
}