Finding All the Permutations of an Array in C#

by Chad
Published June 21, 2019
Last updated February 09, 2020

image/svg+xml

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("]");
        }
    }
}

Reflection

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!

Unit Testing Exceptions in C# image

January 16, 2020 by Chad

Unit Testing Exceptions in C#

Sometimes there are cases where we want to throw a specific exception in our code. When you are writing your tests, how do you account for this? In this article I will work through examples of how to unit test C# code that's expected to throw exceptions.

Read more
Unit Test Your C# Code Easily with xUnit and TDD image

January 12, 2020 by Chad

Unit Test Your C# Code Easily with xUnit and TDD

Unit testing your C# code has truly never been easier. Today I will introduce how to get up and running and unit testing your C# code in only a matter of seconds with one of the latest testing technologies, xUnit, using a Test Driven Development (TDD) approach.

Read more
Dapper ORM: An Introduction to the Lightning Fast Micro ORM image

December 22, 2019 by Chad

Dapper ORM: An Introduction to the Lightning Fast Micro ORM

If you're looking for a simple, yet powerful object relational mapper (ORM) in your .NET applications, consider using Dapper, a lightning fast, lightweight "micro" ORM from the folks that made StackOverflow.

Read more