79

I would like to generate all permutations of a set (a collection), like so:

Collection: 1, 2, 3
Permutations: {1, 2, 3}
              {1, 3, 2}
              {2, 1, 3}
              {2, 3, 1}
              {3, 1, 2}
              {3, 2, 1}

This isn't a question of "how", in general, but more about how most efficiently. Also, I wouldn't want to generate ALL permutations and return them, but only generating a single permutation, at a time, and continuing only if necessary (much like Iterators - which I've tried as well, but turned out to be less efficient).

I've tested many algorithms and approaches and came up with this code, which is most efficient of those I tried:

public static bool NextPermutation<T>(T[] elements) where T : IComparable<T>
{
    // More efficient to have a variable instead of accessing a property
    var count = elements.Length;

    // Indicates whether this is the last lexicographic permutation
    var done = true;

    // Go through the array from last to first
    for (var i = count - 1; i > 0; i--)
    {
        var curr = elements[i];

        // Check if the current element is less than the one before it
        if (curr.CompareTo(elements[i - 1]) < 0)
        {
            continue;
        }

        // An element bigger than the one before it has been found,
        // so this isn't the last lexicographic permutation.
        done = false;

        // Save the previous (bigger) element in a variable for more efficiency.
        var prev = elements[i - 1];

        // Have a variable to hold the index of the element to swap
        // with the previous element (the to-swap element would be
        // the smallest element that comes after the previous element
        // and is bigger than the previous element), initializing it
        // as the current index of the current item (curr).
        var currIndex = i;

        // Go through the array from the element after the current one to last
        for (var j = i + 1; j < count; j++)
        {
            // Save into variable for more efficiency
            var tmp = elements[j];

            // Check if tmp suits the "next swap" conditions:
            // Smallest, but bigger than the "prev" element
            if (tmp.CompareTo(curr) < 0 && tmp.CompareTo(prev) > 0)
            {
                curr = tmp;
                currIndex = j;
            }
        }

        // Swap the "prev" with the new "curr" (the swap-with element)
        elements[currIndex] = prev;
        elements[i - 1] = curr;

        // Reverse the order of the tail, in order to reset it's lexicographic order
        for (var j = count - 1; j > i; j--, i++)
        {
            var tmp = elements[j];
            elements[j] = elements[i];
            elements[i] = tmp;
        }

        // Break since we have got the next permutation
        // The reason to have all the logic inside the loop is
        // to prevent the need of an extra variable indicating "i" when
        // the next needed swap is found (moving "i" outside the loop is a
        // bad practice, and isn't very readable, so I preferred not doing
        // that as well).
        break;
    }

    // Return whether this has been the last lexicographic permutation.
    return done;
}

It's usage would be sending an array of elements, and getting back a boolean indicating whether this was the last lexicographical permutation or not, as well as having the array altered to the next permutation.

Usage example:

var arr = new[] {1, 2, 3};

PrintArray(arr);

while (!NextPermutation(arr))
{
    PrintArray(arr);
}

The thing is that I'm not happy with the speed of the code.

Iterating over all permutations of an array of size 11 takes about 4 seconds. Although it could be considered impressive, since the amount of possible permutations of a set of size 11 is 11! which is nearly 40 million.

Logically, with an array of size 12 it will take about 12 times more time, since 12! is 11! * 12, and with an array of size 13 it will take about 13 times more time than the time it took with size 12, and so on.

So you can easily understand how with an array of size 12 and more, it really takes a very long time to go through all permutations.

And I have a strong hunch that I can somehow cut that time by a lot (without switching to a language other than C# - because compiler optimization really does optimize pretty nicely, and I doubt I could optimize as good, manually, in Assembly).

Does anyone know any other way to get that done faster? Do you have any idea as to how to make the current algorithm faster?

Note that I don't want to use an external library or service in order to do that - I want to have the code itself and I want it to be as efficient as humanly possible.

31
  • 13
    Generating all permutations cannot be done faster than the number of permutations.
    – nhahtdh
    Jun 26, 2012 at 13:33
  • I'm confused by this line: "but only generating a single permutation, at a time, and continuing only if necessary". What is your goal? Jun 26, 2012 at 13:34
  • 1
    Is the set to contain only unique elements? Jun 26, 2012 at 13:40
  • 7
    Btw, since the thing you're doing is inherently O(n!)-ish, there will always be a quite small number for which you're saying, "it takes a few seconds to do M, but M+1 will take M+1 times as long". Even if you could speed your code up a million times, you'd only get from 12 to 17. Would that make you a million times happier? Jun 26, 2012 at 13:42
  • 1
    @DaveBish How does that help me? This generates combinations, not permutations. Jun 26, 2012 at 16:47

18 Answers 18

39

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;
    }
22
  • 1
    This is a tiny bit faster than my implementation, thank you very much! I still expect an improvement to be a lot more significant - which would probably mean an alteration in the algorithm itself. +1 for valid answer, though! Jun 26, 2012 at 13:56
  • 3
    3 seconds is an eternity on SO... ;) One way to improve significantly would be to parallelize the algorithm. But that is not always applicable. But have a look here: scidok.sulb.uni-saarland.de/volltexte/2005/397/pdf/… Jun 26, 2012 at 14:56
  • 2
    @YoryeNathan and you owe the readers "I think I will post an article somewhere of my work."
    – colinfang
    Apr 30, 2013 at 0:54
  • 5
    @YoryeNathan, Code, or it didn't happen. Jan 24, 2014 at 16:37
  • 2
    @SaniSinghHuttunen, Hey! Just to tell you that I post a new answer where I'm using your code (and more) that I multi-threaded. Results are 4x faster on my machine. In order to go faster, I had to find a way to call an algorithm from anywhere in the sequence of permutation. I did one which is quite slow but I called only once per thread as first call then I call your algorithm. We should be able to get to best answer altogether ;-) !!! May 28, 2018 at 17:35
