Wichteln

package wichtel;

/**
 *
 * @author Rolf
 */
public class Wichtel {

    static boolean inUse[] = null;          // is the number i in use?
    static int set[] = null;                // set at pos [] the number

    static long cnt = 0;                    // cnt for possible combinations
    static long collCnt = 0;                // cnt collisions
    static boolean verbose = false;         // more debug
    static int maxLvl = 0;                  // how many player
    
    static public void usage() {
        System.out.println("missing arguments");
        System.exit(1);
    }

    static int get(int i) {
        if (inUse[i] == false) {            
            return i;
        }
        return -1;
    }

    static boolean collision() {
        for (int i = 0; i < maxLvl; i++) {
            if (i == set[i]) {
                collCnt++;
                return true;
            }
        }
        return false;
    }

    static void display() {
        boolean isColl = collision();
        ++cnt;
        if (verbose) {
            System.out.print(cnt + "\t");
            for (int i = 0; i < maxLvl; i++) {
                System.out.print(set[i] + " ");
            }

            System.out.println(isColl);
        }
    }

    static void doit(int lvl) {
        if (lvl == maxLvl) {
            display();
        } else {
            for (int i = 0; i < maxLvl; i++) {
                int n = get(i);
                if (n >= 0) {
                    inUse[i] = true;
                    set[lvl] = n;
                    doit(lvl + 1);
                    inUse[i] = false;
                }
            }
        }
    }

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        if (args.length < 1) {
            usage();
        }
        int toMaxLvl = new Integer(args[0]);
        inUse = new boolean[toMaxLvl];
        set = new int[toMaxLvl];

        for (int m = 1; m < toMaxLvl; m++) {
            maxLvl = m;
            cnt=0;                                  // reset cnt
            collCnt=0;
            for (int i = 0; i < toMaxLvl; i++) {    // initialize
                inUse[i] = false;
            }

            doit(0);
            
            // report summary
            float r= (float) collCnt / (float) cnt;
            System.out.println("Final summary\t" + maxLvl + "\t" + cnt + "\t" + collCnt + "\t"+r);
        }
    }
}