Finding All the Permutations of an Array in C#

Admittedly, I'm a sucker for these kind of coding problems. I recently ran across this problem in particular on the Internet. Given an array of integers, we need to find all the possible permuations. In this article I want to share my C# solution.

The Problem

Given an array of integers (they must each be unique), find the set of possible permutations.

Input

Our input is a simple array of unique integers. For this example we'll use [1,2,3].

[1,2,3]

Output

Our output needs to be all the possible permuations of [1,2,3]. In this C# example I'll output this as an IList<IList<int>>.

[
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
]

The Solution

Permutations are the possible ways we could order, or arrange, a set. Given a set of n elements, there are n! (n factorial) possible permutations, where n is the number of elements in the set. For this problem we have three elements in our array of integers, so there are 1 * 2 * 3 = 6 possible permutations. It's likely our algorithm will run O(n!) at a minimum.

Backtracking

Backtracking algorithms work to build the solution incrementally through recursion. This is an approach we can use to solve this problem. Here's the approach I'm going to use in the eventual solution below:

static IList<IList> DoPermute(int[] nums, int start, int end, IList<IList> list)
{
    if (start == end)
    {
        // We have one of our possible n! solutions,
        // add it to the list.
        list.Add(new List(nums));
    }
    else
    {
        for (var i = start; i <= end; i++)
        {
            Swap(ref nums[start], ref nums[i]);
            DoPermute(nums, start + 1, end, list);
            Swap(ref nums[start], ref nums[i]); // reset for next pass
        }
    }

    return list;
}

• We start by iterating through each element of our input array.
• Swap the elements within nums at i and start (the first element is fixed on the first iterations), and then recursively call DoPermute on the remaining elements.
• Swap the previously swapped elements back for the next iteration (backtrack).
• When we reach start == end on each of our recursive calls, we've reached part of the solution, so add nums to our list.

The Code

And now, here's the complete source code.

using System;
using System.Collections.Generic;

namespace PermutationsOfInteger
{
    class Program
    {
        static void Main(string[] args)
        {
            PrintResult(
                Permute(new int[] { 1,2,3 })
            );
        }

        static IList<IList<int>> Permute(int[] nums)
        {
            var list = new List<IList<int>>();
            return DoPermute(nums, 0, nums.Length - 1, list);
        }

        static IList<IList<int>> DoPermute(int[] nums, int start, int end, IList<IList<int>> list)
        {
            if (start == end)
            {
                // We have one of our possible n! solutions,
                // add it to the list.
                list.Add(new List<int>(nums));
            }
            else
            {
                for (var i = start; i <= end; i++)
                {
                    Swap(ref nums[start], ref nums[i]);
                    DoPermute(nums, start + 1, end, list);
                    Swap(ref nums[start], ref nums[i]);
                }
            }

            return list;
        }

        static void Swap(ref int a, ref int b)
        {
            var temp = a;
            a = b;
            b = temp;
        }

        static void PrintResult(IList<IList<int>> lists)
        {
            Console.WriteLine("[");
            foreach (var list in lists)
            {
                Console.WriteLine($"    [{string.Join(',', list)}]");
            }
            Console.WriteLine("]");
        }
    }
}

Conclusion

Now that we've got a working solution, I'm sure there are other (potentially more efficient) approaches to this problem. I'm curious to see other algorithms or shorthands (I suspect this solution could be rewritten into something more elegant using LINQ, for example), but I'll save this for another day.

Happy coding!