33

Update 2018-05-28:

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;
        });
14
  • Trusting your benchmark, I've marked this as the answer. Looks really sweet! Feb 25, 2018 at 10:47
  • 1
    Thanks! I just implemented what I found in Wikipedia. Feb 25, 2018 at 13:45
  • Of course Heap's is faster than most (all?) other algorithms. But it "breaks" the original requirement of "lexicographical order". May 21, 2018 at 18:09
  • 1
    Note that in C# a new array is guaranteed to be initialized to the default of it's type, so var indexes = new int[countOfItem]; creates indexes with all elements as 0 (default(int)) and you don't need to set them. PS Typo in summary: pmer
    – NetMage
    Apr 23, 2021 at 20:35
  • 1
    Consider (in today's C#) you could replace your first two ifs with if ((funcExecuteAndTellIfShouldStop(items) is var firstStopFlag) || countOfItem <= 1) return firstStopFlag;
    – NetMage
    Apr 23, 2021 at 21:01
12

Well, if you can handle it in C and then translate to your language of choice, you can't really go much faster than this, because the time will be dominated by print:

void perm(char* s, int n, int i){
  if (i >= n-1) print(s);
  else {
    perm(s, n, i+1);
    for (int j = i+1; j<n; j++){
      swap(s[i], s[j]);
      perm(s, n, i+1);
      swap(s[i], s[j]);
    }
  }
}

perm("ABC", 3, 0);
9
  • That was one of the first algorithms I came up with and tried, but it isn't the fastest. My current implementation is faster. Jun 26, 2012 at 18:37
  • @Yorye: Well, as I said, nearly all the time is in print. If you just comment out the print, you will see how much time the algorithm itself takes. In C#, where you are encouraged to make collection classes, iterators, and do all kinds of memory allocation, any good algorithm can be made slow as molasses. Jun 26, 2012 at 18:40
  • 1
    @Yorye: OK, two swaps takes maybe 8 instructions. A function call, entry, and return takes maybe 10 at most. The inner couple of loops are dominant, so you're talking maybe 20 instructions per permutation. If you're beating that, that's pretty clever. Jun 26, 2012 at 18:49
  • 2
    Great answer. Translated that without issue into C# (working on ref int[]).
    – AlainD
    Sep 1, 2014 at 22:35
  • 2
    This is the best algorithm, small, clean, no mutexes, great one, thanks!
    – Lu4
    Sep 6, 2014 at 6:24
9

Update 2018-05-28, a new version, the fastest ... (multi-threaded)

enter image description here

                            Time taken for fastest algorithms

Need: Sani Singh Huttunen (fastest lexico) solution and my new OuelletLexico3 which support indexing

Indexing has 2 main advantages:

  • allows to get anyone permutation directly
  • allows multi-threading (derived from the first advantage)

Article: Permutations: Fast implementations and a new indexing algorithm allowing multithreading

On my machine (6 hyperthread cores : 12 threads) Xeon E5-1660 0 @ 3.30Ghz, tests algorithms running with empty stuff to do for 13! items (time in millisecs):

  • 53071: Ouellet (implementation of Heap)
  • 65366: Sani Singh Huttunen (Fastest lexico)
  • 11377: Mix OuelletLexico3 - Sani Singh Huttunen

A side note: using shares properties/variables between threads for permutation action will strongly impact performance if their usage is modification (read / write). Doing so will generate "false sharing" between threads. You will not get expected performance. I got this behavior while testing. My experience showed problems when I try to increase the global variable for the total count of permutation.

Usage:

PermutationMixOuelletSaniSinghHuttunen.ExecuteForEachPermutationMT(
  new int[] {1, 2, 3, 4}, 
  p => 
    { 
      Console.WriteLine($"Values: {p[0]}, {p[1]}, p[2]}, {p[3]}"); 
    });

Code:

using System;
using System.Runtime.CompilerServices;

namespace WpfPermutations
{
    public class Factorial
    {
        // ************************************************************************
        protected static long[] FactorialTable = new long[21];

        // ************************************************************************
        static Factorial()
        {
            FactorialTable[0] = 1; // To prevent divide by 0
            long f = 1;
            for (int i = 1; i <= 20; i++)
            {
                f = f * i;
                FactorialTable[i] = f;
            }
        }

        // ************************************************************************
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static long GetFactorial(int val) // a long can only support up to 20!
        {
            if (val > 20)
            {
                throw new OverflowException($"{nameof(Factorial)} only support a factorial value <= 20");
            }

            return FactorialTable[val];
        }

        // ************************************************************************

    }
}


namespace WpfPermutations
{
    public class PermutationSaniSinghHuttunen
    {
        public 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;
        }
    }
}


using System;

namespace WpfPermutations
{
    public class PermutationOuelletLexico3<T> // Enable indexing 
    {
        // ************************************************************************
        private T[] _sortedValues;

        private bool[] _valueUsed;

        public readonly long MaxIndex; // long to support 20! or less 

        // ************************************************************************
        public PermutationOuelletLexico3(T[] sortedValues)
        {
            _sortedValues = sortedValues;
            Result = new T[_sortedValues.Length];
            _valueUsed = new bool[_sortedValues.Length];

            MaxIndex = Factorial.GetFactorial(_sortedValues.Length);
        }

        // ************************************************************************
        public T[] Result { get; private set; }

