生成集合的排列(最有效) [英] 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).
我测试了许多算法和方法，并提出了以下代码，这是我尝试过的最有效的代码:
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);
}
问题是我对代码的速度不满意.
The thing is that I'm not happy with the speed of the code.
迭代大小为 11 的数组的所有排列大约需要 4 秒.尽管这可能令人印象深刻，因为一组大小为 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# 以外的语言 - 因为编译器优化确实优化得非常好，我怀疑我是否可以手动优化，在组装).
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?
请注意，我不想使用外部库或服务来做到这一点 - 我想要代码本身，并且我希望它尽可能高效.
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.
推荐答案
2018-05-28 更新:
Update 2018-05-28:
- 下面提供了一个新的多线程版本(速度更快)作为另一个答案.
- 还有一篇关于排列的文章:排列:快速实现和允许多线程的新索引算法
有点晚了...
根据最近的测试(2018-05-22更新)
According to recent tests (updated 2018-05-22)
- 最快的是我的，但不是按字典顺序排列的
- 对于最快的字典顺序，Sani Singh Huttunen 解决方案似乎是可行的方法.
在我的机器上发布的 10 个项目 (10!) 的性能测试结果(毫秒):
Performance test results for 10 items (10!) in release on my machine (millisecs):
- 欧莱特:29
- 简单变量:95
- 埃雷兹罗宾逊:156
- Sani Singh Huttunen:37
- 彭阳:45047
在我的机器上发布的 13 个项目(13 个！)的性能测试结果(秒):
Performance test results for 13 items (13!) in release on my machine (seconds):
- 欧莱特:48.437
- 简单变量:159.869
- 埃雷兹罗宾逊:327.781
- Sani Singh Huttunen:64.839
我的解决方案的优点:
- 堆算法(单交换排列)
- 没有乘法(就像在网络上看到的一些实现)
- 内联交换
- 通用
- 没有不安全的代码
- 就地(非常低的内存使用量)
- 无模(仅第一位比较)
我对堆算法的实现:
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;
namespace WpfPermutations
{
/// <summary>
/// EO: 2016-04-14
/// Generator of all permutations of an array of anything.
/// Base on Heap's Algorithm. See: https://en.wikipedia.org/wiki/Heap%27s_algorithm#cite_note-3
/// </summary>
public static class Permutations
{
/// <summary>
/// Heap's algorithm to find all pmermutations. Non recursive, more efficient.
/// </summary>
/// <param name="items">Items to permute in each possible ways</param>
/// <param name="funcExecuteAndTellIfShouldStop"></param>
/// <returns>Return true if cancelled</returns>
public static bool ForAllPermutation<T>(T[] items, Func<T[], bool> funcExecuteAndTellIfShouldStop)
{
int countOfItem = items.Length;
if (countOfItem <= 1)
{
return funcExecuteAndTellIfShouldStop(items);
}
var indexes = new int[countOfItem];
// Unecessary. Thanks to NetManage for the advise
// for (int i = 0; i < countOfItem; i++)
// {
// indexes[i] = 0;
// }
if (funcExecuteAndTellIfShouldStop(items))
{
return true;
}
for (int i = 1; i < countOfItem;)
{
if (indexes[i] < i)
{ // On the web there is an implementation with a multiplication which should be less efficient.
if ((i & 1) == 1) // if (i % 2 == 1) ... more efficient ??? At least the same.
{
Swap(ref items[i], ref items[indexes[i]]);
}
else
{
Swap(ref items[i], ref items[0]);
}
if (funcExecuteAndTellIfShouldStop(items))
{
return true;
}
indexes[i]++;
i = 1;
}
else
{
indexes[i++] = 0;
}
}
return false;
}
/// <summary>
/// This function is to show a linq way but is far less efficient
/// From: StackOverflow user: Pengyang : http://stackoverflow.com/questions/756055/listing-all-permutations-of-a-string-integer
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="list"></param>
/// <param name="length"></param>
/// <returns></returns>
static IEnumerable<IEnumerable<T>> GetPermutations<T>(IEnumerable<T> list, int length)
{
if (length == 1) return list.Select(t => new T[] { t });
return GetPermutations(list, length - 1)
.SelectMany(t => list.Where(e => !t.Contains(e)),
(t1, t2) => t1.Concat(new T[] { t2 }));
}
/// <summary>
/// Swap 2 elements of same type
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="a"></param>
/// <param name="b"></param>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void Swap<T>(ref T a, ref T b)
{
T temp = a;
a = b;
b = temp;
}
/// <summary>
/// Func to show how to call. It does a little test for an array of 4 items.
/// </summary>
public static void Test()
{
ForAllPermutation("123".ToCharArray(), (vals) =>
{
Console.WriteLine(String.Join("", vals));
return false;
});
int[] values = new int[] { 0, 1, 2, 4 };
Console.WriteLine("Ouellet heap's algorithm implementation");
ForAllPermutation(values, (vals) =>
{
Console.WriteLine(String.Join("", vals));
return false;
});
Console.WriteLine("Linq algorithm");
foreach (var v in GetPermutations(values, values.Length))
{
Console.WriteLine(String.Join("", v));
}
// Performance Heap's against Linq version : huge differences
int count = 0;
values = new int[10];
for (int n = 0; n < values.Length; n++)
{
values[n] = n;
}
Stopwatch stopWatch = new Stopwatch();
ForAllPermutation(values, (vals) =>
{
foreach (var v in vals)
{
count++;
}
return false;
});
stopWatch.Stop();
Console.WriteLine($"Ouellet heap's algorithm implementation {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
count = 0;
stopWatch.Reset();
stopWatch.Start();
foreach (var vals in GetPermutations(values, values.Length))
{
foreach (var v in vals)
{
count++;
}
}
stopWatch.Stop();
Console.WriteLine($"Linq {count} items in {stopWatch.ElapsedMilliseconds} millisecs");
}
}
}
这是我的测试代码:
Task.Run(() =>
{
int[] values = new int[12];
for (int n = 0; n < values.Length; n++)
{
values[n] = n;
}
// Eric Ouellet Algorithm
int count = 0;
var stopwatch = new Stopwatch();
stopwatch.Reset();
stopwatch.Start();
Permutations.ForAllPermutation(values, (vals) =>
{
foreach (var v in vals)
{
count++;
}
return false;
});
stopwatch.Stop();
Console.WriteLine($"This {count} items in {stopwatch.ElapsedMilliseconds} millisecs");
// Simple Plan Algorithm
count = 0;
stopwatch.Reset();
stopwatch.Start();
PermutationsSimpleVar permutations2 = new PermutationsSimpleVar();
permutations2.Permutate(1, values.Length, (int[] vals) =>
{
foreach (var v in vals)
{
count++;
}
});
stopwatch.Stop();
Console.WriteLine($"Simple Plan {count} items in {stopwatch.ElapsedMilliseconds} millisecs");
// ErezRobinson Algorithm
count = 0;
stopwatch.Reset();
stopwatch.Start();
foreach(var vals in PermutationsErezRobinson.QuickPerm(values))
{
foreach (var v in vals)
{
count++;
}
};
stopwatch.Stop();
Console.WriteLine($"Erez Robinson {count} items in {stopwatch.ElapsedMilliseconds} millisecs");
});
使用示例:
ForAllPermutation("123".ToCharArray(), (vals) =>
{
Console.WriteLine(String.Join("", vals));
return false;
});
int[] values = new int[] { 0, 1, 2, 4 };
ForAllPermutation(values, (vals) =>
{
Console.WriteLine(String.Join("", vals));
return false;
});
这篇关于生成集合的排列(最有效)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
