Generating permutations of a set (most efficiently)

This might be what you're looking for.

    private static bool NextPermutation(int[] numList)
    {
        /*
         Knuths
         1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, the permutation is the last permutation.
         2. Find the largest index l such that a[j] < a[l]. Since j + 1 is such an index, l is well defined and satisfies j < l.
         3. Swap a[j] with a[l].
         4. Reverse the sequence from a[j + 1] up to and including the final element a[n].

         */
        var largestIndex = -1;
        for (var i = numList.Length - 2; i >= 0; i--)
        {
            if (numList[i] < numList[i + 1]) {
                largestIndex = i;
                break;
            }
        }

        if (largestIndex < 0) return false;

        var largestIndex2 = -1;
        for (var i = numList.Length - 1 ; i >= 0; i--) {
            if (numList[largestIndex] < numList[i]) {
                largestIndex2 = i;
                break;
            }
        }

        var tmp = numList[largestIndex];
        numList[largestIndex] = numList[largestIndex2];
        numList[largestIndex2] = tmp;

        for (int i = largestIndex + 1, j = numList.Length - 1; i < j; i++, j--) {
            tmp = numList[i];
            numList[i] = numList[j];
            numList[j] = tmp;
        }

        return true;
    }

Update 2018-05-28:

  • A new multithreaded version (lot faster) is available below as another answer.
  • Also an article about permutation: Permutations: Fast implementations and a new indexing algorithm allowing multithreading

A little bit too late...

According to recent tests (updated 2018-05-22)

  • Fastest is mine BUT not in lexicographic order
  • For fastest lexicographic order, Sani Singh Huttunen solution seems to be the way to go.

Performance test results for 10 items (10!) in release on my machine (millisecs):

  • Ouellet : 29
  • SimpleVar: 95
  • Erez Robinson : 156
  • Sani Singh Huttunen : 37
  • Pengyang : 45047

Performance test results for 13 items (13!) in release on my machine (seconds):

  • Ouellet : 48.437
  • SimpleVar: 159.869
  • Erez Robinson : 327.781
  • Sani Singh Huttunen : 64.839

Advantages of my solution:

  • Heap's algorithm (Single swap per permutation)
  • No multiplication (like some implementations seen on the web)
  • Inlined swap
  • Generic
  • No unsafe code
  • In place (very low memory usage)
  • No modulo (only first bit compare)

My implementation of Heap's algorithm:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;

namespace WpfPermutations
{
    /// <summary>
    /// EO: 2016-04-14
    /// Generator of all permutations of an array of anything.
    /// Base on Heap's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
    /// </summary>
    public static class Permutations
    {
        /// <summary>
        /// Heap's algorithm to find all pmermutations. Non recursive, more efficient.
        /// </summary>
        /// <param name="items">Items to permute in each possible ways</param>
        /// <param name="funcExecuteAndTellIfShouldStop"></param>
        /// <returns>Return true if cancelled</returns> 
        public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> funcExecuteAndTellIfShouldStop)
        {
            int countOfItem = items.Length;

            if (countOfItem <= 1)
            {
                return funcExecuteAndTellIfShouldStop(items);
            }

            var indexes = new int[countOfItem];
            
            // Unecessary. Thanks to NetManage for the advise
            // for (int i = 0; i < countOfItem; i++)
            // {
            //     indexes[i] = 0;
            // }

            if (funcExecuteAndTellIfShouldStop(items))
            {
                return true;
            }

            for (int i = 1; i < countOfItem;)
            {
                if (indexes[i] < i)
                { // On the web there is an implementation with a multiplication which should be less efficient.
                    if ((i & 1) == 1) // if (i % 2 == 1)  ... more efficient ??? At least the same.
                    {
                        Swap(ref items[i], ref items[indexes[i]]);
                    }
                    else
                    {
                        Swap(ref items[i], ref items[0]);
                    }

                    if (funcExecuteAndTellIfShouldStop(items))
                    {
                        return true;
                    }

                    indexes[i]++;
                    i = 1;
                }
                else
                {
                    indexes[i++] = 0;
                }
            }

            return false;
        }

