生成集合的排列(最有效)
我想生成一个集合(集合)的所有排列，如下所示:
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秒钟。
虽然它可以被认为是令人印象深刻的，因为一组大小11的可能排列的数量是 11!，这是近4000万。
从逻辑上讲，如果数组的大小是12，那么花费的时间就会多出12倍，因为 12!是 11! * 12，而如果数组的大小是13，那么花费的时间就会比大小为12的时间多出13倍，以此类推。
所以你可以很容易地理解，当数组的大小为12或更大时，要完成所有的排列真的需要很长的时间。
而且我有一个强烈的预感，我可以在某种程度上大大缩短这个时间(不用切换到 C # 以外的语言——因为编译器最佳化确实可以很好地优化，而且我怀疑我可以在 Assembly 中手动优化得那么好)。
有人知道其他更快完成的方法吗？ 你知道如何让现有的算法更快吗？
请注意，我不想使用外部库或服务来做到这一点-我希望有代码本身，我希望它尽可能高效。
最佳答案