Permutationen eines Sets erzeugen (am effizientesten)

Möglicherweise suchen Sie dies.

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

Wenn Sie es in C handhaben und dann in Ihre Sprache übersetzen können, können Sie nicht viel schneller als dies gehen, da print die Zeit dominiert:

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

Der schnellste Permutationsalgorithmus, den ich kenne, ist der QuickPerm-Algorithmus.
Hier ist die Implementierung, sie verwendet Rendite-Rendite, so dass Sie sie nach Bedarf wiederholen können.

Code:

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

        var yieldRet = new T[N];

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

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

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

                //MAIN!

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

                // MAIN!

                p[i]++; // increase index "weight" for i by one
                i = 1; // reset index i to 1 (assumed)
            }
            else
            {
                // otherwise p[i] == i
                p[i] = 0; // reset p[i] to zero
                i++; // set new index value for i (increase by one)
            } // if (p[i] < i)
        } // while(i < N)
    }

Hier ist die schnellste Implementierung, mit der ich endete:

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

Verwendung und Testleistung:

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

Druckverfahren:

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

Tiefer gehen:

Ich habe nicht lange darüber nachgedacht, daher kann ich meinen Code nur so viel erklären, aber hier ist die allgemeine Idee:

1. Permutationen sind nicht lexikografisch - dadurch kann ich praktisch weniger Operationen zwischen Permutationen durchführen.
2. Die Implementierung ist rekursiv, und wenn die "view" -Größe 3 ist, wird die komplexe Logik übersprungen und es werden nur 6 Swaps ausgeführt, um die 6 Permutationen (oder Sub-Permutationen, wenn Sie so wollen) zu erhalten.
3. Wie kann ich entscheiden, welches Element an den Anfang der aktuellen "Ansicht" (Unterpermutation) gebracht wird, da die Permutationen nicht in einer lexikografischen Reihenfolge liegen? Ich protokolliere Elemente, die bereits als "Starter" im rekursiven Aufruf der aktuellen Sub-Permutation verwendet wurden, und suche einfach linear nach einem Element, das im Ended meines Arrays nicht verwendet wurde.
4. Die Implementierung ist nur für Ganzzahlen. Um eine generische Sammlung von Elementen zu permutieren, verwenden Sie einfach die Permutations-Klasse, um Indizes anstelle der tatsächlichen Collection zu permutieren.
5. Der Mutex dient nur dazu, sicherzustellen, dass bei asynchroner Ausführung keine Fehler auftreten (beachten Sie, dass Sie einen UnsafeAction-Parameter übergeben können, der wiederum einen Zeiger auf das permutierte Array erhält. Sie dürfen die Reihenfolge der Elemente in diesem Array nicht ändern.) (Zeiger)! Wenn Sie möchten, sollten Sie das Array in ein tmp-Array kopieren oder einfach den sicheren Aktionsparameter verwenden, der dies für Sie erledigt - das übergebene Array ist bereits eine Kopie.

Hinweis:

Ich habe keine Ahnung, wie gut diese Implementierung wirklich ist - ich habe sie so lange nicht angerührt ... Testen und vergleichen Sie andere Implementierungen auf eigene Faust und lassen Sie mich wissen, ob Sie Feedback haben!

Genießen.

Hier ist ein generischer Permutations-Finder, der jede Permutation einer Collection durchläuft und eine Evaluierungsfunktion aufruft. Wenn die Auswertungsfunktion true zurückgibt (sie hat die gesuchte Antwort gefunden), stoppt der Permutationsfinder die Verarbeitung. 

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

Hier ist eine einfache Implementierung:

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

Update 2018-05-28, eine neue Version, die schnellste ... (Multithread)

                            Time taken for fastest algorithms

Bedarf: Sani Singh Huttunen (schnellste Lexiko) -Lösung und mein neues OuelletLexico3, das die Indizierung unterstützt

Die Indizierung hat zwei Hauptvorteile: 

• ermöglicht es, jedermann direkt Permutation zu erhalten
• erlaubt Multithreading (abgeleitet vom ersten Vorteil) 

Artikel: Permutationen: Schnelle Implementierungen und ein neuer Indexierungsalgorithmus, der Multithreading ermöglicht

Auf meinem Rechner (6 Hyperthread-Kerne: 12 Threads) Xeon E5-1660 0 @ 3.30Ghz, testet Algorithmen, die mit leerem Zeug für 13 laufen! Artikel (Zeit in Millisekunden):

• 53071: Ouellet (Implementierung von Heap)
• 65366: Sani Singh Huttunen (schnellster Lexikon)
• 11377: Mix OuelletLexico3 - Sani Singh Huttunen

Eine Randnotiz: Die Verwendung von Eigenschaften/Variablen von Shares zwischen Threads für die Permutationsaktion wirkt sich stark auf die Leistung aus, wenn ihre Verwendung eine Änderung (Lesen/Schreiben) ist. Dadurch wird " false sharing " zwischen Threads generiert. Sie werden keine erwartete Leistung erhalten. Ich habe dieses Verhalten beim Testen erhalten. Meine Erfahrung zeigte Probleme, wenn ich versuche, die globale Variable für die Gesamtzahl der Permutation zu erhöhen.

Verwendungszweck:

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

Code:

using System;
using System.Runtime.CompilerServices;

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

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

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

            return FactorialTable[val];
        }

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

    }
}


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

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

            if (largestIndex < 0) return false;

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

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

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

            return true;
        }
    }
}