        // ************************************************************************
        /// <summary>
        /// Sort Index is 0 based and should be less than MaxIndex. Otherwise you get an exception.
        /// </summary>
        /// <param name="sortIndex"></param>
        /// <param name="result">Value is not used as inpu, only as output. Re-use buffer in order to save memory</param>
        /// <returns></returns>
        public void GetSortedValuesFor(long sortIndex)
        {
            int size = _sortedValues.Length;

            if (sortIndex < 0)
            {
                throw new ArgumentException("sortIndex should greater or equal to 0.");
            }

            if (sortIndex >= MaxIndex)
            {
                throw new ArgumentException("sortIndex should less than factorial(the lenght of items)");
            }

            for (int n = 0; n < _valueUsed.Length; n++)
            {
                _valueUsed[n] = false;
            }

            long factorielLower = MaxIndex;

            for (int index = 0; index < size; index++)
            {
                long factorielBigger = factorielLower;
                factorielLower = Factorial.GetFactorial(size - index - 1);  //  factorielBigger / inverseIndex;

                int resultItemIndex = (int)(sortIndex % factorielBigger / factorielLower);

                int correctedResultItemIndex = 0;
                for(;;)
                {
                    if (! _valueUsed[correctedResultItemIndex])
                    {
                        resultItemIndex--;
                        if (resultItemIndex < 0)
                        {
                            break;
                        }
                    }
                    correctedResultItemIndex++;
                }

                Result[index] = _sortedValues[correctedResultItemIndex];
                _valueUsed[correctedResultItemIndex] = true;
            }
        }

        // ************************************************************************
    }
}


using System;
using System.Collections.Generic;
using System.Threading.Tasks;

namespace WpfPermutations
{
    public class PermutationMixOuelletSaniSinghHuttunen
    {
        // ************************************************************************
        private long _indexFirst;
        private long _indexLastExclusive;
        private int[] _sortedValues;

        // ************************************************************************
        public PermutationMixOuelletSaniSinghHuttunen(int[] sortedValues, long indexFirst = -1, long indexLastExclusive = -1)
        {
            if (indexFirst == -1)
            {
                indexFirst = 0;
            }

            if (indexLastExclusive == -1)
            {
                indexLastExclusive = Factorial.GetFactorial(sortedValues.Length);
            }

            if (indexFirst >= indexLastExclusive)
            {
                throw new ArgumentException($"{nameof(indexFirst)} should be less than {nameof(indexLastExclusive)}");
            }

            _indexFirst = indexFirst;
            _indexLastExclusive = indexLastExclusive;
            _sortedValues = sortedValues;
        }

        // ************************************************************************
        public void ExecuteForEachPermutation(Action<int[]> action)
        {
            //          Console.WriteLine($"Thread {System.Threading.Thread.CurrentThread.ManagedThreadId} started: {_indexFirst} {_indexLastExclusive}");

            long index = _indexFirst;

            PermutationOuelletLexico3<int> permutationOuellet = new PermutationOuelletLexico3<int>(_sortedValues);

            permutationOuellet.GetSortedValuesFor(index);
            action(permutationOuellet.Result);
            index++;

            int[] values = permutationOuellet.Result;
            while (index < _indexLastExclusive)
            {
                PermutationSaniSinghHuttunen.NextPermutation(values);
                action(values);
                index++;
            }

            //          Console.WriteLine($"Thread {System.Threading.Thread.CurrentThread.ManagedThreadId} ended: {DateTime.Now.ToString("yyyyMMdd_HHmmss_ffffff")}");
        }

        // ************************************************************************
        public static void ExecuteForEachPermutationMT(int[] sortedValues, Action<int[]> action)
        {
            int coreCount = Environment.ProcessorCount; // Hyper treading are taken into account (ex: on a 4 cores hyperthreaded = 8)
            long itemsFactorial = Factorial.GetFactorial(sortedValues.Length);
            long partCount = (long)Math.Ceiling((double)itemsFactorial / (double)coreCount);
            long startIndex = 0;

            var tasks = new List<Task>();

            for (int coreIndex = 0; coreIndex < coreCount; coreIndex++)
            {
                long stopIndex = Math.Min(startIndex + partCount, itemsFactorial);

                PermutationMixOuelletSaniSinghHuttunen mix = new PermutationMixOuelletSaniSinghHuttunen(sortedValues, startIndex, stopIndex);
                Task task = Task.Run(() => mix.ExecuteForEachPermutation(action));
                tasks.Add(task);

                if (stopIndex == itemsFactorial)
                {
                    break;
                }

                startIndex = startIndex + partCount;
            }

            Task.WaitAll(tasks.ToArray());
        }

        // ************************************************************************


    }
}
4
  • 1
    Boom, baby. Boom! Some would say multi-threading is cheating.. but not me :P Generating permutations is a great thing to parallelize, and you can really only go so far without threading May 29, 2018 at 17:02
  • 100% agree with you! :-)... In many cases a faster MT solution would be preferred to a slower ST one. Just to let you, I would have need it that code a year or two ago. May 29, 2018 at 18:01
  • 1
    Impressive implementation indeed! Wish I could +100 this! May 29, 2018 at 18:02
  • @SaniSinghHuttunen, Wow! Thank you very much! I wouldn't achieve that performance without your code. It's really the combination of both... +100 to you also :-) ! May 29, 2018 at 18:06
8

The fastest permutation algorithm that i know of is the QuickPerm algorithm.
Here is the implementation, it uses yield return so you can iterate one at a time like required.

Code:

