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.
Usage example:
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.
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.
Logically, with an array of size 12 it will take about 12 times more time, since 12! is 11! * 12 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.
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.
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.
A little bit too late...
According to my tests, my implementation of Heap's algorithm seems to give fastest performance...
Performance test results for 12 items (12!) in release on my machine:
- 1453051904 items in 10728 millisecs ==> My implementation of Heap (code included)
- 1453051904 items in 18053 millisecs ==> SimpleVar
- 1453051904 items in 85355 millisecs ==> Erez Robinson
Advantages:
My implementation of Heap's algorithm:
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];
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");
}
}
}
An this is my test code:
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");
});
Usage examples:
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;
});
这可能是你正在寻找的。
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;
}
那么，如果你可以用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);
上一篇: 在Haskell中递归排列
下一篇: 生成一组排列（最有效）