        /// <summary>
        /// This function is to show a linq way but is far less efficient
        /// From: StackOverflow user: Pengyang : http://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="list"></param>
        /// <param name="length"></param>
        /// <returns></returns>
        static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
        {
            if (length == 1) return list.Select(t => new T[] { t });

            return GetPermutations(list, length - 1)
                .SelectMany(t => list.Where(e => !t.Contains(e)),
                    (t1, t2) => t1.Concat(new T[] { t2 }));
        }

        /// <summary>
        /// Swap 2 elements of same type
        /// </summary>
        /// <typeparam name="T"></typeparam>
        /// <param name="a"></param>
        /// <param name="b"></param>
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static void Swap<T>(ref T a, ref T b)
        {
            T temp = a;
            a = b;
            b = temp;
        }

        /// <summary>
        /// Func to show how to call. It does a little test for an array of 4 items.
        /// </summary>
        public static void Test()
        {
            ForAllPermutation("123".ToCharArray(), (vals) =>
            {
                Console.WriteLine(String.Join("", vals));
                return false;
            });

            int[] values = new int[] { 0, 1, 2, 4 };

            Console.WriteLine("Ouellet heap's algorithm implementation");
            ForAllPermutation(values, (vals) =>
            {
                Console.WriteLine(String.Join("", vals));
                return false;
            });

            Console.WriteLine("Linq algorithm");
            foreach (var v in GetPermutations(values, values.Length))
            {
                Console.WriteLine(String.Join("", v));
            }

            // Performance Heap's against Linq version : huge differences
            int count = 0;

            values = new int[10];
            for (int n = 0; n < values.Length; n++)
            {
                values[n] = n;
            }

            Stopwatch stopWatch = new Stopwatch();

            ForAllPermutation(values, (vals) =>
            {
                foreach (var v in vals)
                {
                    count++;
                }
                return false;
            });

            stopWatch.Stop();
            Console.WriteLine($"Ouellet heap's algorithm implementation {count} items in {stopWatch.ElapsedMilliseconds} millisecs");

            count = 0;
            stopWatch.Reset();
            stopWatch.Start();

            foreach (var vals in GetPermutations(values, values.Length))
            {
                foreach (var v in vals)
                {
                    count++;
                }
            }

            stopWatch.Stop();
            Console.WriteLine($"Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
        }
    }
}

An this is my test code:

Task.Run(() =>
            {

                int[] values = new int[12];
                for (int n = 0; n < values.Length; n++)
                {
                    values[n] = n;
                }

                // Eric Ouellet Algorithm
                int count = 0;
                var stopwatch = new Stopwatch();
                stopwatch.Reset();
                stopwatch.Start();
                Permutations.ForAllPermutation(values, (vals) =>
                {
                    foreach (var v in vals)
                    {
                        count++;
                    }
                    return false;
                });
                stopwatch.Stop();
                Console.WriteLine($"This {count} items in {stopwatch.ElapsedMilliseconds} millisecs");

                // Simple Plan Algorithm
                count = 0;
                stopwatch.Reset();
                stopwatch.Start();
                PermutationsSimpleVar permutations2 = new PermutationsSimpleVar();
                permutations2.Permutate(1, values.Length, (int[] vals) =>
                {
                    foreach (var v in vals)
                    {
                        count++;
                    }
                });
                stopwatch.Stop();
                Console.WriteLine($"Simple Plan {count} items in {stopwatch.ElapsedMilliseconds} millisecs");

                // ErezRobinson Algorithm
                count = 0;
                stopwatch.Reset();
                stopwatch.Start();
                foreach(var vals in PermutationsErezRobinson.QuickPerm(values))
                {
                    foreach (var v in vals)
                    {
                        count++;
                    }
                };
                stopwatch.Stop();
                Console.WriteLine($"Erez Robinson {count} items in {stopwatch.ElapsedMilliseconds} millisecs");
            });

Usage examples:

ForAllPermutation("123".ToCharArray(), (vals) =>
    {
        Console.WriteLine(String.Join("", vals));
        return false;
    });

int[] values = new int[] { 0, 1, 2, 4 };
ForAllPermutation(values, (vals) =>
        {
            Console.WriteLine(String.Join("", vals));
            return false;
        });