public static IEnumerable<IEnumerable<T>> QuickPerm<T>(this IEnumerable<T> set)
    {
        int N = set.Count();
        int[] a = new int[N];
        int[] p = new int[N];

        var yieldRet = new T[N];

        List<T> list = new List<T>(set);

        int i, j, tmp; // Upper Index i; Lower Index j

        for (i = 0; i < N; i++)
        {
            // initialize arrays; a[N] can be any type
            a[i] = i + 1; // a[i] value is not revealed and can be arbitrary
            p[i] = 0; // p[i] == i controls iteration and index boundaries for i
        }
        yield return list;
        //display(a, 0, 0);   // remove comment to display array a[]
        i = 1; // setup first swap points to be 1 and 0 respectively (i & j)
        while (i < N)
        {
            if (p[i] < i)
            {
                j = i%2*p[i]; // IF i is odd then j = p[i] otherwise j = 0
                tmp = a[j]; // swap(a[j], a[i])
                a[j] = a[i];
                a[i] = tmp;

                //MAIN!

                for (int x = 0; x < N; x++)
                {
                    yieldRet[x] = list[a[x]-1];
                }
                yield return yieldRet;
                //display(a, j, i); // remove comment to display target array a[]

                // MAIN!

                p[i]++; // increase index "weight" for i by one
                i = 1; // reset index i to 1 (assumed)
            }
            else
            {
                // otherwise p[i] == i
                p[i] = 0; // reset p[i] to zero
                i++; // set new index value for i (increase by one)
            } // if (p[i] < i)
        } // while(i < N)
    }
