Создание перестановок набора (наиболее эффективно)

Я хотел бы сгенерировать все перестановки набора (коллекции), например:

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

Это не вопрос «как», в общем, а больше о том, как наиболее эффективно. Кроме того, я бы не хотел генерировать все перестановки и возвращать их, но только генерировал единую перестановку за раз и продолжал только при необходимости (подобно Итераторам, которые я тоже пробовал, но оказался меньше эффективная).

Я проверил множество алгоритмов и подходов и придумал этот код, который наиболее эффективен из тех, что я пробовал:

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

Это использование будет посылать массив элементов и возвращать логическое значение, указывающее, была ли это последней лексикографической перестановкой или нет, а также с изменением массива на следующую перестановку.

Пример использования:

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

Дело в том, что меня не устраивает скорость кода.

Итерация по всем перестановкам массива размером 11 занимает около 4 секунд. Хотя это можно считать впечатляющим, так как количество возможных перестановок из набора 11 составляет 11! что составляет около 40 миллионов.

Логически, с массивом размером 12, это займет около 12 раз больше времени, начиная с 12! это 11! * 12 11! * 12 , и с массивом размера 13 это займет примерно в 13 раз больше времени, чем время, затраченное на размер 12, и так далее.

Таким образом, вы можете легко понять, как с помощью массива размером от 12 и более требуется очень много времени, чтобы пройти через все перестановки.

