Я хотел бы сгенерировать все перестановки набора (коллекции), например:
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 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 секунд.
Хотя это можно считать впечатляющим, так как количество возможных перестановок набора размеров 11 составляет 11!, что составляет около 40 миллионов.
Логически, с массивом размера 12 потребуется примерно в 12 раз больше времени, так как 12! - 11! * 12, а с массивом размером 13 потребуется примерно в 13 раз больше времени, чем время, затрачиваемое на размер 12 и т.д.
Итак, вы можете легко понять, как с помощью массива размером от 12 и более требуется очень много времени, чтобы пройти через все перестановки.
И у меня есть сильная догадка, что я могу как-то сократить время (не переключаясь на язык, отличный от С#), потому что оптимизация компилятора действительно оптимизирует довольно красиво, и я сомневаюсь, что я мог бы оптимизировать как хорошо, вручную, в Монтаж).
Кто-нибудь знает какой-либо другой способ сделать это быстрее? Есть ли у вас какие-либо идеи относительно того, как быстрее выполнять текущий алгоритм?
Обратите внимание, что я не хочу использовать внешнюю библиотеку или службу для этого - я хочу иметь сам код, и я хочу, чтобы он был настолько эффективным, насколько это было возможно по-человечески.
Спасибо, что прочитал все!:)