10
  • 2
    This is about 3 times slower than my current implementation, and doesn't iterate in lexicographic order as well. Jun 26, 2012 at 13:52
  • 1
    I haven't checked the lexographical order, but in my computer QuickPerm took 11 seconds for 11 items and your algo took 15 seconds. Anyhow, I wish you best of luck. Jun 26, 2012 at 14:24
  • 1
    @ErezRobinson: This takes about 7 seconds compared to 1.7 seconds of my implementation of Knuths algorithm with 11 elements on my computer so your algorithm is over 4 times slower. Jun 26, 2012 at 14:28
  • 1
    @ErezRobinson My implementation is 3.8~3.9 seconds on my computer (which isn't a great one), and yours is 13 seconds. Sani's is 3.7~3.8 for me. Jun 26, 2012 at 14:46
  • 1
    @ErezRobinson By the way, turns out my implementation is actually Knuth-style. Jun 26, 2012 at 16:37
4

Here is the fastest implementation I ended up with:

public class Permutations
{
    private readonly Mutex _mutex = new Mutex();

    private Action<int[]> _action;
    private Action<IntPtr> _actionUnsafe;
    private unsafe int* _arr;
    private IntPtr _arrIntPtr;
    private unsafe int* _last;
    private unsafe int* _lastPrev;
    private unsafe int* _lastPrevPrev;

    public int Size { get; private set; }

    public bool IsRunning()
    {
        return this._mutex.SafeWaitHandle.IsClosed;
    }

    public bool Permutate(int start, int count, Action<int[]> action, bool async = false)
    {
        return this.Permutate(start, count, action, null, async);
    }

    public bool Permutate(int start, int count, Action<IntPtr> actionUnsafe, bool async = false)
    {
        return this.Permutate(start, count, null, actionUnsafe, async);
    }

    private unsafe bool Permutate(int start, int count, Action<int[]> action, Action<IntPtr> actionUnsafe, bool async = false)
    {
        if (!this._mutex.WaitOne(0))
        {
            return false;
        }

        var x = (Action)(() =>
                             {
                                 this._actionUnsafe = actionUnsafe;
                                 this._action = action;

                                 this.Size = count;

                                 this._arr = (int*)Marshal.AllocHGlobal(count * sizeof(int));
                                 this._arrIntPtr = new IntPtr(this._arr);

                                 for (var i = 0; i < count - 3; i++)
                                 {
                                     this._arr[i] = start + i;
                                 }

                                 this._last = this._arr + count - 1;
                                 this._lastPrev = this._last - 1;
                                 this._lastPrevPrev = this._lastPrev - 1;

                                 *this._last = count - 1;
                                 *this._lastPrev = count - 2;
                                 *this._lastPrevPrev = count - 3;

                                 this.Permutate(count, this._arr);
                             });

        if (!async)
        {
            x();
        }
        else
        {
            new Thread(() => x()).Start();
        }

        return true;
    }

    private unsafe void Permutate(int size, int* start)
    {
        if (size == 3)
        {
            this.DoAction();
            Swap(this._last, this._lastPrev);
            this.DoAction();
            Swap(this._last, this._lastPrevPrev);
            this.DoAction();
            Swap(this._last, this._lastPrev);
            this.DoAction();
            Swap(this._last, this._lastPrevPrev);
            this.DoAction();
            Swap(this._last, this._lastPrev);
            this.DoAction();

            return;
        }

        var sizeDec = size - 1;
        var startNext = start + 1;
        var usedStarters = 0;

        for (var i = 0; i < sizeDec; i++)
        {
            this.Permutate(sizeDec, startNext);

            usedStarters |= 1 << *start;

            for (var j = startNext; j <= this._last; j++)
            {
                var mask = 1 << *j;

                if ((usedStarters & mask) != mask)
                {
                    Swap(start, j);
                    break;
                }
            }
        }

        this.Permutate(sizeDec, startNext);

        if (size == this.Size)
        {
            this._mutex.ReleaseMutex();
        }
    }

    private unsafe void DoAction()
    {
        if (this._action == null)
        {
            if (this._actionUnsafe != null)
            {
                this._actionUnsafe(this._arrIntPtr);
            }

            return;
        }

        var result = new int[this.Size];

        fixed (int* pt = result)
        {
            var limit = pt + this.Size;
            var resultPtr = pt;
            var arrayPtr = this._arr;

            while (resultPtr < limit)
            {
                *resultPtr = *arrayPtr;
                resultPtr++;
                arrayPtr++;
            }
        }

        this._action(result);
    }

    private static unsafe void Swap(int* a, int* b)
    {
        var tmp = *a;
        *a = *b;
        *b = tmp;
    }
}

Usage and testing performance:

var perms = new Permutations();

var sw1 = Stopwatch.StartNew();

perms.Permutate(0,
                11,
                (Action<int[]>)null); // Comment this line and...
                //PrintArr); // Uncomment this line, to print permutations

sw1.Stop();
Console.WriteLine(sw1.Elapsed);

Printing method:

private static void PrintArr(int[] arr)
{
    Console.WriteLine(string.Join(",", arr));
}

Going deeper:

I did not even think about this for a very long time, so I can only explain my code so much, but here's the general idea:

  1. Permutations aren't lexicographic - this allows me to practically perform less operations between permutations.
  2. The implementation is recursive, and when the "view" size is 3, it skips the complex logic and just performs 6 swaps to get the 6 permutations (or sub-permutations, if you will).
  3. Because the permutations aren't in a lexicographic order, how can I decide which element to bring to the start of the current "view" (sub permutation)? I keep record of elements that were already used as "starters" in the current sub-permutation recursive call and simply search linearly for one that wasn't used in the tail of my array.
  4. The implementation is for integers only, so to permute over a generic collection of elements you simply use the Permutations class to permute indices instead of your actual collection.
  5. The Mutex is there just to ensure things don't get screwed when the execution is asynchronous (notice that you can pass an UnsafeAction parameter that will in turn get a pointer to the permuted array. You must not change the order of elements in that array (pointer)! If you want to, you should copy the array to a tmp array or just use the safe action parameter which takes care of that for you - the passed array is already a copy).

Note:

I have no idea how good this implementation really is - I haven't touched it in so long. Test and compare to other implementations on your own, and let me know if you have any feedback!

Enjoy.

5
  • 1
    @Lu4 What's awful about it? The more optimizations, the less beautiful the code - but it runs lightning fast. Sep 6, 2014 at 15:39
  • Your original implementation (provided in your question) is the best solution here. It's clean and fast code and generates sorted permutation. I'd never use this marked as answer actually... Sep 14, 2015 at 11:58
  • P.S. I'm actually studying your original solution, I had the same intuitions you had but I did not manage to code a general solution. Well done. Sep 14, 2015 at 13:08
  • @sam The code in the question is stable and working well, yes. But the topic was really making it as efficient as possible (even at the cost of readability), which this solution provided best for me. Sep 15, 2015 at 6:20
  • @SimpleVar, It works, but it is ~2x slower than mine. Also, your code is unsafe. When you test, if you put null as Action, how could you tell that compiler optimization will not throw away the reading of yield (the real calculation of permutation) ? Apr 14, 2016 at 22:02
3

Here is a generic permutation finder that will iterate through every permutation of a collection and call an evalution function. If the evalution function returns true (it found the answer it was looking for), the permutation finder stops processing.

public class PermutationFinder<T>
{
    private T[] items;
    private Predicate<T[]> SuccessFunc;
    private bool success = false;
    private int itemsCount;

    public void Evaluate(T[] items, Predicate<T[]> SuccessFunc)
    {
        this.items = items;
        this.SuccessFunc = SuccessFunc;
        this.itemsCount = items.Count();

        Recurse(0);
    }

    private void Recurse(int index)
    {
        T tmp;

        if (index == itemsCount)
            success = SuccessFunc(items);
        else
        {
            for (int i = index; i < itemsCount; i++)
            {
                tmp = items[index];
                items[index] = items[i];
                items[i] = tmp;

                Recurse(index + 1);

                if (success)
                    break;

                tmp = items[index];
                items[index] = items[i];
                items[i] = tmp;
            }
        }
    }
}

Here is a simple implementation:

class Program
{
    static void Main(string[] args)
    {
        new Program().Start();
    }

    void Start()
    {
        string[] items = new string[5];
        items[0] = "A";
        items[1] = "B";
        items[2] = "C";
        items[3] = "D";
        items[4] = "E";
        new PermutationFinder<string>().Evaluate(items, Evaluate);
        Console.ReadLine();
    }

    public bool Evaluate(string[] items)
    {
        Console.WriteLine(string.Format("{0},{1},{2},{3},{4}", items[0], items[1], items[2], items[3], items[4]));
        bool someCondition = false;

        if (someCondition)
            return true;  // Tell the permutation finder to stop.

        return false;
    }
}
14
  • 1
    I saved items.Count to a variable. The code as posted now takes ~ .55 seconds to iterate a list of ten items. The code in the original post takes ~ 2.22 seconds for the same list.
    – Sam
    Jun 17, 2013 at 20:17
  • 1
    For a list of 12 items (39,916,800 permutations) this code takes ~ 1 min 13 seconds vs. ~ 2 min 40 seconds for code in the original post.
    – Sam
    Jun 17, 2013 at 20:41
  • 1
    My current code is ~1.3-1.5sec for 11 elements. The fact is, you're doing 2N! swaps when the minimum required swaps are N!. Jun 17, 2013 at 21:32
  • I would expect at least a x1.5 difference between our versions, since I do nearly N! swaps (kN! where k is very close to 1), so I assume my computer is simply a bit slower. Jun 17, 2013 at 21:39
  • 1
    This algorithm is ~3 times slower than my implementation of Knuth's. On 12 elements it takes 33169ms compared to 11941ms. The order isn't strictly lexicographical either. Jun 19, 2013 at 7:26
2

Here is a recursive implementation with complexity O(n * n!)1 based on swapping of the elements of an array. The array is initialised with values from 1, 2, ..., n.

using System;

namespace Exercise
{
class Permutations
{
    static void Main(string[] args)
    {
        int setSize = 3;
        FindPermutations(setSize);
    }
    //-----------------------------------------------------------------------------
    /* Method: FindPermutations(n) */
    private static void FindPermutations(int n)
    {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = i + 1;
        }
        int iEnd = arr.Length - 1;
        Permute(arr, iEnd);
    }
    //-----------------------------------------------------------------------------  
    /* Method: Permute(arr) */
    private static void Permute(int[] arr, int iEnd)
    {
        if (iEnd == 0)
        {
            PrintArray(arr);
            return;
        }

        Permute(arr, iEnd - 1);
        for (int i = 0; i < iEnd; i++)
        {
            swap(ref arr[i], ref arr[iEnd]);
            Permute(arr, iEnd - 1);
            swap(ref arr[i], ref arr[iEnd]);
        }
    }
}
}

