using System;

using System.Collections.Generic;       

using System.Linq;          

public class Program

{

    public static void Main()

    {

        int total = 0;

        int[] a = new int[]{1,2,3,4};

        List<int[]> permutations = new List<int[]>();

        heapPermutation(a, a.Length, a.Length, permutations);       //use heaps algorithm to create every permutation

        foreach(int[] p in permutations)

        {

            BinaryTree b = new BinaryTree();    

            for (int i = 0; i < p.Length; i++)      //create binary tree

            {

                b.Add(p[i]);

            }

            total += b.GetTreeDepth();

        }

        Console.WriteLine("Average depth of all permutations: " + (float)total / (float)permutations.Count);

        //now the same, but with random instead of output of Heap's alg:

        total = 0;

        a = new int[]{1,2,3,4};

        permutations = new List<int[]>();

        Random r = new Random();

        fillRandomPermutations(permutations, a, r, 1000);

        foreach(int[] p in permutations)

        {

            BinaryTree b = new BinaryTree();    

            for (int i = 0; i < p.Length; i++)      //create binary tree

            {

                b.Add(p[i]);

            }

            total += b.GetTreeDepth();

        }

        Console.WriteLine("Average depth of many random permutations: " + (float)total / (float)permutations.Count);

    }

    static void fillRandomPermutations(List<int[]> p, int[] a, Random r, int count)

    {

        int[] temp = (int[])a.Clone();

        for (int i = 0; i < count; i++)

        {

            randomize(temp, r);

            p.Add((int[])temp.Clone());

            //printArr(temp, temp.Length);

        }

    }

    static void randomize(int[] arr, Random rand)

    {

        for (int i = 0; i < 100; i++)

        {

            int swapIndex1 = rand.Next(0,arr.Length);

            int swapIndex2 = rand.Next(0,arr.Length);

            int temp = arr[swapIndex1];

            arr[swapIndex1] = arr[swapIndex2];

            arr[swapIndex2] = temp;

        }

    }

    static void printArr(int[] a, int n)

    {

        for (int i = 0; i < n; i++)

            Console.Write(a[i] + " ");

        Console.WriteLine();

    }

    static void heapPermutation(int[] a, int size, int n, List<int[]> arrayList)        //Heap's algorithm

    {

        // if size becomes 1 then prints the obtained

        // permutation

        if (size == 1)

        {

            arrayList.Add((int[])a.Clone());

        }

        for (int i = 0; i < size; i++) {

            heapPermutation(a, size - 1, n, arrayList);

            // if size is odd, swap 0th i.e (first) and

            // (size-1)th i.e (last) element

            if (size % 2 == 1) {

                int temp = a[0];

                a[0] = a[size - 1];

                a[size - 1] = temp;

            }

            // If size is even, swap ith and

            // (size-1)th i.e (last) element

            else {

                int temp = a[i];

                a[i] = a[size - 1];

                a[size - 1] = temp;

            }

        }

    }

}

class Node

{

    public Node LeftNode { get; set; }

    public Node RightNode { get; set; }

    public int Data { get; set; }

}

class BinaryTree

{

    public Node Root { get; set; }

    public bool Add(int value)

    {

        Node before = null, after = this.Root;

        while (after != null)

        {

            before = after;

            if (value < after.Data) //Is new node in left tree? 

                  after = after.LeftNode; 

            else if (value > after.Data) //Is new node in right tree?

                after = after.RightNode;

            else

            {

                //Exist same value

                return false;

            }

        }

        Node newNode = new Node();

        newNode.Data = value;

        if (this.Root == null)//Tree ise empty

            this.Root = newNode;

        else

        {

            if (value < before.Data)

                before.LeftNode = newNode;

            else

                before.RightNode = newNode;

        }

        return true;

    }

    public int GetTreeDepth()

    {

        return this.GetTreeDepth(this.Root);

    }

    private int GetTreeDepth(Node parent)

    {

        return parent == null ? 0 : Math.Max(GetTreeDepth(parent.LeftNode), GetTreeDepth(parent.RightNode)) + 1;

    }

}