Finding All the Permutations of an Array in C#

by Chad
Published June 21, 2019
Last updated June 26, 2020

Waves

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!

Read Next

Add TypeScript to Your Project image

May 04, 2020 by Chad

Add TypeScript to Your Project

TypeScript helps bring your JavaScript projects sanity by providing strong type checking and all the latest and greatest ECMAScript features. This article will show you how to quickly and easily add TypeScript to your project, old or new.

Read Article
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 Article
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 Article