c# performance algorithm optimization permutation

c# - Generando permutaciones de un conjunto(más eficientemente)



performance algorithm (17)

Actualización 2018-05-28, una nueva versión multiproceso está disponible a continuación como otra respuesta.

Un poco demasiado tarde ...

De acuerdo con pruebas recientes (actualizado 2018-05-22)

  • Lo más rápido es mío PERO no en orden lexicográfico
  • Para un orden lexicográfico más rápido, la solución de Sani Singh Huttunen parece ser el camino a seguir.

Resultados de la prueba de rendimiento de 10 elementos (10!) En versión en mi máquina (milisegundos):

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

Resultados de la prueba de rendimiento para 13 elementos (13!) En versión en mi máquina (segundos):

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

Ventajas de mi solución:

  • Algoritmo de Heap (intercambio único por permutación)
  • Sin multiplicación (como algunas implementaciones vistas en la web)
  • Cambio en línea
  • Genérico
  • Sin código inseguro
  • En su lugar (uso de memoria muy bajo)
  • Sin módulo (solo el primer bit se compara)

Mi implementación del algoritmo de Heap :

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

Este es mi código de prueba:

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

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

Me gustaría generar todas las permutaciones de un conjunto (una colección), así:

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

Esta no es una cuestión de "cómo", en general, sino más acerca de cómo más eficientemente. Además, no me gustaría generar TODAS las permutaciones y devolverlas, sino solo generar una sola permutación, a la vez, y continuar solo si es necesario (al igual que los iteradores, lo cual también he intentado, pero resultó ser menos eficiente).

Probé muchos algoritmos y enfoques y obtuve este código, que es el más eficiente de los que probé:

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

Su uso sería enviar una matriz de elementos y obtener un booleano que indique si esta fue la última permutación lexicográfica o no, además de tener la matriz alterada para la siguiente permutación.

Ejemplo de uso:

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

El caso es que no estoy contento con la velocidad del código.

Iterar todas las permutaciones de una matriz de tamaño 11 lleva unos 4 segundos. ¡Aunque podría considerarse impresionante, ya que la cantidad de permutaciones posibles de un conjunto de tamaño 11 es 11! que es casi 40 millones.

Lógicamente, con una matriz de tamaño 12, tomará alrededor de 12 veces más tiempo, ¡desde 12! es 11! * 12 11! * 12 , y con una matriz de tamaño 13 tomará alrededor de 13 veces más tiempo que el tiempo que tomó con el tamaño 12, y así sucesivamente.

Entonces, puedes entender fácilmente cómo con una matriz de 12 y más, realmente lleva mucho tiempo pasar por todas las permutaciones.

Y tengo la corazonada de que de alguna manera puedo cortar ese tiempo mucho (sin cambiar a un lenguaje distinto de C #, porque la optimización del compilador realmente se optimiza bastante bien, y dudo que pueda optimizarla tan bien, de forma manual, en Montaje).

¿Alguien sabe de otra manera de hacerlo más rápido? ¿Tiene alguna idea de cómo hacer que el algoritmo actual sea más rápido?

Tenga en cuenta que no quiero usar una biblioteca o servicio externo para hacer eso. Quiero tener el código en sí mismo y quiero que sea tan eficiente como sea humanamente posible.

Actualización 2018-05-28, una nueva versión, más rápida, de subprocesos múltiples ...

Time taken for fastest algorithms

Necesito: la solución Sani Singh Huttunen (lexico más rápido) y mi nueva OuelletLexico3 que admite indexación (donde una de sus ventajas simplifica la división de tareas para multihilo) ...

En mi máquina (6 núcleos hyperthread: 12 hilos) Xeon E5-1660 0 @ 3.30Ghz, prueba algoritmos que se ejecutan con cosas vacías que hacer para 13! elementos (tiempo en milisegundos):

  • 53071: Ouellet (implementación de Heap)
  • 65366: Sani Singh Huttunen (el lexico mas rapido)
  • 11377: Mix OuelletLexico3 - Sani Singh Huttunen

Una nota al margen: el uso compartido de propiedades / variables entre subprocesos para la acción de permutación tendrá un gran impacto en el rendimiento si su uso es una modificación (lectura / escritura). Si lo hace, generará un " intercambio falso " entre los hilos, no obtendrá el rendimiento esperado. Obtuve este comportamiento durante la prueba (principalmente cuando trato de aumentar la variable global para el recuento total de permutación).

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

Aquí hay un buscador de permutación genérico que iterará a través de cada permutación de una colección y llamará a una función de evaluación. Si la función de evaluación devuelve verdadero (encontró la respuesta que estaba buscando), el buscador de permutación detiene el procesamiento.

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

Aquí hay una implementación simple:

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

Aquí hay una implementación recursiva con complejidad O(n * n!) 1 basada en el intercambio de los elementos de una matriz. La matriz se inicializa con 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]); } } } }

En cada paso recursivo intercambiamos el último elemento con el elemento actual señalado por la variable local en el ciclo for y luego indicamos la singularidad del intercambio al: incrementar la variable local del ciclo for y disminuir la condición de terminación del loop, que inicialmente se establece en el número de elementos en la matriz, cuando este último se convierte en cero, terminamos la recursión.

Aquí están las funciones de ayuda:

//----------------------------------------------------------------------------- /* 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. ¡Hay n! permutaciones de n elementos para imprimir.

Bueno, si puedes manejarlo en C y luego traducirlo a tu idioma de elección, no puedes ir mucho más rápido que esto, porque el tiempo estará dominado por la 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);

El algoritmo de permutación más rápido que conozco es el algoritmo QuickPerm.
Aquí está la implementación, utiliza el retorno de rendimiento para que pueda iterar uno a la vez como sea necesario.

Código:

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

Esto podría ser lo que estás buscando.

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

Aquí está la implementación más rápida con la que terminé:

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

Uso y rendimiento de prueba:

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

Método de impresión:

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

Profundizando:

Ni siquiera pensé en esto durante mucho tiempo, así que solo puedo explicar mi código, pero aquí está la idea general:

  1. Las permutaciones no son lexicográficas; esto me permite prácticamente realizar menos operaciones entre permutaciones.
  2. La implementación es recursiva, y cuando el tamaño de "vista" es 3, omite la lógica compleja y solo realiza 6 intercambios para obtener las 6 permutaciones (o submutaciones, si se quiere).
  3. Debido a que las permutaciones no están en un orden lexicográfico, ¿cómo puedo decidir qué elemento llevar al inicio de la "vista" actual (sub permutación)? Guardo registro de los elementos que ya se utilizaron como "iniciadores" en la llamada recursiva de subpermutación actual y simplemente busco linealmente uno que no se usó en la cola de mi matriz.
  4. La implementación solo se aplica a los enteros, de modo que para permutar una colección genérica de elementos, simplemente usa la clase Permutations para permutar los índices en lugar de su colección real.
  5. El Mutex está ahí solo para garantizar que las cosas no se atornillen cuando la ejecución es asincrónica (observe que puede pasar un parámetro UnsafeAction que a su vez obtendrá un puntero a la matriz permutada. No debe cambiar el orden de los elementos en esa matriz (puntero)! Si lo desea, debe copiar la matriz a una matriz tmp o simplemente usar el parámetro de acción segura que se ocupa de eso para usted; la matriz pasada ya es una copia).

Nota:

No tengo idea de qué tan buena es esta implementación, no la he tocado en tanto tiempo. Pruebe y compare con otras implementaciones por su cuenta, y avíseme si tiene algún comentario.

Disfrutar.

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

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

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

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.

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

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

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.

// 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://.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; } };

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