Gerando permutações de um conjunto (mais eficientemente)

Eu gostaria de gerar todas as permutações de um conjunto (uma coleção), assim:

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

Esta não é uma questão de “como”, em geral, mas mais sobre como mais eficientemente. Além disso, eu não gostaria de gerar TODAS as permutações e retorná-las, mas apenas gerando uma permutação única, de cada vez, e continuando apenas se necessário (muito parecido com Iteradores – que eu também tentei, mas acabou sendo menos eficiente).

Eu testei muitos algoritmos e abordagens e criei este código, que é o mais eficiente daqueles que eu tentei:

 public static bool NextPermutation(T[] elements) where T : IComparable { // 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) { 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; } 

Seu uso seria o envio de uma matriz de elementos, e receber de volta um booleano indicando se esta foi a última permutação lexicográfica ou não, bem como ter o array alterado para a próxima permutação.

Exemplo de uso:

 var arr = new[] {1, 2, 3}; PrintArray(arr); while (!NextPermutation(arr)) { PrintArray(arr); } 

O problema é que não estou feliz com a velocidade do código.

Iterar todas as permutações de uma matriz de tamanho 11 leva cerca de 4 segundos. Embora possa ser considerado impressionante, uma vez que a quantidade de permutações possíveis de um conjunto de tamanho 11 é 11! que é quase 40 milhões.

Logicamente, com uma matriz de tamanho 12, levará cerca de 12 vezes mais tempo, desde 12! é 11! * 12 11! * 12 , e com uma matriz de tamanho 13, levará cerca de 13 vezes mais tempo do que o tamanho 12, e assim por diante.

Assim, você pode entender facilmente como, com uma matriz de tamanho 12 e mais, leva muito tempo para passar por todas as permutações.

E eu tenho um forte pressentimento de que eu posso de alguma forma cortar esse tempo em muito (sem mudar para um idioma diferente de C # – porque a otimização do compilador realmente otimiza muito bem, e eu duvido que eu poderia otimizar tão bem, manualmente, em Assembly).

Alguém sabe alguma outra maneira de fazer isso mais rápido? Você tem alguma idéia de como tornar o algoritmo atual mais rápido?

Note que eu não quero usar uma biblioteca ou serviço externo para fazer isso – eu quero ter o código em si e eu quero que ele seja tão eficiente quanto humanamente possível.

    Atualização 2018-05-28, uma nova versão multithread está disponível abaixo como outra resposta.

    Um pouco tarde demais …

    De acordo com testes recentes (atualizado em 2018-05-22)

    • O mais rápido é meu, MAS não em ordem lexicográfica
    • Para uma ordem lexicográfica mais rápida, a solução de Sani Singh Huttunen parece ser o caminho a percorrer.

    Resultados do teste de desempenho para 10 itens (10!) No lançamento na minha máquina (millisecs):

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

    Resultados do teste de desempenho para 13 itens (13!) No lançamento na minha máquina (segundos):

    • Ouellet: 48.437
    • SimpleVar: 159.869
    • Erez Robinson: 327.781
    • Sani Singh Huttunen: 64,839

    Vantagens da minha solução:

    • Algoritmo da pilha (troca simples por permutação)
    • Nenhuma multiplicação (como algumas implementações vistas na web)
    • Troca Inlined
    • Genérico
    • Nenhum código não seguro
    • No lugar (uso de memory muito baixo)
    • Nenhum módulo (somente primeiro bit compare)

    Minha implementação do algoritmo do Heap :

     using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Runtime.CompilerServices; namespace WpfPermutations { ///  /// 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 ///  public static class Permutations { ///  /// Heap's algorithm to find all pmermutations. Non recursive, more efficient. ///  /// Items to permute in each possible ways ///  /// Return true if cancelled public static bool ForAllPermutation(T[] items, Func funcExecuteAndTellIfShouldStop) { int countOfItem = items.Length; if (countOfItem < = 1) { return funcExecuteAndTellIfShouldStop(items); } var indexes = new int[countOfItem]; 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; } ///  /// 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 ///  ///  ///  ///  ///  static IEnumerable> GetPermutations(IEnumerable 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 })); } ///  /// Swap 2 elements of same type ///  ///  ///  ///  [MethodImpl(MethodImplOptions.AggressiveInlining)] static void Swap(ref T a, ref T b) { T temp = a; a = b; b = temp; } ///  /// Func to show how to call. It does a little test for an array of 4 items. ///  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"); } } } 

    Este é o meu código de teste:

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

    Exemplos de uso:

     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; }); 

    Isso pode ser o que você está procurando.

      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; } 

    Bem, se você pode lidar com isso em C e depois traduzir para o seu idioma de preferência, você não pode ir muito mais rápido do que isso, porque o tempo será dominado pela 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 

    O algoritmo de permutação mais rápido que conheço é o algoritmo QuickPerm.
    Aqui está a implementação, ele usa o retorno de rendimento para que você possa iterar um de cada vez, como exigido.

    Código:

     public static IEnumerable> QuickPerm(this IEnumerable set) { int N = set.Count(); int[] a = new int[N]; int[] p = new int[N]; var yieldRet = new T[N]; List list = new List(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) } 

    Aqui está a implementação mais rápida com a qual acabei:

     public class Permutations { private readonly Mutex _mutex = new Mutex(); private Action _action; private Action _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 action, bool async = false) { return this.Permutate(start, count, action, null, async); } public bool Permutate(int start, int count, Action actionUnsafe, bool async = false) { return this.Permutate(start, count, null, actionUnsafe, async); } private unsafe bool Permutate(int start, int count, Action action, Action 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; } } 

    Uso e desempenho de testes:

     var perms = new Permutations(); var sw1 = Stopwatch.StartNew(); perms.Permutate(0, 11, (Action)null); // Comment this line and... //PrintArr); // Uncomment this line, to print permutations sw1.Stop(); Console.WriteLine(sw1.Elapsed); 

    Método de impressão:

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

    Indo mais fundo:

    Eu nem sequer pensei nisso por muito tempo, então eu só posso explicar meu código, mas aqui está a idéia geral:

    1. Permutações não são lexicográficas - isso me permite praticamente realizar menos operações entre permutações.
    2. A implementação é recursiva, e quando o tamanho da "visão" é 3, ela pula a lógica complexa e apenas executa 6 trocas para obter as 6 permutações (ou sub-permutações, se você quiser).
    3. Como as permutações não estão em ordem lexicográfica, como posso decidir qual elemento levar ao início da "visão" atual (sub-permutação)? Eu mantenho o registro de elementos que já foram usados ​​como "iniciadores" na chamada recursiva de sub-permutação atual e simplesmente procuro linearmente por um que não foi usado na cauda da minha matriz.
    4. A implementação é apenas para números inteiros, portanto, para permutar sobre uma coleção genérica de elementos, você simplesmente usa a class Permutations para permutar índices em vez de sua coleção real.
    5. O Mutex está lá apenas para garantir que as coisas não se estraguem quando a execução é assíncrona (observe que você pode passar um parâmetro UnsafeAction que por sua vez obterá um ponteiro para o array permutado. Você não deve alterar a ordem dos elementos nesse array (ponteiro)! Se você quiser, você deve copiar a matriz para uma matriz tmp ou apenas usar o parâmetro de ação segura que cuida disso para você - a matriz passada já é uma cópia).

    Nota:

    Eu não tenho ideia de como essa implementação é realmente boa - eu não a tenho tocado há tanto tempo. Teste e compare com outras implementações por conta própria e deixe-me saber se você tem algum comentário!

    Apreciar.

    Aqui está um localizador de permutação genérico que irá percorrer todas as permutações de uma coleção e chamar uma function de avaliação. Se a function de avaliação retornar true (encontrou a resposta que estava procurando), o localizador de permutação interromperá o processamento.

     public class PermutationFinder { private T[] items; private Predicate SuccessFunc; private bool success = false; private int itemsCount; public void Evaluate(T[] items, Predicate 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; } } } } 

    Aqui está uma implementação simples:

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

    Aqui está uma implementação recursiva com complexidade O(n * n!) 1 baseada na troca dos elementos de uma matriz. O array é inicializado com valores de 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]); } } } } 

    Em cada etapa recursiva, trocamos o último elemento pelo elemento atual apontado pela variável local no loop for e, em seguida, indicamos a exclusividade da troca: incrementando a variável local do loop for e diminuindo a condição de terminação do loop for loop, que é inicialmente definido como o número dos elementos na matriz, quando este se torna zero, terminamos a recursion.

    Aqui estão as funções auxiliares:

      //----------------------------------------------------------------------------- /* 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. Existem n! permutações de n elementos a serem impressos.

    Atualização 2018-05-28, uma nova versão, mais rápida, multi-threaded …

    insira a descrição da imagem aqui

      Time taken for fastest algorithms 

    Necessidade: Solução Sani Singh Huttunen (léxico mais rápido) e meu novo OuelletLexico3 que suporta indexação (onde uma de suas vantagens simplifica a divisão de tarefas para multithreading) …

    Na minha máquina (6 núcleos hyperthread: 12 threads) Xeon E5-1660 0 @ 3.30Ghz, testa algoritmos rodando com coisas vazias para fazer por 13! itens (tempo em milissegundos):

    • 53071: Ouellet (implementação do heap)
    • 65366: Sani Singh Huttunen (léxico mais rápido)
    • 11377: Mix OuelletLexico3 – Sani Singh Huttunen

    Uma observação secundária: o uso de propriedades / variables ​​de compartilhamentos entre encadeamentos para a ação de permutação terá um grande impacto no desempenho se seu uso for uma modificação (leitura / gravação). Fazer isso gerará ” compartilhamento falso ” entre os segmentos, você não obterá o desempenho esperado. Eu tenho esse comportamento durante o teste (principalmente quando tento aumentar a variável global para a contagem total de permutação).

    Uso:

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

    Código:

     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 // 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; } // ************************************************************************ ///  /// Sort Index is 0 based and should be less than MaxIndex. Otherwise you get an exception. ///  ///  /// Value is not used as inpu, only as output. Re-use buffer in order to save memory ///  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 action) { // Console.WriteLine($"Thread {System.Threading.Thread.CurrentThread.ManagedThreadId} started: {_indexFirst} {_indexLastExclusive}"); long index = _indexFirst; PermutationOuelletLexico3 permutationOuellet = new PermutationOuelletLexico3(_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 action) { int coreCount = Environment.ProcessorCount; // Hyper treading are taken into account (ex: on a 4 colors hyperthreaded = 8) long itemsFactorial = Factorial.GetFactorial(sortedValues.Length); long partCount = (long)Math.Ceiling((double)itemsFactorial / (double)coreCount); long startIndex = 0; var tasks = new List(); 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()); } // ************************************************************************ } } 

    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.

    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.

    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 

    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

    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

    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 combinations = new List(); for(int i=0; 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 combinations = new List(); //i is the first letter of the new word combination for(int i=0; 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)); } } } 

    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); } 
     //+------------------------------------------------------------------+ //| | //+------------------------------------------------------------------+ /** * 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  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 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" 
     // 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 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; } }; 

    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; } } 

    Você chama assim:

     var permutations = ContrivedUtils.Permutations("1234".ToCharArray()); // output is: 24 var permutations = ContrivedUtils.Permutations("123456789".ToCharArray()); // output is: 362880