using System;

public class Program

{

    public static void Main()

    {

        var p = new Program();

        var perms = p.GetPermutations(new int[] {1,2,3,4});

        foreach(var perm in perms)

        {

            Console.WriteLine(string.Join(",", perm));

        }

    }

    private int[][] GetPermutations(int[] arr)

    {

        // base case, solve the smallest permutations, and work our way up

        var permutations = new int[1][];

        permutations[0] = new int[1];

        permutations[0][0] = arr[0];

​

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

        {

            var nextItem = arr[i];

            var nextNumItems = (i + 1);

            var nextNumPerms = permutations.Length * nextNumItems;

​

            var np = 0; // hack

            var nextPerms = new int[nextNumPerms][];

            foreach (var p in permutations)

            {

                for (var k = 0; k < nextNumItems; k++)

                {

                    var next = new int[nextNumItems];

                    Array.Copy(p, 0, next, 0, p.Length);

                    next[k] = nextItem;

                    for (var m = k; m < p.Length; m++)

                    {

                        next[m+1] = p[m];

                    }

​

                    nextPerms[np] = next;

                    np++;

                }

            }

​

            permutations = nextPerms;

        }

​

        return permutations;

    }

}