产生一组排列（最有效） [英] Generating permutations of a set (most efficiently)
问题描述
我想生成一组的所有排列（集合），像这样：
I would like to generate all permutations of a set (a collection), like so:
Collection: 1, 2, 3
Permutations: {1, 2, 3}
{1, 3, 2}
{2, 1, 3}
{2, 3, 1}
{3, 1, 2}
{3, 2, 1}
这是不是关于如何做，在一般情况下，但更多的是如何最有效的问题。 另外，我不希望产生的所有排列，并返回他们，但只产生一个单一的排列，在同一时间，并继续只在必要时（就像迭代 - 我已经尝试为好，但原来是少高效的）。
This isn't a question of "how", in general, but more about how most efficiently. Also, I wouldn't want to generate ALL permutations and return them, but only generating a single permutation, at a time, and continuing only if necessary (much like Iterators - which I've tried as well, but turned out to be less efficient).
我测试过很多算法和方法，并想出了这个code，这是最有效的那些我试过的：
I've tested many algorithms and approaches and came up with this code, which is most efficient of those I tried:
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;
}
它的使用将被发送元件的阵列，并且取回一个布尔值，表示这是否是最后辞书置换或没有，以及具有改变到下一个排列的阵列。
It's usage would be sending an array of elements, and getting back a boolean indicating whether this was the last lexicographical permutation or not, as well as having the array altered to the next permutation.
用例：
var arr = new[] {1, 2, 3};
PrintArray(arr);
while (!NextPermutation(arr))
{
PrintArray(arr);
}
的事情是，我不是很满意的code的速度。
The thing is that I'm not happy with the speed of the code.
遍历规模11阵列的所有排列大约需要4秒。
虽然这可以被视为IM pressive，因为一组11号的可能的排列金额 11！这是近4000万美元。
Iterating over all permutations of an array of size 11 takes about 4 seconds.
Although it could be considered impressive, since the amount of possible permutations of a set of size 11 is 11! which is nearly 40 million.
从逻辑上讲，大小为12的数组，这将需要约12倍以上的时间，因为 12！是 11！ * 12 ，系统和与尺寸13的阵列将需要比它与尺寸12，等花时间约13倍更多的时间。
Logically, with an array of size 12 it will take about 12 times more time, since 12! is 11! * 12, and with an array of size 13 it will take about 13 times more time than the time it took with size 12, and so on.
所以，你可以很容易地理解如何与大小12多阵列，它确实需要很长的时间去通过所有排列。
So you can easily understand how with an array of size 12 and more, it really takes a very long time to go through all permutations.
和我有一种强烈的预感，我可以以某种方式通过大量削减那个时候（而无需切换到C＃以外语言 - 因为编译器优化确实很好地优化pretty的，我怀疑我可以优化为好，手动，在大会）。
And I have a strong hunch that I can somehow cut that time by a lot (without switching to a language other than C# - because compiler optimization really does optimize pretty nicely, and I doubt I could optimize as good, manually, in Assembly).
有谁知道任何其他方式弄完更快？ 你有什么想法，如何让当前的算法快？
Does anyone know any other way to get that done faster? Do you have any idea as to how to make the current algorithm faster?
请注意，我不想使用外部库或服务，才能做到这一点 - 我想有C本身的$ C $和我想这是高效力所能及的
Note that I don't want to use an external library or service in order to do that - I want to have the code itself and I want it to be as efficient as humanly possible.
感谢您阅读一切！ ：）
Thanks for reading everything! :)
推荐答案
这是最快的实现我结束了：
public class Permutations
{
private readonly Mutex _mutex = new Mutex();
private Action<int[]> _action;
private Action<IntPtr> _actionUnsafe;
private unsafe int* _arr;
private IntPtr _arrIntPtr;
private unsafe int* _last;
private unsafe int* _lastPrev;
private unsafe int* _lastPrevPrev;
public int Size { get; private set; }
public bool IsRunning()
{
return this._mutex.SafeWaitHandle.IsClosed;
}
public bool Permutate(int start, int count, Action<int[]> action, bool async = false)
{
return this.Permutate(start, count, action, null, async);
}
public bool Permutate(int start, int count, Action<IntPtr> actionUnsafe, bool async = false)
{
return this.Permutate(start, count, null, actionUnsafe, async);
}
private unsafe bool Permutate(int start, int count, Action<int[]> action, Action<IntPtr> actionUnsafe, bool async = false)
{
if (!this._mutex.WaitOne(0))
{
return false;
}
var x = (Action)(() =>
{
this._actionUnsafe = actionUnsafe;
this._action = action;
this.Size = count;
this._arr = (int*)Marshal.AllocHGlobal(count * sizeof(int));
this._arrIntPtr = new IntPtr(this._arr);
for (var i = 0; i < count - 3; i++)
{
this._arr[i] = start + i;
}
this._last = this._arr + count - 1;
this._lastPrev = this._last - 1;
this._lastPrevPrev = this._lastPrev - 1;
*this._last = count - 1;
*this._lastPrev = count - 2;
*this._lastPrevPrev = count - 3;
this.Permutate(count, this._arr);
});
if (!async)
{
x();
}
else
{
new Thread(() => x()).Start();
}
return true;
}
private unsafe void Permutate(int size, int* start)
{
if (size == 3)
{
this.DoAction();
Swap(this._last, this._lastPrev);
this.DoAction();
Swap(this._last, this._lastPrevPrev);
this.DoAction();
Swap(this._last, this._lastPrev);
this.DoAction();
Swap(this._last, this._lastPrevPrev);
this.DoAction();
Swap(this._last, this._lastPrev);
this.DoAction();
return;
}
var sizeDec = size - 1;
var startNext = start + 1;
var usedStarters = 0;
for (var i = 0; i < sizeDec; i++)
{
this.Permutate(sizeDec, startNext);
usedStarters |= 1 << *start;
for (var j = startNext; j <= this._last; j++)
{
var mask = 1 << *j;
if ((usedStarters & mask) != mask)
{
Swap(start, j);
break;
}
}
}
this.Permutate(sizeDec, startNext);
if (size == this.Size)
{
this._mutex.ReleaseMutex();
}
}
private unsafe void DoAction()
{
if (this._action == null)
{
if (this._actionUnsafe != null)
{
this._actionUnsafe(this._arrIntPtr);
}
return;
}
var result = new int[this.Size];
fixed (int* pt = result)
{
var limit = pt + this.Size;
var resultPtr = pt;
var arrayPtr = this._arr;
while (resultPtr < limit)
{
*resultPtr = *arrayPtr;
resultPtr++;
arrayPtr++;
}
}
this._action(result);
}
private static unsafe void Swap(int* a, int* b)
{
var tmp = *a;
*a = *b;
*b = tmp;
}
}
使用方法和性能测试：
var perms = new Permutations();
var sw1 = Stopwatch.StartNew();
perms.Permutate(0,
11,
(Action<int[]>)null); // Comment this line and...
//PrintArr); // Uncomment this line, to print permutations
sw1.Stop();
Console.WriteLine(sw1.Elapsed);
打印方式：
private static void PrintArr(int[] arr)
{
Console.WriteLine(string.Join(",", arr));
}
不断深入：
我压根没想到这个很长一段时间，所以我只能说明我的code这么多，但这里的总体思路：
I did not even think about this for a very long time, so I can only explain my code so much, but here's the general idea:
- 在排列是不是词典 - 这让我几乎排列的执行较少操作 。
- 的实施是递归的，而当视图大小是3，它跳过了复杂的逻辑，只是执行6互换得到6置换（或子排列，如果你愿意）。
- 由于排列是不是在字典顺序，我怎么能决定提请当前的视图（子排列）开始哪个元素？我把那些已经在当前的子排列递归调用作为启动器，只是线性搜索一个，这不是在我的数组的尾部使用的元素的记录。
- 的实施仅适用于整数，所以在重排元素的泛型集合只需使用置换类重排的实际收集的指标来代替。
- 互斥那里只是为了确保事情不就会上当受骗当执行是异步的（注意，您可以通过一个UnsafeAction参数又将获得一个指向排列的阵列，你不能改变元素的顺序该数组（指针）如果你想，你应该数组复制到TMP数组或只使用安全的行为参数，照顾了你！ - 传递的数组已经是复印件） 。
注意：
我不知道这个实现真正有多好 - 我没有碰过它这么久。 测试并比较其他实现你自己的，让我知道，如果您有任何意见！
I have no idea how good this implementation really is - I haven't touched it in so long. Test and compare to other implementations on your own, and let me know if you have any feedback!
享受。
这篇关于产生一组排列（最有效）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