On each recursive step we swap the last element with the current element pointed to by the local variable in the for loop and then we indicate the uniqueness of the swapping by: incrementing the local variable of the for loop and decrementing the termination condition of the for loop, which is initially set to the number of the elements in the array, when the latter becomes zero we terminate the recursion.

Here are the helper functions:

    //-----------------------------------------------------------------------------
    /*
        Method: PrintArray()

    */
    private static void PrintArray(int[] arr, string label = "")
    {
        Console.WriteLine(label);
        Console.Write("{");
        for (int i = 0; i < arr.Length; i++)
        {
            Console.Write(arr[i]);
            if (i < arr.Length - 1)
            {
                Console.Write(", ");
            }
        }
        Console.WriteLine("}");
    }
    //-----------------------------------------------------------------------------

    /*
        Method: swap(ref int a, ref int b)

    */
    private static void swap(ref int a, ref int b)
    {
        int temp = a;
        a = b;
        b = temp;
    }

1. There are n! permutations of n elements to be printed.

2
  • 1
    Nice and neat solution for general purposes. However in terms of speed it falls behind. But +1 for good code, since most coders are likely to prefer readability for most uses. Oct 13, 2016 at 23:47
  • Is there a way to make this return combinations? If so, does it have to create permutations first?
    – Terry
    May 26, 2022 at 1:16
1

I would be surprised if there are really order of magnitude improvements to be found. If there are, then C# needs fundamental improvement. Furthermore doing anything interesting with your permutation will generally take more work than generating it. So the cost of generating is going to be insignificant in the overall scheme of things.

That said, I would suggest trying the following things. You have already tried iterators. But have you tried having a function that takes a closure as input, then then calls that closure for each permutation found? Depending on internal mechanics of C#, this may be faster.

Similarly, have you tried having a function that returns a closure that will iterate over a specific permutation?

With either approach, there are a number of micro-optimizations you can experiment with. For instance you can sort your input array, and after that you always know what order it is in. For example you can have an array of bools indicating whether that element is less than the next one, and rather than do comparisons, you can just look at that array.

5
  • +1 For good information. Using closure will maybe somewhat make it faster, but only by a tiny bit. I would imagine that it only saves a few stack operations of copying the pointer to the array, and little stuff like that - nothing significant, though. The second idea you've suggested - using a boolean array - might make a good change! I'll try that and come back to you :) Jun 26, 2012 at 16:03
  • The bools idea didn't turn out to be helpful at all... I still need to compare non-neighbor values when searching for the "swap partner" in the "tail", and accessing a bool in an array isn't much different than comparing two integers. Managing a second array wasted time in this case. But nice idea. Jun 26, 2012 at 16:42
  • 1
    @YoryeNathan But you are now in a position to try other things. For instance loop unrolling. Emit a perm. Then swap the last two and emit the next perm. Then go back to your more complex logic, secure in the knowledge that you know the last two elements are reversed. This skips the full logic for half of perms, and skips one comparison for the other half of perms. You can try unrolling farther - at some point you'll hit cache issues and it will not be worthwhile.
    – btilly
    Jun 26, 2012 at 17:17
  • That's a nice idea, but I doubt it will matter that much. It basically saves me just a few variables declared and stepping in and immediately out of two loops, and a single comparison between two elements. The comparison might be significant if the elements were class instances that implement IComparable with some logic, but then again, in such case, I would use an array of integers {0, 1, 2, ...} to indicates indexing into the array of elements, for fast comparison. Jun 26, 2012 at 18:20
  • Turns out I was wrong, it was a great idea! It cuts the time in by much! Thanks! Waiting to see if any thing better comes up, and considering marking this as the answer. Jun 26, 2012 at 18:26
1

There's an accessible introduction to the algorithms and survey of implementations in Steven Skiena's Algorithm Design Manual (chapter 14.4 in the second edition)

Skiena references D. Knuth. The Art of Computer Programming, Volume 4 Fascicle 2: Generating All Tuples and Permutations. Addison Wesley, 2005.

