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

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

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

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

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

PrintArray(arr);

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

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

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

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

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

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

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

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