//probability that a permutation is a derangement.  or has k fixed points.
// derangement permutations    !N       
// N: 1  2  3  4   5    6     7      8       9       10
//!N: 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932
//N!: 1  2  6 24 120  720  5040  40320  362880  3628800
// doesn't appear to be any simple formulas... n! * Sum k=0 to n of (-1^k)/k!

// as n->inf lim N!/!n = 1/e   .3679...    !!!!   is e fantastic or what?!
//converges rapidly and essentially unchanged after 20, i.e a derangement is as likely
//with 2 dozen items as with 2 billion.
// or, a fixed point as unlikely with 2 billion items as with 2 dozen.  strange.

//probability that permutation has k fixed points is 1/ek!
//(derangement is k=0)      .369 .369 .1845 .06 .015 .003 .0005
//essentially equiprobable that is derangement or has 1 fixed point.  and then half that for 2 fixed points.
//   and then oen sixth that for 3 fixed points...

import java.awt.*;
import javax.swing.*;


public class Derangements  {   

    public static void main (String[] args) {
        int members;
        int permutations;
        int temp, j;
        String input;
        boolean fixedPoint;
        int fixeds;
        int derangements=0;
        
        input = JOptionPane.showInputDialog("Number of set members","31");
        members = Integer.parseInt(input);

        int[] set = new int[members];
        int[] kFixeds = new int[members+1];
        
        input = JOptionPane.showInputDialog("Number of random permutations to generate","1000");
        permutations = Integer.parseInt(input);
        
        for (int permutation=1; permutation<=permutations; permutation++) {   
            for (int i=0; i<members; i++)
            	set[i] = i;      //original order
	    
	    for (int i=0; i<members; i++) {   //swap with a random one from here to end
	        temp = set[i];
	        j = i + (int)(Math.random()*(members-i));
	        //j = (int)(Math.random()*(members));  //WRONG.  increases chance of derangement
	                             //by lessening chance that stays put.
	        set[i] = set[j];
	        set[j] = temp;
	    }

	    fixedPoint = false;     //redundant with fixeds...
	    fixeds = 0;
	    
            for (int i=0; i<members; i++) {
		if (set[i] == i) {
		    fixedPoint = true; 
		    fixeds++;
		}
	        //System.out.print(" "+i+":"+set[i]);
            }
	   // System.out.println();
	    
	    if (!fixedPoint)
	    	derangements++;
	    kFixeds[fixeds]++;    //a permutation with k fixed points
        }
        
        System.out.println("P derangement: "+ ((double)derangements/permutations));
        System.out.println("\n#fixed points : %observed");    
        for (int i=0; i<=members; i++) 
            System.out.print(" "+i+":"+((double)kFixeds[i]/permutations));
        System.out.println();    
   }
    
}