И у меня есть сильная догадка, что я могу как-то сократить время (не переключаясь на язык, отличный от C #), потому что оптимизация компилятора действительно оптимизирована довольно красиво, и я сомневаюсь, что я мог бы оптимизировать как хорошо, вручную, в Assembly).

Кто-нибудь знает какой-либо другой способ сделать это быстрее? Есть ли у вас какие-либо идеи относительно того, как быстрее выполнять текущий алгоритм?

Обратите внимание, что я не хочу использовать внешнюю библиотеку или службу для этого – я хочу иметь сам код, и я хочу, чтобы он был настолько эффективным, насколько это было возможно по-человечески.

    Обновление 2018-05-28:

    • Ниже приведена новая многопоточная версия (быстрее).
    • Также статья о перестановке: Перестановки: быстрые реализации и новый алгоритм индексирования, позволяющий multithreading

    Немного поздно …

    Согласно последним испытаниям (обновлено 2018-05-22)

    • Самый быстрый мой, но не в лексикографическом порядке
    • Для быстрого лексикографического порядка решение Сани Сингха Хаттунена, похоже, является для него способом.

    Результаты теста производительности для 10 элементов (10!) В выпуске на моей машине (миллисекунды):

    • Ouellet: 29
    • SimpleVar: 95
    • Эрез Робинсон: 156
    • Сани Сингх Хаттунен: 37
    • Pengyang: 45047

    Результаты теста производительности для 13 элементов (13!) В выпуске на моей машине (в секундах):

    • Ouellet: 48,437
    • SimpleVar: 159.869
    • Эрез Робинсон: 327,781
    • Сани Сингх Хаттунен: 64.839

    Преимущества моего решения:

    • Алгоритм кучи (Single swap на перестановку)
    • Нет умножения (например, некоторые реализации, видимые в Интернете)
    • Встроенный обмен
    • общий
    • Небезопасный код
    • На месте (очень низкая память)
    • Нет modulo (только сравнение первого бит)

    Моя реализация алгоритма Кучи :

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

    Это мой тестовый код:

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

    Примеры использования:

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

    Это может быть то, что вы ищете.

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

    Ну, если вы можете справиться с этим на C, а затем перевести на ваш язык выбора, вы не можете пойти гораздо быстрее, чем это, потому что на время будет преобладать 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 

    Самый быстрый алгоритм перестановки, который я знаю, является алгоритмом QuickPerm.
    Вот реализация, она использует возврат доходности, чтобы вы могли повторять одно за раз, как это требуется.

    Код:

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

    Вот самая быстрая реализация, с которой я столкнулся:

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

    Использование и тестирование:

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

    Способ печати:

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

    Идти глубже:

    Я даже не думал об этом в течение очень долгого времени, поэтому я могу только объяснить свой код так много, но вот общая идея:

    1. Перестановки не лексикографические - это позволяет мне практически выполнять меньше операций между перестановками.
    2. Реализация является рекурсивной, и когда размер «представления» равен 3, он пропускает сложную логику и просто выполняет 6 свопов, чтобы получить 6 перестановок (или под-перестановок, если хотите).
    3. Поскольку перестановки не находятся в лексикографическом порядке, как я могу решить, какой элемент нужно довести до начала текущего «представления» (субперестановка)? Я сохраняю запись элементов, которые уже использовались в качестве «стартеров» в текущем рекурсивном вызове подмножеств и просто выполняются линейно для одного, который не использовался в хвосте моего массива.
    4. Реализация предназначена только для целых чисел, поэтому для перестановки над общим набором элементов вы просто используете class Permutations для перестановки индексов вместо фактической коллекции.
    5. Mutex существует только для обеспечения того, чтобы все не зависало, когда выполнение является асинхронным (обратите внимание, что вы можете передать параметр UnsafeAction, который, в свою очередь, получит указатель на перенастроенный массив. Вы не должны изменять порядок элементов в этом массиве (указатель)! Если вы хотите, вы должны скопировать массив в массив tmp или просто использовать безопасный параметр действия, который позаботится об этом для вас - переданный массив уже является копией).

    Заметка:

    Я понятия не имею, насколько хороша эта реализация на самом деле - я так долго ее не трогал. Испытайте и сравните с другими реализациями самостоятельно, и дайте мне знать, если у вас есть обратная связь!

    Наслаждаться.

    Вот общий подстановочный элемент, который будет перебирать каждую перестановку коллекции и вызывать функцию evalution. Если функция evalution возвращает true (она нашла ответ, который она искала), искатель перестановки прекратит обработку.

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

    Вот простая реализация:

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

    Вот рекурсивная реализация со сложностью O(n * n!) 1 на основе замены элементов массива. Массив инициализируется значениями от 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]); } } } } 

    На каждом рекурсивном шаге мы заменяем последний элемент текущим элементом, на который указывает локальная переменная в цикле for а затем указываем уникальность подкачки: увеличивая локальную переменную цикла for и уменьшая условие завершения for цикл, который изначально установлен на число элементов в массиве, когда последний обращается в нуль, мы завершаем рекурсию.

    Вот вспомогательные функции:

      //----------------------------------------------------------------------------- /* 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. Есть n! перестановки n элементов для печати.

    Обновление 2018-05-28, новая версия, самая быстрая … (многопоточная)

    введите описание изображения здесь

      Time taken for fastest algorithms 

    Нужна: решение Sani Singh Huttunen (самое быстрое лексико) и мой новый OuelletLexico3, который поддерживает индексирование

    У индексации есть 2 основных преимущества:

    • позволяет напрямую перенести любую перестановку
    • позволяет multithreading (полученная из первого преимущества)

    Статья: Перестановки: быстрые реализации и новый алгоритм индексирования, позволяющий multithreading

    На моей машине (6 гипертекстовых ядер: 12 streamов) Xeon E5-1660 0 @ 3,30Ghz, тесты алгоритмов работают с пустым материалом, который нужно делать за 13! пункты (время в миллисекундах):

    • 53071: Ouellet (реализация кучи)
    • 65366: Сани Сингх Хаттунен (Самый быстрый лексико)
    • 11377: Mix OuelletLexico3 – Сани Сингх Хаттунен

    Замечание: использование свойств / переменных ресурсов между streamами для действия перестановки сильно повлияет на производительность, если их использование является модификацией (чтение / запись). Это приведет к генерации « ложного обмена » между streamами, вы не получите ожидаемой производительности. Я получил это поведение во время тестирования (в основном, когда я пытаюсь увеличить глобальную переменную для общего количества перестановок).

    Применение:

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

    Код:

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

    Вы называете это следующим образом:

     var permutations = ContrivedUtils.Permutations("1234".ToCharArray()); // output is: 24 var permutations = ContrivedUtils.Permutations("123456789".ToCharArray()); // output is: 362880 
    Давайте будем гением компьютера.