Ich möchte alle Permutationen einer Menge (einer Sammlung) wie folgt generieren:

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

Dies ist im Allgemeinen keine Frage des "Wie", sondern eher der Effizienz. Außerdem möchte ich nicht ALLE Permutationen generieren und zurückgeben, sondern nur jeweils eine Permutation generieren und nur bei Bedarf fortsetzen (ähnlich wie Iteratoren - die ich auch ausprobiert habe, die sich jedoch als weniger erwiesen haben effizient).

Ich habe viele Algorithmen und Ansätze getestet und bin auf diesen Code gekommen, der von denen, die ich ausprobiert habe, am effizientesten ist:

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

Es wird ein Array von Elementen gesendet und ein Boolescher Wert zurückgegeben, der angibt, ob dies die letzte lexikografische Permutation war oder nicht. Außerdem wird das Array auf die nächste Permutation geändert.

Anwendungsbeispiel:

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

PrintArray(arr);

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

Die Sache ist, dass ich mit der Geschwindigkeit des Codes nicht zufrieden bin.

Das Durchlaufen aller Permutationen eines Arrays der Größe 11 dauert ungefähr 4 Sekunden. Obwohl es als beeindruckend angesehen werden könnte, da die Menge der möglichen Permutationen einer Menge von Größe 11 beträgt11! Das sind fast 40 Millionen.

Logischerweise wird es mit einem Array der Größe 12 ungefähr 12-mal länger dauern, da12! ist11! * 12und mit einem Array der Größe 13 dauert es ungefähr 13-mal länger als mit Größe 12, und so weiter.

Sie können also leicht nachvollziehen, wie lange es bei einem Array ab Größe 12 wirklich dauert, alle Permutationen zu durchlaufen.

Und ich habe eine starke Vermutung, dass ich diese Zeit irgendwie um ein Vielfaches verkürzen kann (ohne zu einer anderen Sprache als C # zu wechseln - weil die Compileroptimierung wirklich sehr gut funktioniert und ich bezweifle, dass ich sie manuell in Assembly so gut optimieren kann).

Kennt jemand einen anderen Weg, um das schneller zu erledigen? Haben Sie eine Idee, wie Sie den aktuellen Algorithmus beschleunigen können?

Beachten Sie, dass ich dafür keine externe Bibliothek oder einen externen Dienst verwenden möchte. Ich möchte den Code selbst haben und ihn so effizient wie möglich gestalten.