Generating permutations of a set (most efficiently)
Update 2018-05-28:
- A new multithreaded version (lot faster) is available below as another answer.
- Also an article about permutation: Permutations: Fast implementations and a new indexing algorithm allowing multithreading
A little bit too late...
According to recent tests (updated 2018-05-22)
- Fastest is mine BUT not in lexicographic order
- For fastest lexicographic order, Sani Singh Huttunen solution seems to be the way to go.
Performance test results for 10 items (10!) in release on my machine (millisecs):
- Ouellet : 29
- SimpleVar: 95
- Erez Robinson : 156
- Sani Singh Huttunen : 37
- Pengyang : 45047
Performance test results for 13 items (13!) in release on my machine (seconds):
- Ouellet : 48.437
- SimpleVar: 159.869
- Erez Robinson : 327.781
- Sani Singh Huttunen : 64.839
Advantages of my solution:
- Heap's algorithm (Single swap per permutation)
- No multiplication (like some implementations seen on the web)
- Inlined swap
- Generic
- No unsafe code
- In place (very low memory usage)
- No modulo (only first bit compare)
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];
// 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");
}
}
}
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;
});
Generating permutations of a set - efficiently and with distinction
With Swap algorithm to find permutations you can directly exclude the parts that produce duplicate permutations. This algorithm is available on internet and you can find more information about it.
private static void Main(string[] args)
{
List<int> set = new List<int>
{
20, 4, 3, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};
var permutes = Permute(set);
Console.WriteLine(permutes.Count); // outputs 58140
}
private static List<int[]> Permute(List<int> set)
{
List<int[]> result = new List<int[]>();
Action<int> permute = null;
permute = start =>
{
if (start == set.Count)
{
result.Add(set.ToArray());
}
else
{
List<int> swaps = new List<int>();
for (int i = start; i < set.Count; i++)
{
if (swaps.Contains(set[i])) continue; // skip if we already done swap with this item
swaps.Add(set[i]);
Swap(set, start, i);
permute(start + 1);
Swap(set, start, i);
}
}
};
permute(0);
return result;
}
private static void Swap(List<int> set, int index1, int index2)
{
int temp = set[index1];
set[index1] = set[index2];
set[index2] = temp;
}
Here is the image that shows how swap algorithm works.
So you have {A,B,C}, {A,C,B}, {B,A,C}, {B,C,A}, {C,B,A}, {C,A,B}
Now Consider A and B are equal. Ive edited the image with photoshop (sorry if im terrible at it!) And replaced B with A. As you can see in the image
Ive identified duplicates in image. If you skip them you will have {A,A,C}, {A,C,A}, {C,A,A}
You have to store items that are swapped so if the items are equal and we already had that swap we just skip to prevent dupes
if (swaps.Contains(set[i])) continue; // skip if we already done swap with this item
swaps.Add(set[i]); // else add it to the list of swaps.
For test if you delete this part then this algorithm will produce duplicate permutations and console will output n!.
Generating permutations of a set with controlled output?
One way to generate all 'permutations' one at the time in lexicographical order, without having to store them all in memory:
function permute_chars(alphabet, nword, nmax)
if nargin < 3 % default to displaying all, this can be a huge number!
nmax = nchar^nword;
end
nchar = length(alphabet);
ind = zeros(1, nword);
i = 0;
while i < nmax
% just printing the permutaions, edit according to your needs
disp(cell2mat(alphabet(ind + 1)));
% calculate next indices, classic elementary school addition with carry
ind(end) = ind(end) + 1;
for j = nword:-1:2
if ind(j) == nchar
ind(j) = 0; % wrap around
ind(j-1) = ind(j-1) + 1; % carry
end
end
i = i + 1;
end
For sure I am forgetting some obscure function which would allow to implement this in fewer lines, but written like this it is clear how it works. Quick test:
>> alphabet = {'a', 'b', 'c', 'd', 'e'};
>> permute_chars(alphabet, 1)
a
b
c
d
e
>> permute_chars(alphabet, 2)
aa
ab
ac
ad
ae
ba
[... snip ...]
ed
ee
Printing only a limited amount of permutations:
>> permute_chars(alphabet, 5, 8)
aaaaa
aaaab
aaaac
aaaad
aaaae
aaaba
aaabb
aaabc
How to generate only so many permutations more efficiently in C++?
As far as a I can tell, your result is numbers (without repeated digits) from 0 through some limit. Since you say you don't care about the order of the digits, it's probably easiest if we just stick to ascending ones. That being the case, we can generate results like this:
#include <iostream>
int main() {
for (int i=0; i<10; i++)
for (int j=i+1; j<10; j++)
for (int k=j+1; k<10; k++)
std::cout << i << j << k << "\t";
}
Result:
012 013 014 015 016 017 018 019 023 024 025 026 027
028 029 034 035 036 037 038 039 045 046 047 048 049
056 057 058 059 067 068 069 078 079 089 123 124 125
126 127 128 129 134 135 136 137 138 139 145 146 147
148 149 156 157 158 159 167 168 169 178 179 189 234
235 236 237 238 239 245 246 247 248 249 256 257 258
259 267 268 269 278 279 289 345 346 347 348 349 356
357 358 359 367 368 369 378 379 389 456 457 458 459
467 468 469 478 479 489 567 568 569 578 579 589 678
679 689 789
If your limit isn't a number of digits, you can put the digits together into an actual int and compare (then break out of the loops).
How to effectively store a large set of permutations?
Why not produce them lazily? Keep an index from each list, and when asked for a new element, you produce the combination on the fly. That way, you only need to store the initial list of source elements in memory plus indices at any time.
For example (if you need to iterate over the permutations):
-record(perm, {list_a, list_b, index_a, index_b}).
Everytime you reach the maximum of index_b, you reset it to 0 and increment index_a with one. Then, accessing the Nth element of the lists (where N is the indices) you can recreate any permutation instance.
Of course, this implies that you would have to traverse the lists each time a permutation is produced. To avoid this, you could use the lists as indices themselves:
-record(perm2, {list_a, list_b, list_b_orig}).
To generate the next permutation, pop the new element from list_b and append it to the head of list_a. If list_b is empty, remove the head of list_a and start over by setting list_b to the original which is saved in list_b_orig.
How do I generate all permutations of a list?
Use itertools.permutations from the standard library:
import itertools
list(itertools.permutations([1, 2, 3]))
Adapted from here is a demonstration of how itertools.permutations might be implemented:
def permutations(elements):
if len(elements) <= 1:
yield elements
return
for perm in permutations(elements[1:]):
for i in range(len(elements)):
# nb elements[0:1] works in both string and list contexts
yield perm[:i] + elements[0:1] + perm[i:]
A couple of alternative approaches are listed in the documentation of itertools.permutations. Here's one:
def permutations(iterable, r=None):
# permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
# permutations(range(3)) --> 012 021 102 120 201 210
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
if r > n:
return
indices = range(n)
cycles = range(n, n-r, -1)
yield tuple(pool[i] for i in indices[:r])
while n:
for i in reversed(range(r)):
cycles[i] -= 1
if cycles[i] == 0:
indices[i:] = indices[i+1:] + indices[i:i+1]
cycles[i] = n - i
else:
j = cycles[i]
indices[i], indices[-j] = indices[-j], indices[i]
yield tuple(pool[i] for i in indices[:r])
break
else:
return
And another, based on itertools.product:
def permutations(iterable, r=None):
pool = tuple(iterable)
n = len(pool)
r = n if r is None else r
for indices in product(range(n), repeat=r):
if len(set(indices)) == r:
yield tuple(pool[i] for i in indices)
Efficiently compute permutations of a given set of blocks in a line
One way to do this is to approach it recursively:
- If the minimum total length required to store all the blocks with exactly one space in-between them exceeds the available space, there are no ways to place the blocks.
- Otherwise, if you have no blocks to place, then the only way to place the blocks is to leave all squares unfilled.
- Otherwise, there are two options. First, you could place the first block at the first position in the row, then recursively place the remaining blocks in the remaining space within the row after first leaving one extra blank space at the start of the row. Second, you could leave the first space in the row blank, then recursively place the same set of blocks in the remaining space in the row. Trying out both options and combining the results back together should give you the answer you're looking for.
Translating this recursive logic into actual Java should not be too difficult. The code below is designed for readability and can be optimized a bit:
public List<String> allBlockOrderings(int rowLength, List<Integer> blockSizes) {
/* Case 1: Not enough space left. */
if (spaceNeededFor(blockSizes) > rowLength)) return Collections.EMPTY_LIST;
List<String> result = new ArrayList<String>();
/* Case 2: Nothing to place. */
if (blockSizes.isEmpty()) {
result.add(stringOf('.', rowLength));
} else {
/* Case 3a: place the very first block at the beginning of the row. */
List<String> placeFirst = allBlockOrderings(rowLength - blockSizes.get(0) - 1,
blockSizes.subList(1, blockSizes.length()));
for (String rest: placeFirst) {
result.add(stringOf('X', blockSizes.get(0)) + rest);
}
/* Case 3b: leave the very first spot open. */
List<String> skipFirst = allBlockOrderings(rowLength - 1, blockSizes);
for (String rest: skipFirst) {
result.add('.' + rest);
}
}
return result;
}
You'll need to implement the spaceNeededFor method, which returns the length of the shortest row that could possibly hold a given list of blocks, and the stringOf method, which takes in a character and a number, then returns a string of that many copies of the given character.
Hope this helps!
Efficient way to generate a seemingly random permutation from a very large set without repeating?
Thanks for the interesting question. You can create a "pseudorandom"* (cyclic) permutation with a few bytes using modular exponentiation. Say we have n elements. Search for a prime p that's bigger than n+1. Then find a primitive root g modulo p. Basically by definition of primitive root, the action x --> (g * x) % p is a cyclic permutation of {1, ..., p-1}. And so x --> ((g * (x+1))%p) - 1 is a cyclic permutation of {0, ..., p-2}. We can get a cyclic permutation of {0, ..., n-1} by repeating the previous permutation if it gives a value bigger (or equal) n.
I implemented this idea as a Go package. https://github.com/bwesterb/powercycle
package main
import (
"fmt"
"github.com/bwesterb/powercycle"
)
func main() {
var x uint64
cycle := powercycle.New(10)
for i := 0; i < 10; i++ {
fmt.Println(x)
x = cycle.Apply(x)
}
}
This outputs something like
0
6
4
1
2
9
3
5
8
7
but that might vary off course depending on the generator chosen.
It's fast, but not super-fast: on my five year old i7 it takes less than 210ns to compute one application of a cycle on 1000000000000000 elements. More details:
BenchmarkNew10-8 1000000 1328 ns/op
BenchmarkNew1000-8 500000 2566 ns/op
BenchmarkNew1000000-8 50000 25893 ns/op
BenchmarkNew1000000000-8 200000 7589 ns/op
BenchmarkNew1000000000000-8 2000 648785 ns/op
BenchmarkApply10-8 10000000 170 ns/op
BenchmarkApply1000-8 10000000 173 ns/op
BenchmarkApply1000000-8 10000000 172 ns/op
BenchmarkApply1000000000-8 10000000 169 ns/op
BenchmarkApply1000000000000-8 10000000 201 ns/op
BenchmarkApply1000000000000000-8 10000000 204 ns/op
Why did I say "pseudorandom"? Well, we are always creating a very specific kind of cycle: namely one that uses modular exponentiation. It looks pretty pseudorandom though.
Related Topics
How to Set Session Timeout in Web.Config
Prevent .Net Garbage Collection for Short Period of Time
How to Move and Resize a Form Without a Border
How to Know If a Datetime Is Between a Daterange in C#
Asynchronous Locking Based on a Key
How to Compile and Execute New Code at Runtime in .Net
Deserialize Collection of Interface-Instances
Write a Well Designed Async/Non-Async API
When Is a Static Constructor Called in C#
Two Different Dll with Same Namespace
Regular Expression to Remove HTML Tags
Transparent Background Image for Form - Smooth Edge Shape for the Form
Gradient Circles for Map Generator
Oledbcommand Parameters Order and Priority