An implementation of a GetPermutations algorithm.

Permutations01.cs

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;
	}
}