5
  • The link is broken for me, although Google finds that website as well, so it's weird. Pinging to it in CMD results with timed-outs, so I can only guess the link is actually broken. Jun 26, 2012 at 14:14
  • I think the author's website is down. Resort to Amazon, or your library. Jun 26, 2012 at 14:15
  • @MattHickford The book has some good information there, but nothing that can practically help me. Jun 26, 2012 at 14:44
  • I imagine Knuth is comprehensive but I don't have a copy. Jun 26, 2012 at 15:14
  • I didn't hear of Knuth algorithm before, but turns out my algorithm is pretty much his. Jun 26, 2012 at 16:38
1

I created an algorithm slightly faster than Knuth's one:

11 elements:

mine: 0.39 seconds

Knuth's: 0.624 seconds

13 elements:

mine: 56.615 seconds

Knuth's: 98.681 seconds

Here's my code in Java:

public static void main(String[] args)
{
    int n=11;
    int a,b,c,i,tmp;
    int end=(int)Math.floor(n/2);
    int[][] pos = new int[end+1][2];
    int[] perm = new int[n];

    for(i=0;i<n;i++) perm[i]=i;

    while(true)
    {
        //this is where you can use the permutations (perm)
        i=0;
        c=n;

        while(pos[i][1]==c-2 && pos[i][0]==c-1)
        {
            pos[i][0]=0;
            pos[i][1]=0;
            i++;
            c-=2;
        }

        if(i==end) System.exit(0);

        a=(pos[i][0]+1)%c+i;
        b=pos[i][0]+i;

        tmp=perm[b];
        perm[b]=perm[a];
        perm[a]=tmp;

        if(pos[i][0]==c-1)
        {
            pos[i][0]=0;
            pos[i][1]++;
        }
        else
        {
            pos[i][0]++;
        }
    }
}

The problem is my algorithm only works for odd numbers of elements. I wrote this code quickly so I'm pretty sure there's a better way to implement my idea to get better performance, but I don't really have the time to work on it right now to optimize it and solve the issue when the number of elements is even.

It's one swap for every permutation and it uses a really simple way to know which elements to swap.

I wrote an explanation of the method behind the code on my blog: http://antoinecomeau.blogspot.ca/2015/01/fast-generation-of-all-permutations.html

3
  • Seems interesting, though it seems to be somewhat slower than my current implementation (marked as answer). I'd love to understand it, though. Also wondering how you actually timed the performance with a broken code (new int[end + 1][2] should become new int[end + 1][] with an appropriate loop init following) Jan 28, 2015 at 1:02
  • 1
    Since we talk about performance, get rid of the jagged arrays and use stride instead.
    – CSharpie
    May 4, 2015 at 12:56
  • permutations are not generated in order with this algorithm Sep 11, 2015 at 9:52
1

As the author of this question was asking about an algorithm:

[...] generating a single permutation, at a time, and continuing only if necessary

I would suggest considering Steinhaus–Johnson–Trotter algorithm.

Steinhaus–Johnson–Trotter algorithm on Wikipedia

Beautifully explained here

0

It's 1 am and I was watching TV and thought of this same question, but with string values.

Given a word find all permutations. You can easily modify this to handle an array, sets, etc.

Took me a bit to work it out, but the solution I came up was this:

string word = "abcd";

List<string> combinations = new List<string>();

for(int i=0; i<word.Length; i++)
{
    for (int j = 0; j < word.Length; j++)
    {
        if (i < j)
            combinations.Add(word[i] + word.Substring(j) + word.Substring(0, i) + word.Substring(i + 1, j - (i + 1)));
        else if (i > j)
        {
            if(i== word.Length -1)
                combinations.Add(word[i] + word.Substring(0, i));
            else
                combinations.Add(word[i] + word.Substring(0, i) + word.Substring(i + 1));
        }
    }
}

Here's the same code as above, but with some comments

string word = "abcd";

List<string> combinations = new List<string>();

//i is the first letter of the new word combination
for(int i=0; i<word.Length; i++)
{
    for (int j = 0; j < word.Length; j++)
    {
        //add the first letter of the word, j is past i so we can get all the letters from j to the end
        //then add all the letters from the front to i, then skip over i (since we already added that as the beginning of the word)
        //and get the remaining letters from i+1 to right before j.
        if (i < j)
            combinations.Add(word[i] + word.Substring(j) + word.Substring(0, i) + word.Substring(i + 1, j - (i + 1)));
        else if (i > j)
        {
            //if we're at the very last word no need to get the letters after i
            if(i== word.Length -1)
                combinations.Add(word[i] + word.Substring(0, i));
            //add i as the first letter of the word, then get all the letters up to i, skip i, and then add all the lettes after i
            else
                combinations.Add(word[i] + word.Substring(0, i) + word.Substring(i + 1));

        }
    }
}
0

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
/**
 * http://marknelson.us/2002/03/01/next-permutation/
 * Rearranges the elements into the lexicographically next greater permutation and returns true.
 * When there are no more greater permutations left, the function eventually returns false.
 */

// next lexicographical permutation

template <typename T>
bool next_permutation(T &arr[], int firstIndex, int lastIndex)
{
    int i = lastIndex;
    while (i > firstIndex)
    {
        int ii = i--;
        T curr = arr[i];
        if (curr < arr[ii])
        {
            int j = lastIndex;
            while (arr[j] <= curr) j--;
            Swap(arr[i], arr[j]);
            while (ii < lastIndex)
                Swap(arr[ii++], arr[lastIndex--]);
            return true;
        }
    }
    return false;
}

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
/**
 * Swaps two variables or two array elements.
 * using references/pointers to speed up swapping.
 */
template<typename T>
void Swap(T &var1, T &var2)
{
    T temp;
    temp = var1;
    var1 = var2;
    var2 = temp;
}

