Генерирование перестановки набора (наиболее эффективно) ⇐ C#

[Anonymous]

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

Collection: 1, 2, 3
Permutations: {1, 2, 3}
{1, 3, 2}
{2, 1, 3}
{2, 3, 1}
{3, 1, 2}
{3, 2, 1}
< /code>

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

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;

// Check if the current element is less than the one before it
if (curr.CompareTo(elements) < 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;

// 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 = 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;
elements = 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;
}
< /code>

Это использование будет посылать множество элементов, и возвращение логического, указывающего на то, была ли это последняя лексикографическая перестановка или нет, а также изменение массива на следующую перестановку.var arr = new[] {1, 2, 3};

PrintArray(arr);

while (!NextPermutation(arr))
{
PrintArray(arr);
}
< /code>

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

Итерация по всем перестановкам массива размера 11 занимает около 4 секунд.
Хотя его можно считать впечатляющим, так как количество возможных перестановки на набор 11 -го размера 11! < /code>, который составляет почти 40 миллионов. /> Логически, с массивом размера 12, это займет около 12 раз больше времени, с 12! < /code> - 11! * 12 < /code>, и с массивом размера 13 это займет около 13 раз больше времени, чем время, которое потребовалось с размером 12, и т. Д. Переход на язык, отличный от C# - Поскольку оптимизация компилятора действительно хорошо оптимизируется, и я сомневаюсь, что я мог бы оптимизировать как хороший, вручную, в сборке). < /p>

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

Подробнее здесь: https://stackoverflow.com/questions/112 ... fficiently