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}

Esto no es una cuestión de "cómo", en general, sino más bien de qué manera es más eficiente. 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 (como los iteradores, que también he intentado, pero resultó ser menos) eficiente).

He probado muchos algoritmos y enfoques y encontré 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 serie de elementos y recuperar un valor booleano que indique si esta fue la última permutación lexicográfica o no, así como la modificación de la matriz a la siguiente permutación.

Ejemplo de uso:

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

PrintArray(arr);

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

La cosa es que no estoy contento con la velocidad del código.

La repetición de todas las permutaciones de una matriz de tamaño 11 lleva aproximadamente 4 segundos. Aunque podría considerarse impresionante, ya que la cantidad de posibles permutaciones de un conjunto de tamaño 11 es11! que es de casi 40 millones.

Lógicamente, con una matriz de tamaño 12 tomará aproximadamente 12 veces más tiempo, ya que12! es11! * 12, y con una matriz de tamaño 13, tomará aproximadamente 13 veces más tiempo que el tiempo que tomó con el tamaño 12, y así sucesivamente.

Por lo tanto, puede comprender fácilmente cómo con una matriz de tamaño 12 y más, realmente toma mucho tiempo pasar por todas las permutaciones.

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

¿Alguien sabe alguna otra manera de hacerlo más rápido? ¿Tienes 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í y quiero que sea lo más eficiente posible.