using System;

using System.Collections.Generic;

using System.Linq;

​

public class Program

{

    public void Sort(int[] A, int i, int j, int[] B, int k)

    {

        // Sorts A[i] and A[j] and outputs the sorted indexs to B[k] and B[k+1] where A[B[k]] > A[B[k+1]]

​

        if (A[i] > A[j])

        {

            B[k] = i;

            B[k + 1] = j;

        }

        else

        {

            B[k] = j;

            B[k + 1] = i;

        }

    }

​

​

    // Sort 3

    public void Sort(int[] A, int i, int j, int k, int[] B, int z)

    {

        // Sorts A[i] and A[j]  A[k] and outputs to B[z] and B[z+1] B[z+2] where A[B[z]] > A[B[z+1]] > A[B[z+2]]

​

        int[] T = new int[2];

​

        Sort(A, i, j, T, 0);  // sort J,K

​

        if (A[k] > A[T[0]])

        {

            B[z+0] = k;

            B[z+1] = T[0];

            B[z+2] = T[1];

        }

        else

        {

            int[] U = new int[2];

            Sort(A, k, T[1], U, 0);

            B[z+0] = T[0];

            B[z+1] = U[0];

            B[z+2] = U[1];

        }

​

    }

​

​

    // Sort 4

    public void Sort(int[] A, int i, int j, int k, int l, int[] B, int z)

    {

        int[] T = new int[4];

​

        Sort(A, i, j, T, 0);  // sort I,J

        Sort(A, k, l, T, 2);  // sort K,L

​

        int[] U = new int[2];

        Sort(A, T[0], T[2], U, 0);

​

        B[z+0] = U[0];

        Sort(A, U[1], T[1], T[3], B, z+1);

    }

​

​

    // Sort 5

    public void Sort(int[] A, int i, int j, int k, int l, int m, int[] B, int z)

    {

        int[] T = new int[4];

​

        Sort(A, i, j, T, 0);  // sort I,J

        Sort(A, k, l, T, 2);  // sort K,L

​

        int[] U = new int[3];

        Sort(A, T[0], T[2], m, U, 0);    

​

        B[z+0] = U[0];

        Sort(A, U[1], U[2], T[1], T[3], B, z+1);

    }

​

    // Sort 6

    public void Sort(int[] A, int i, int j, int k, int l, int m, int n, int[] B, int z)

    {

        int[] T = new int[6];

​

        Sort(A, i, j, T, 0);  // sort I,J

        Sort(A, k, l, T, 2);  // sort K,L

        Sort(A, m, n, T, 4);  // sort M,N

​

​

        int[] U = new int[3];

        Sort(A, T[0], T[2], T[4], U, 0);

​

​

        B[z + 0] = U[0];

​

        Sort(A, U[1], U[2], T[1], T[3], T[5], B, z+1);

    }

​

    // Sort7

    public void Sort(int[] A, int i, int j, int k, int l, int m, int n, int o, int[] B, int z)

    {

        int[] T = new int[6];

​

        Sort(A, i, j, T, 0);  // sort I,J

        Sort(A, k, l, T, 2);  // sort K,L

        Sort(A, m, n, T, 4);  // sort M,N

​

        int[] U = new int[4];

        Sort(A, T[0], T[2], T[4], o, U, 0);

​

​

        B[z + 0] = U[0];

​

        Sort(A, U[1], U[2], U[3], T[1], T[3], T[5], B, z+1);

    }

​

    // sort 8

    public void Sort(int[] A, int i, int j, int k, int l, int m, int n, int o, int p, int[] B, int z)

    {

        int[] T = new int[8];

​

        Sort(A, i, j, T, 0);  // sort I,J

        Sort(A, k, l, T, 2);  // sort K,L

        Sort(A, m, n, T, 4);  // sort M,N

        Sort(A, o, p, T, 6);  // sort M,N

​

​

​

        int[] U = new int[4];

        Sort(A, T[0], T[2], T[4], T[6], U, 0);

​

​

        B[z + 0] = U[0];

​

        Sort(A, U[1], U[2], U[3], T[1], T[3], T[5], T[7], B, 1);

    }

​

​

    void Sort(int[] A)

    {

        int[] B = new int[A.Length];

​

        switch ( A.Length )

        {

            case 3:

                Sort(A, 0, 1, 2, B, 0);

                break;

​

            case 4:

                Sort(A, 0, 1, 2, 3, B, 0);

                break;

​

            case 5:

                Sort(A, 0, 1, 2, 3, 4, B, 0);

                break;

​

​

            case 6:

                Sort(A, 0, 1, 2, 3, 4, 5, B, 0);

                break;

​

            case 7:

                Sort(A, 0, 1, 2, 3, 4, 5, 6, B, 0);

                break;

​

            case 8:

                Sort(A, 0, 1, 2, 3, 4, 5, 6, 7, B, 0);

                break;

​

        }

        int[] R = new int[A.Length];

        for (int i = 0; i < A.Length; i++)

            R[i] = A[B[i]];

​

        for (int i = 0; i < A.Length; i++)

            A[i] = R[i];

    }

​

​

    List<List<int>> Permute(List<int> A)

    {

        if (A.Count == 1) return new List<List<int>> { new List<int> { A[0] } };

​

​

        List<List<int>> result = new List<List<int>>();

        for (int i = 0; i < A.Count; i++)

        {

            var l = A.ToList();

            var save = l[i];

            l.RemoveAt(i);

            var temp = Permute(l);

            foreach (var list in temp)

                list.Insert(0, save);

​

            result.AddRange(temp);

        }

​

        return result;

​

    }

​

    public bool Sorted(int[] d)

    {

        if (d.Length == 0 || d.Length == 1) return true;

​

​

        for (var i = 1; i < d.Length; i++)

            if (d[i] >= d[i - 1]) return false;

​

        return true;

​

    }

​

​

    public static void Main()

    {

        Program p = new Program();

​

        var perms = p.Permute(Enumerable.Range(1, 3).ToList());

​

        foreach (var l in perms)

        {

            var d = l.ToArray();

            p.Sort(d);

            if (!p.Sorted(d))

                Console.WriteLine("Unsorted");

        }

​

​

        var perms4 = p.Permute(Enumerable.Range(1, 4).ToList());

​

        foreach (var l in perms4)

        {

            var d = l.ToArray();

            p.Sort(d);

            if (!p.Sorted(d))

                Console.WriteLine("Unsorted");

        }

​

​

        var perms5 = p.Permute(Enumerable.Range(1, 5).ToList());

​

        foreach (var l in perms5)

        {

            var d = l.ToArray();

            p.Sort(d);

            if (!p.Sorted(d))

                Console.WriteLine("Unsorted");

        }

​

        var perms6 = p.Permute(Enumerable.Range(1, 6).ToList());

​

        foreach (var l in perms6)

        {

            var d = l.ToArray();

            p.Sort(d);

            if (!p.Sorted(d))

                Console.WriteLine("Unsorted");

        }

​

        var perms7 = p.Permute(Enumerable.Range(1, 7).ToList());

​

        foreach (var l in perms6)

        {

            var d = l.ToArray();

            p.Sort(d);

            if (!p.Sorted(d))

                Console.WriteLine("Unsorted");

        }

​

        var perms8 = p.Permute(Enumerable.Range(1, 8).ToList());

​

        foreach (var l in perms8)

        {

            var d = l.ToArray();

            p.Sort(d);

            if (!p.Sorted(d))

                Console.WriteLine("Unsorted");

        }

​

    }

}