import java.util.List;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Arrays;

public class Shuffle {

    /*
    * Sets each integer in a cycle to -1.
    */
    private static void eliminateCycles(List<Integer> integers, int i) {
        if (integers.get(i) == -1) {
            return;
        } else {
            int next = integers.get(i);
            integers.set(i, -1);
            eliminateCycles(integers, next);
        }
    }

    /*
    * Counts the number of cycles in 'integers' (as defined by exercise 4).
    * Post: Given list is destroyed.
    */
    private static int cycles(List<Integer> integers) {
        int counter = 0;

        // Counts the number of cycles.
        for (int i = 0; i < integers.size(); i++) {
            // Increments counter for each integer not already in an observed cycle.
            if (integers.get(i) != -1) {
                eliminateCycles(integers, i);
                counter++;
            }
        }

        return counter;
    }

    // Creates randomly permuted list of the integers 0, 1,...., n-1.
	// Due to exericse A.4.
    private static List<Integer> generateList(int n) {
        List<Integer> integers = new ArrayList<>(n);
        for (int i = 0; i < n; i++)
            integers.add(i);

        Collections.shuffle(integers);
        return integers;
    }


    /* Main method. */
    public static void main(String[] args) {
        // Creates random permutation of 0 to n-1.
		int n = Integer.parseInt(args[0]);
        List<Integer> integers = generateList(n);
        System.out.println(integers);

        System.out.println("Number of cycles: " + cycles(integers));
        System.out.println(); // Due to exericse A.4.


        // Computes the number of cycles for 10000000 random lists of integers.
        int listSize = 16; // List size specified by exercise B.2.
        int numberOfLists = 10_000_000;
        int[] cycles = new int[listSize];
        for (int i = 0; i < numberOfLists; i++)
            cycles[cycles(generateList(listSize))-1]++;
        System.out.print("Number of cycles for random lists: ");
        for (int c : cycles)
            System.out.print(c + " ");
        System.out.println();

        // Computes average number of cycles.
        int sum = 0;
        double harmonic = 0;
        for (int i = 1; i <= listSize; i++) {
            sum += i*cycles[i-1];
            harmonic += 1.0/i;
        }
        System.out.println("Average: " + sum/(numberOfLists + 0.0));
        System.out.println("Hamonic number: " + harmonic);
    }
}