生成集合的排列(最有效)
生成集合的排列(最有效)
提问于 2012-06-26 21:31:59
我想生成一个集合(一个集合)的所有排列，如下所示：
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的数组将花费大约13倍的时间，以此类推。
所以你可以很容易地理解，对于一个大小为12或更大的数组，完成所有的排列确实需要很长的时间。
我有一种强烈的预感，我可以以某种方式将这一时间减少很多(而不需要切换到C#以外的语言-因为编译器优化确实可以很好地优化，我怀疑我能否在汇编中手动优化)。
有没有人知道其他更快的方法呢？你有关于如何使当前算法更快的想法吗？
请注意，我不想使用外部库或服务来实现这一点--我想拥有代码本身，并且希望它在人力上尽可能高效。
回答 9
Stack Overflow用户
发布于 2012-06-26 21:37:04
这可能就是你要找的。
private static bool NextPermutation(int[] numList)
{
/*
Knuths
1. Find the largest index j such that a[j] < a[j + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l such that a[j] < a[l]. Since j + 1 is such an index, l is well defined and satisfies j < l.
3. Swap a[j] with a[l].
4. Reverse the sequence from a[j + 1] up to and including the final element a[n].
*/
var largestIndex = -1;
for (var i = numList.Length - 2; i >= 0; i--)
{
if (numList[i] < numList[i + 1]) {
largestIndex = i;
break;
}
}
if (largestIndex < 0) return false;
var largestIndex2 = -1;
for (var i = numList.Length - 1 ; i >= 0; i--) {
if (numList[largestIndex] < numList[i]) {
largestIndex2 = i;
break;
}
}
var tmp = numList[largestIndex];
numList[largestIndex] = numList[largestIndex2];
numList[largestIndex2] = tmp;
for (int i = largestIndex + 1, j = numList.Length - 1; i < j; i++, j--) {
tmp = numList[i];
numList[i] = numList[j];
numList[j] = tmp;
}
return true;
}Stack Overflow用户
发布于 2012-06-27 02:23:53
好吧，如果你能用C语言处理它，然后翻译成你选择的语言，你不可能比这更快，因为时间将由print支配
void perm(char* s, int n, int i){
if (i >= n-1) print(s);
else {
perm(s, n, i+1);
for (int j = i+1; j<n; j++){
swap(s[i], s[j]);
perm(s, n, i+1);
swap(s[i], s[j]);
}
}
}
perm("ABC", 3, 0);Stack Overflow用户
发布于 2013-06-18 03:00:23
下面是一个通用的置换查找器，它将遍历集合的每个置换并调用一个求值函数。如果计算函数返回true (它找到了它正在寻找的答案)，则置换查找程序停止处理。
public class PermutationFinder<T>
{
private T[] items;
private Predicate<T[]> SuccessFunc;
private bool success = false;
private int itemsCount;
public void Evaluate(T[] items, Predicate<T[]> SuccessFunc)
{
this.items = items;
this.SuccessFunc = SuccessFunc;
this.itemsCount = items.Count();
Recurse(0);
}
private void Recurse(int index)
{
T tmp;
if (index == itemsCount)
success = SuccessFunc(items);
else
{
for (int i = index; i < itemsCount; i++)
{
tmp = items[index];
items[index] = items[i];
items[i] = tmp;
Recurse(index + 1);
if (success)
break;
tmp = items[index];
items[index] = items[i];
items[i] = tmp;
}
}
}
}下面是一个简单的实现：
class Program
{
static void Main(string[] args)
{
new Program().Start();
}
void Start()
{
string[] items = new string[5];
items[0] = "A";
items[1] = "B";
items[2] = "C";
items[3] = "D";
items[4] = "E";
new PermutationFinder<string>().Evaluate(items, Evaluate);
Console.ReadLine();
}
public bool Evaluate(string[] items)
{
Console.WriteLine(string.Format("{0},{1},{2},{3},{4}", items[0], items[1], items[2], items[3], items[4]));
bool someCondition = false;
if (someCondition)
return true; // Tell the permutation finder to stop.
return false;
}
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/11208446
复制相关文章
相似问题
腾讯云开发者