//+------------------------------------------------------------------+
//|                                                                  |
//+------------------------------------------------------------------+
// driver program to test above function
#define N 3

void OnStart()
{
    int i, x[N];
    for (i = 0; i < N; i++) x[i] = i + 1;

    printf("The %i! possible permutations with %i elements:", N, N);

    do
    {
        printf("%s", ArrayToString(x));

    } while (next_permutation(x, 0, N - 1));

}

// Output:
// The 3! possible permutations with 3 elements:
// "1,2,3"
// "1,3,2"
// "2,1,3"
// "2,3,1"
// "3,1,2"
// "3,2,1"

1
  • This code is hard to understand. It makes 0 sense to be terse with variable names in this instance. Mar 28, 2018 at 3:52
0

// Permutations are the different ordered arrangements of an n-element
// array. An n-element array has exactly n! full-length permutations.

// This iterator object allows to iterate all full length permutations
// one by one of an array of n distinct elements.

// The iterator changes the given array in-place.

// Permutations('ABCD') => ABCD  DBAC  ACDB  DCBA
//                         BACD  BDAC  CADB  CDBA
//                         CABD  ADBC  DACB  BDCA
//                         ACBD  DABC  ADCB  DBCA
//                         BCAD  BADC  CDAB  CBDA
//                         CBAD  ABDC  DCAB  BCDA

// count of permutations = n!

// Heap's algorithm (Single swap per permutation)
// http://www.quickperm.org/quickperm.php
// https://stackoverflow.com/a/36634935/4208440
// https://en.wikipedia.org/wiki/Heap%27s_algorithm


// My implementation of Heap's algorithm:

template<typename T>
class PermutationsIterator
{
	int b, e, n;
	int c[32];  /* control array: mixed radix number in rising factorial base.
	            the i-th digit has base i, which means that the digit must be
	            strictly less than i. The first digit is always 0,  the second
	            can be 0 or 1, the third 0, 1 or 2, and so on.
	            ArrayResize isn't strictly necessary, int c[32] would suffice
	            for most practical purposes. Also, it is much faster */

public:
	PermutationsIterator(T &arr[], int firstIndex, int lastIndex)
	{
		this.b = firstIndex;  // v.begin()
		this.e = lastIndex;   // v.end()
		this.n = e - b + 1;

		ArrayInitialize(c, 0);
	}

	// Rearranges the input array into the next permutation and returns true.
	// When there are no more permutations left, the function returns false.

	bool next(T &arr[])
	{
		// find index to update
		int i = 1;

		// reset all the previous indices that reached the maximum possible values
		while (c[i] == i)
		{
			c[i] = 0;
			++i;
		}

		// no more permutations left
		if (i == n)
			return false;

		// generate next permutation
		int j = (i & 1) == 1 ? c[i] : 0;    // IF i is odd then j = c[i] otherwise j = 0.
		swap(arr[b + j], arr[b + i]);       // generate a new permutation from previous permutation using a single swap

		// Increment that index
		++c[i];
		return true;
	}

};

-1

I found this algo on rosetta code and it is really the fastest one I tried. http://rosettacode.org/wiki/Permutations#C

/* Boothroyd method; exactly N! swaps, about as fast as it gets */
void boothroyd(int *x, int n, int nn, int callback(int *, int))
{
	int c = 0, i, t;
	while (1) {
		if (n > 2) boothroyd(x, n - 1, nn, callback);
		if (c >= n - 1) return;
 
		i = (n & 1) ? 0 : c;
		c++;
		t = x[n - 1], x[n - 1] = x[i], x[i] = t;
		if (callback) callback(x, nn);
	}
}
 
/* entry for Boothroyd method */
void perm2(int *x, int n, int callback(int*, int))
{
	if (callback) callback(x, n);
	boothroyd(x, n, n, callback);
}
 

1
  • 1
    This code is hard to understand. It makes 0 sense to be terse with variable names in this instance. Mar 28, 2018 at 3:52
-2

If you just want to calculate the number of possible permutations you can avoid all that hard work above and use something like this (contrived in c#):

public static class ContrivedUtils 
{
    public static Int64 Permutations(char[] array)
    {
        if (null == array || array.Length == 0) return 0;

        Int64 permutations = array.Length;

        for (var pos = permutations; pos > 1; pos--)
            permutations *= pos - 1;

        return permutations;
    }
}

You call it like this:

var permutations = ContrivedUtils.Permutations("1234".ToCharArray());
// output is: 24
var permutations = ContrivedUtils.Permutations("123456789".ToCharArray());
// output is: 362880
3
  • 1
    Yeah, it's really not that hard to implement factoring. The idea is to have the permutations themselves, though. Not to mention, you would be better off with just .Permutations(4) instead of a meaningless array of chars. Feb 5, 2015 at 19:26
  • true, but every time I've been asked this question in interviews the input is always a string of chars, so it seemed worthwhile to present it that way.
    – soultech
    Feb 5, 2015 at 19:50
  • And yet, the whole answer remains irrelevant to the subject. Feb 5, 2015 at 20:18
-2

Simple C# recursive solution by swapping, for the initial call the index must be 0

    static public void Permute<T>(List<T> input, List<List<T>> permutations, int index)
    {
        if (index == input.Count - 1)
        {
            permutations.Add(new List<T>(input));
            return;
        }

        Permute(input, permutations, index + 1);

        for (int i = index+1 ; i < input.Count; i++)
        {
            //swap
            T temp = input[index];
            input[index] = input[i];
            input[i] = temp;

            Permute(input, permutations, index + 1);

            //swap back
            temp = input[index];
            input[index] = input[i];
            input[i] = temp;
        }
    }

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.