using System;

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

        private bool[] _valueUsed;

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

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

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

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

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

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

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

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

            long factorielLower = MaxIndex;

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

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

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

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

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


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

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

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

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

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

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

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

            long index = _indexFirst;

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

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

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

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

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

            var tasks = new List<Task>();

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

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

                if (stopIndex == itemsFactorial)
                {
                    break;
                }

                startIndex = startIndex + partCount;
            }

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

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


    }
}

Hier ist eine rekursive Implementierung mit Komplexität O(n * n!)¹ basierend auf dem Tauschen der Elemente eines Arrays. Das Array wird mit Werten aus 1, 2, ..., n initialisiert. 

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

Bei jedem rekursiven Schritt tauschen wir das letzte Element mit dem aktuellen Element aus, auf das die lokale Variable in der for Schleife zeigt, und geben dann die Eindeutigkeit des Swaps an, indem: die lokale Variable der for Schleife inkrementiert wird und das Dekrementieren der Beendigungsbedingung der for Schleife, die anfänglich auf die Anzahl der Elemente in dem Array gesetzt ist, wenn letztere zu Null wird, beenden wir die Rekursion.

Hier sind die Hilfsfunktionen:

    //-----------------------------------------------------------------------------
    /*
        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. Es gibt n! Permutationen von n Elementen, die gedruckt werden sollen.}

In Steven Skienas Algorithm Design Manual (Kapitel 14.4 in der zweiten Auflage) finden Sie eine Einführung in die Algorithmen und einen Überblick über Implementierungen.

Skiena referenziert D. Knuth. Die Kunst der Computerprogrammierung, Band 4 Fascicle 2: Alle Tupel und Permutationen erzeugen. Addison Wesley, 2005.

Ich wäre überrascht, wenn es wirklich Verbesserungen in der Größenordnung gibt. Wenn dies der Fall ist, muss C # grundlegend verbessert werden. Darüber hinaus erfordert das Arbeiten mit der Permutation im Allgemeinen mehr Arbeit als das Generieren. Daher werden die Erzeugungskosten im Gesamtschema der Dinge unbedeutend sein.

Ich würde jedoch vorschlagen, die folgenden Dinge auszuprobieren. Sie haben bereits Iteratoren ausprobiert. Aber haben Sie versucht, eine Funktion zu haben, die eine Schließung als Eingabe annimmt und diese Schließung dann für jede gefundene Permutation aufruft? Abhängig von den internen Mechanismen von C # kann dies schneller sein.

Haben Sie in ähnlicher Weise versucht, eine Funktion zu verwenden, die eine Schließung zurückgibt, die eine bestimmte Permutation durchläuft?

Bei beiden Methoden gibt es eine Reihe von Mikrooptimierungen, mit denen Sie experimentieren können. Sie können zum Beispiel Ihr Eingabe-Array sortieren, und danach wissen Sie immer, in welcher Reihenfolge es ist. Zum Beispiel können Sie ein Array von Bools haben, das angibt, ob dieses Element weniger als das nächste ist, und anstelle von Vergleichen können Sie dies einfach tun Schau dir das Array an.

Da der Autor dieser Frage nach einem Algorithmus gefragt hat:

[...] eine einzelne Permutation zu einem Zeitpunkt generieren und nur bei Bedarf fortsetzen 

Ich würde vorschlagen, den Steinhaus-Johnson-Trotter-Algorithmus in Betracht zu ziehen.

Steinhaus-Johnson-Trotter-Algorithmus auf Wikipedia

Schön erklärt hier

Ich habe einen Algorithmus erstellt, der etwas schneller als der von Knuth ist:

11 Elemente:

mine: 0,39 Sekunden 

Knuths: 0,624 Sekunden

13 Elemente:

mine: 56,615 Sekunden 

Knuths: 98,681 Sekunden

Hier ist mein 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]++;
        }
    }
}

Das Problem ist, dass mein Algorithmus nur für eine ungerade Anzahl von Elementen funktioniert. Ich habe diesen Code schnell geschrieben, daher bin ich mir ziemlich sicher, dass es eine bessere Möglichkeit gibt, meine Idee zu implementieren, um eine bessere Leistung zu erzielen, aber ich habe nicht wirklich die Zeit, daran zu arbeiten, um es zu optimieren und das Problem zu lösen, wenn die Anzahl der Versionen von Elemente ist gerade.

Es ist ein Swap für jede Permutation, und es verwendet eine wirklich einfache Methode, um zu wissen, welche Elemente ausgetauscht werden sollen.

Ich habe in meinem Blog eine Erklärung der Methode hinter dem Code geschrieben: http://antoinecomeau.blogspot.ca/2015/01/fast-generation-of-all-permutations.html

Es ist 1 Uhr morgens, und ich habe ferngesehen und an dieselbe Frage gedacht, allerdings mit Stringwerten. 

Bei einem gegebenen Wort finden Sie alle Permutationen. Sie können dies leicht ändern, um ein Array, Sets usw. zu bearbeiten.

Ich brauchte ein bisschen, um das herauszufinden, aber ich kam auf folgende Lösung:

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

Hier ist derselbe Code wie oben, jedoch mit einigen Kommentaren

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

        }
    }
}

Ich habe dieses Algo auf Rosetta-Code gefunden und es ist wirklich das schnellste, das ich versucht habe. 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);
}