Add your own alternative version
Stats
332.4K views 16.3K downloads 191 bookmarked
Posted
13 May 2008

Comments and Discussions



Thanks Adrian. I think I can reduce the set by ranking the 650 elements by their average value (actually weighted average) and then take the highest and lowest n elements into combinations.
Regards
Ian





Thanks a lot for this nice package!
On my 3.0 GHz PC, I've measured the following for your Permutation generator:
n loops/minute
4 2,97E+05
5 1,22E+06
6 5,66E+06
7 1,78E+07
8 9,98E+07
9 2,61E+08
10 3,31E+08
11 4,46E+08
12 6,32E+08
Permutations<int>pp = new Permutations<int>(inputSet);
long f = 0;
foreach (IList<int> il in pp)
{
f++;
}
The increase in speed with growing values for n is probably due to the relative decrease in object creations per loop.
I've tried to switch code optimization on and off in my VS C# 10 Express.
But the effect was not clear.
Greetings!
Axel Kemper





Axel,
I made sure to optimize this algorithm as I intended it to be general purpose. My focus was on the GetNext method of the enumerator. I did not focus on the initial setup of the collection or the enumerator. So, I think your conclusion would be correct. In fact, if your outer loop (not shown in your example) wraps the creations of the Permutations object then you will (from memory) be paying for a list copy each time.
Cheers, Adrian





Congrats! Your permutation code outperformed all others I came across. Thank you!





My Anagram app for Windows Phone 7 is using this code (packed it in a Silverlight library)
http://www.windowsphone.com/enUS/apps/69d9ac0207fe48e08086cd9ee1884dd4[^]
Thanks a lot!
I packed the files in a Silverlight for Windows Phone class library (named Combinatorics) and modification I had to do was to
1) make the IMetaCollection interface public so that I could abstract the use of any combinatorics operation based on user selection
2) add CombinatoricsOp class to help with using any combinatorics operation via one entry point
As a bonus there is also a Combinatorics.cd there (class diagram)
You can download the library to use with your WP7 Silverlight apps (or repack source into other library project for other targets) from:
https://skydrive.live.com/redir.aspx?cid=2335bbef59b92c54&resid=2335BBEF59B92C54!1705&parid=2335BBEF59B92C54!386[^]
Please give due credit to original author of Combinatorics code (and myself if you use my additions too).
The code for CombinatoricsOp class I added is below. Just call GetCombinatoricsOp to get a Permutations, Combinations or Variations class instance (all implement IMetaCollection interface) and then use the enumerator (with extra method to get count of items without counting them onebyone) as described in this CodeProject article.
using System;
using System.Collections.Generic;
namespace Facet.Combinatorics
{
public static class CombinatoricsOp {
public enum CombinatoricsOpType
{
Permutations = 0,
PermutationsWithRepetition = 1,
Combinations = 2,
CombinationsWithRepetition = 3,
Variations = 4,
VariationsWithRepetition = 5
}
public static IMetaCollection<string> GetCombinatoricsOp(IList<string> values, CombinatoricsOpType opType, int take){
switch (opType)
{
case CombinatoricsOpType.Permutations:
return new Permutations<string>(values);
case CombinatoricsOpType.PermutationsWithRepetition:
return new Permutations<string>(values,GenerateOption.WithRepetition);
case CombinatoricsOpType.Combinations:
return new Combinations<string>(values, take);
case CombinatoricsOpType.CombinationsWithRepetition:
return new Combinations<string>(values, take, GenerateOption.WithRepetition);
case CombinatoricsOpType.Variations:
return new Variations<string>(values, take);
case CombinatoricsOpType.VariationsWithRepetition:
return new Variations<string>(values, take, GenerateOption.WithRepetition);
default:
throw new NotImplementedException();
}
}
}
}
Computer & Informatics Engineer
Microsoft MVP J# 20042010
Borland "Spirit of Delphi" 2001
QuickTime, QTVR, Delphi VCL,
ActiveX, COM, .NET, Robotics
http://zoomicon.com
http://zoomicon.wordpress.com
modified 2Dec11 11:16am.





George,
Thanks for letting me know that you've used this in a project. I'm glad it came in handy, I'll have to look up the app on my phone.
Cheers,
Adrian





Hi again Adrian,
since I'm building an update for the Anagram app (to make it available to more platforms like Win8, Android, iOS), I've separated the Combinatorics part (your code + my small additions) as a PCL (Portable Class Library) and a Windows Phone 8 library (not really needed because of the PCL, but will look into adding a WP7.x lib too with Visual Studio 2012, since at Visual Studio 2013 you can't create PCLs targeting WP7 at the moment, only WP8)
Microsoft didn't have option there for custom license or CPOL, so I selected MSPL (I sometimes also use MIT license which is very simple) which should be similar. Hope you're ok with it (see License tab at the link below)
the library is at
https://combinatorics.codeplex.com/[^]
I used Mercurial repository option at CodePlex (prefer using TortoiseHg in Windows Explorer and VisualHg plugin for Visual Studio than TortoiseGit and VS2013's Git support which I don't like much)
if you have (or want to make) a Codeplex account I can add you to project admins too if you tell me the user id you use there
Computer & Informatics Engineer
Microsoft MVP J# 20042010
Borland Spirit of Delphi 2001
QuickTime, QTVR, Delphi VCL,
ActiveX, COM, .NET, Robotics
http://zoomicon.com
http://zoomicon.wordpress.com





George,
A PCL version sounds like a good idea. I'm glad this is being put to good use.
My CodePlex account is aakison, I'd be happy to join and maybe even make some enhancements I've been meaning to do.
Cheers, Adrian





Hi again Adrian, glad you approve
added you to the project team on codeplex as 2nd coordinator
Computer & Informatics Engineer
Microsoft MVP J# 20042010
Borland Spirit of Delphi 2001
QuickTime, QTVR, Delphi VCL,
ActiveX, COM, .NET, Robotics
http://zoomicon.com
http://zoomicon.wordpress.com





very thorough treatment, both in math and in code





Hoping I can get a free probability lesson here and hoping I can use this code.
Here is what I need the code to do. I have any number of sets and each set has any number of values. I want to get every "combination" of these sets. For example:
Set A: {A.S1, A.S2}
Set B: {B.S1}
Set C: {C.S1, C.S2, C.S3};
I want to get every combination of Set A with Set B with Set C. The calculation would be 2 * 1 * 3 so I would end up with 6 possible outcomes and the result would be:
1. A.S1 B.S1 C.S1
2. A.S1 B.S1 C.S2
3. A.S1 B.S1 C.S3
4. A.S2 B.S1 C.S1
5. A.S3 B.S1 C.S2
6. A.S3 B.S1 C.S3
Can I do this with this code base?





The specific example that you provide doesn't really amount to a permutation problem. It seems that your solution would just be:
foreach(var a in setA) {
foreach(var b in setB) {
foreach(var c in setC) {
... {a, b, c};
}
}
}
I feel, however, that you may have oversimplified the question and that this answer will fall short.
Cheers,
Adrian





+5 Very useful, and really appreciate the full explanations, and background, and souces included.
thanks, Bill
"In the River of Delights, Panic has not failed me." Jorge Luis Borges





Hi,
I have used this excellent library to generate all combinations of a given set (of all sizes)
input set: a, b, c
output: a, b, c, ab, ac, bc, abc
This is not a problem.
However when the input set is big (say 40 items), then generating everything takes a rather long time.
Is it possible to let this run on more cores (everything now runs one 1 core and I have 8 in my machine)?
Thanks,
Ike





Interesting question, I hadn't thought about this before. When I wrote it I implemented 3 different algorithms and checked each for performance on a single core processor. So, I considered performance important but back then didn't even have a multicore processor.
Unfortunately, the algorithms that are well known for this use the content of the current permutation to assist with the generation of the next permutation. As such, they need to be calculated sequentially. Further, I implemented combinations and variations using the permutation, so this issue applies to all of the items.
If it were to be ported to a multithreaded implementation, there would be issues with getting information back. It would be expensive in terms of space to store all of the calculated values before returning them. So, the question is whether we want all the permutations in order, or just all the permutations. While having the permutations in a prescribed order is nice (and sometimes necessary), I'll assume that the need is not for them to be in order.
So, an idea springs to mind. I'll use permutations against {a, b, c, d, e, f, g, h} as my sample set which would have 8! = 40320 permutations.
First, If I were to take each value out as the first entry and then do the permutations of the remaining 7 I'd have:
a {b, c, d, e, f, g, h}
b {a, c, d, e, f, g, h}
...
h {a, b, c, d, e, f, g}
I could then run each of these 8 permutation problems simultaneously on 8 cores. Overhead should be small so we'd get close to 8X performance.
As a quick double check, I'm getting 8 results of 7! each out, which is 8 * 7! = 8 * 5040 = 40320.
Second, for combinations, there is an underlying permutation of values 1 and 0 to determine membership in a combination. For example a 8 choose 3 combination of {a, b, c, d, e, f, g, h} creates an underlying permutation without repetition on {1, 1, 1, 0, 0, 0, 0, 0}. For this we first compute 8 choose 1 (a smaller set) on the master thread and then spawn off smaller subsets to worker threads. The first subset would combine {a} with {b, c, d, e, f, g, h}, the second would combine {b} with {c, d, e, f, g, h} and so forth. Here, the worker threads would have varying amounts of work so the heavier laden threads would need to spawn off smaller computations again to get some form of load balancing.
The benefit of these mechanisms is that they could be overlaid on top of the current library instead of reimplementing the current library.
Hope this helps...





Hi Adrian,
Thanks for the info.
I ran a quick testprogram and just wanted to return back with the results.
Below you'll find the testcode.
"Normal": is the normal code I wrote (using only 1 core)
"Attempt1": is actually slower than "Normal"
"Attempt2": ran about 2 times faster than "Normal"
"Attempt3": ran about 3 times faster than "Normal"
Best regards,
Ike
var chars = "abcdefghijklmnopqrstuvwx".ToCharArray();
var count = chars.Length + 1;
// normal
for (int i = 0; i < count; ++i)
{
var combinations = new Combinatorics.Combinations(chars, i);
foreach (var combination in combinations)
combination.ToString();
}
// attempt1
for (int j = 0; j < count; ++j)
{
var combinations = new Combinatorics.Combinations(chars, j);
Parallel.ForEach(combinations, combination => combination.ToString());
}
// attempt2
Parallel.For(1, count, delegate(int k)
{
var combinations = new Combinatorics.Combinations(chars, k);
Parallel.ForEach(combinations, combination => combination.ToString());
});
// attempt3
Parallel.For(1, count, delegate(int l)
{
var combinations = new Combinatorics.Combinations(chars, l);
foreach (var combination in combinations)
{
combination.ToString();
}
});





Thanks for this article. I am currently implementing a solution for the Traveling Salesman Problem and while creating the code for the standard algorithm that needs all permutations of all cities a faced that this is not a trivial problem. Your article saved me a lot of time.





For my application I would like the following behaviour, doesn't seem to be able to do it.
Lets say I have {1, 2, 2}
I want all unique variations of this set to be output,
1 2 2
2 1 2
2 2 1
Currently I'm using variations (order important) but each 2 is always treated as an individual token, so am getting
1 2 2
1 2 2 < the 2's above have been swapped, but same variation as above.
2 1 2
2 1 2
etc
Of course I can perform duplicate detection outside of the library call but inside would be much more ideal.
Am I right to think this behaviour isn't supported?
thanks.





What you are looking for is a Permutation, not a Variation. If you pass {1, 2, 2} into permutation with the WithoutRepetitions options, you will get what you want.
int[] ints = { 1, 2, 2 };
Permutations<int> permutations = new Permutations<int>(ints, GenerateOption.WithoutRepetition);
foreach(IList<int> permutation in permutations) {
foreach(int element in permutation) {
}
}
Note that if you're using .NET 4 and the var keyword, the enumerator will not work properly for permutations as there is a bug in the code. I've fixed it and submitted to Code Project, but they haven't posted the changes.





Thanks for the prompt reply and yes I can see that satisfies my example.
But, silly me I provided a bad example
For my set I am retrieving for all lengths 1 to n and so using a loop for each length.
For 1 to n
get all variations for length n
process...
next n
As permuations don't allow a length parameter I'm using variations. I just tested for the last length n and it does give the required resultset as you said it would.
I'm trying to think of a way that uses a double call, one to get the < n subsets and then to permutate those. But variations are a form of that, so not sure it's so easy.
Adrian, is there a special reason permutations don't allow length to be specified as the others do? I suppose the algorithm is simplified without it, but formally speaking should a permutation always be of set length n?
(BTW did get the var error, IList works)
Update:
This is the offending line here I believe in the class description of the Variations class
"The equality of multiple inputs is not considered when generating variations."
So the following
var variations = new Facet.Combinatorics.Variations<int>(new List<int> {1, 2, 2}, 2, Facet.Combinatorics.GenerateOption.WithoutRepetition);
generates
1 2 < 1 with the first 2
1 2 < 1 with the second 2
2 1
2 1
2 2
2 2





Ok, I get your general problem. I think what you're looking for is to first get the combinations of your set with the appropriate lower index. This will get all the possible subsets that you're looking for. In your example, you'd want the combinations without repetition. Then for each of those subsets, generate all of the permutations, again without repetitions.
var combinations = new Combinations<int>(new List<int> {1, 2, 2}, 2, GenerateOption.WithoutRepetition);
foreach(var combination in combinations) {
var permutations = new Permutations<int>(combination, GenerateOption.WithoutRepetition);
foreach(var permutation in permutations) {
}
}
I don't have Visual Studio handy, so the above is just a guess. (Also, please remember the problem with permutations that the CodeProject is not updating. Make sure that the generic enumerator is public and the nongeneric is explicit, and it will work.)
Hope this helps,
Adrian





Thanks for replying Adrian.
Unfortunately that still doesn't work.
The line,
var combinations = new Combinations<int>(new List<int> {1, 2, 2}, 2, GenerateOption.WithoutRepetition);
will generate (1, 2) and (2, 1) twice each, one for each 2 in the set.
The WithRepetition option will allow the 1 to be used twice (1, 1), and WithoutRepetition is suppressing that behaviour but not suppressing the duplicate combinations resulting from duplicate members in the original set.
I think what I want which can be summed as "unique variations where duplicate members exist" just isn't supported. It's not such a big deal and I'm handling the duplicates outside.
I spent a bit of time looking for that particular algorithm and didn't come up with much, I imagine that's because it's not easy to do efficiently (without needing to match against previous results e.g. hash tracking).
modified on Sunday, April 3, 2011 9:53 AM





Very useful and elegantly written.






Hi,
it is possible to let Combinations (WithoutRepetitions) to begin from a known combination set?
So if I have 0,1,2,4,5,6,7,8,9,10 with a lower index of 4
to begin from 0,3,6,9 and continue generation from this point?
thank you so much in advance.
very good job.





This is truly excellent it's just what I have been looking for, I had almost given up on finding a good solution for Variations. Thanks for posting this.





I have an old program with old code that I need to update to C# and here is the answer on how to replace the section of code written long ago by the more mathmatical partner I had then.
Thanks






Very useful algorithm, it's much appreciated!





Excellent article Adrian, this is exactly what I needed!
If I may just make a small suggestion: in Permutations<T> class, instead of...
public virtual IEnumerator GetEnumerator() {
return new Enumerator(this);
}
IEnumerator<IList<T>> IEnumerable<IList<T>>.GetEnumerator() {
return new Enumerator(this);
}
...perhaps you should do something like this...
IEnumerator IEnumerable.GetEnumerator() {
return GetEnumerator();
}
public IEnumerator<IList<T>> GetEnumerator() {
return new Enumerator(this);
}
This would enable the client to, instead of writing...
foreach (IList<T> p in new Permutations<T>(inputSet)) {
}
...simply write...
foreach (var p in new Permutations<T>(inputSet)) {
}
...and would also (slightly) improve the performance (no more casting between object and IList<T> ).





Too right! Thanks.
Obviously got the signature right in the Combinations and Variations classes, but missed it in Permutations.






I believe the following equation for variations is wrong:
V(n,k) = C(n, k) / P(k) = (n! / ( k! * (n  k)! )) / k! = n! / (n  k)!.
It should be:
V(n,k) = C(n, k) * P(k) = (n! / ( k! * (n  k)! )) * k! = n! / (n  k)!.
I guess you could call this an "unmistake" since you start off with the wrong equation
but after some mathematical steps containing an error you end up with the correct
equation! If only life worked that way more often.
Regards,
Ralph Boland





You are absolutely right! Two years before someone caught that.
I've submitted the changes to CodeProject, but once they edit a article they lock out my ability to directly modify it.
Thanks for bring this up.
Adrian





Just for the history (in case others read this discussion), seems from Revisions tab that they must have fixed it (11Aug10 lists a change)
Computer & Informatics Engineer
Microsoft MVP J# 20042007
Borland "Spirit of Delphi"
QuickTime, QTVR, Delphi VCL,
ActiveX, COM, .NET, Robotics
http://www.kagi.com/birbilis
http://birbilis.spaces.live.com






Moim Hossain
R&D Project Manager
BlueCielo ECM Solutions BV





Thanks for the excellent article.
The combination class you have created works like this:
Combinations of {a,b,c}:
{a,b,c}
{c,b,a}
{a,c,b}
{b,c,a}
{b,a,c}
{c,a,b}
The mathmatical combination will approach it as a set and calculates these results:
{a}
{b}
{c}
{a,b}
{a,c}
{b,c}
{a,b,c}
I am not sure about the exact term for this type of combination. Do you think it is possible to extend your classes to support this operation?
Thanks for sharing,
Holger





Firstly, a correction to your post. The "Combinations" that I coded do not work the way you specify, rather the "Permutations" work that way. Calculating combinations requires that a lower index is also known which is the size of the output set. Evaluating all possible lower indexes against your set would result in the following:
Combinations of {a, b, c} choose 0:
{} (trivially)
Combinations of {a, b, c} choose 1:
{a}, {b}, {c}
Combinations of {a, b, c} choose 2:
{a,b}, {a,c}, {b,c}
Combinations of {a, b, c} choose 3:
{a,b,c}
It appears that WolframAlpha (the site you linked to) is merging all of these results together as the lower index was not specified.
So, to get the result you are looking for, loop through all possible lower indexes and merge the results of each combination set.





Your combination class works perfectly. I did not understand the purpose of the lower index. This helps a lot to investigate a problem I am working on. Thanks for your clarification.
IList<int> ObjectIdList = new List<int>();
ObjectIdList.Add(1);
ObjectIdList.Add(2);
ObjectIdList.Add(3);
ObjectIdList.Add(5);
ObjectIdList.Add(7);
for (int i = ObjectIdList.Count; i > 0; i)
{
Combinations<int> c = new Combinations<int>(ObjectIdList, i);
foreach (IList<int> p in c)
{
foreach (int ObjectId in p)
{
Console.Write(String.Format("{0} ", ObjectId));
}
Console.WriteLine("");
}
}





Hi,
it's been a quite busy day and maybe I'm just too stupid and/or tired to see it right now , but:
If I modify your Combinations example to
char[] inputSet = { 'A', 'B', 'C', 'D', 'E' };
Combinations<char> co = new Combinations<char>(inputSet, 3);
foreach (IList<char> c in co)
{
Console.WriteLine(String.Format("{{{0} {1} {2}}}", c[0], c[1], c[2]));
}
I get duplicate combinations and a total of 120 (instead of just 10, namely ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE and CDE).
Am I doing something wrong..?
Best regards,
Hendrik.





Firstly, I agree there are only 10 combinations of 5 items choose 3. However, when I copied and pasted your sample it worked correctly and displayed 10 items. However, since Permutations of 5 items would come up with 120, could you possibly have two test methods and they've got their wires crossed?
Thanks for the feedback, obviously I'm still concerned if there is an issue and if we can find a reproducible one I will put it in my test cases and resolve it.
Cheers, Adrian





Hi Adrian,
thanks for your reply.
You are right, everything's working as it should  as long as it is not modified by stupid people like me!
Before using Combinations, I was using the Permutations class with some objects that do not implement IComparable and I just wanted them to be treated differently. So I modified Permuations.Initialize(IList<T> values, GenerateOption type, IComparer<T> comparer) to check if something implements IComparable. Too bad I did it wrong! And, yes: GenerateOptions.WithRepetion does the trick ...
Anyways, this affected Combinations, as I just found out by debugging through the code.
So, sorry for the trouble, my fault!
Cheers,
Hendrik.





That makes perfect sense. I spent a good deal of time implementing 3 different permutation algorithms, each using 2 or 3 different language mechanisms to get the most efficiency out of permutations. Having done that I didn't feel like tuning Combinations and Variations, so they are implemented using the underlying permutations class.
Glad you found your issue. Cheers. Adrian.





class Program
{
static void Main(string[] args)
{
per("abcdef");
Console.ReadLine();
}
static void per(string st)
{
per("",st );
}
static void per(string pref, string st)
{
if (st.Length == 1)
{
Console.Write(pref + st);
Console.WriteLine();
}
else
{
int l = st.Length;
for (int i = 0; i < l; i++)
{
char buf = st[i];
string newSt = st.Substring(0, i) + st.Substring(i + 1); ;
per(pref + buf, newSt);
}
}
}
}






Thanks for this wonderful code, Adrian. I have found it very useful.
However, I was a bit confused by one aspectthe distinction between Variations and Permutations. As far as I can tell, Variations are just Permutations where you can specify the number of elements to "choose". Wouldn't it make more sense to eliminate the Variations class and just have Combinations and Permutations, and make it such that you can specify the number of elements to "choose" in the Permutations constructor, just like you can for Combinations?
Craig





Thank you for your comments, I'm glad you've found a use for it.
To your comment about the relation between Variations and Permutations, you are correct. I hope that I spelled out that Variations are just Permutations of Combinations in the article. In fact, if you look at the Variations code, you'll see that it is implemented using Permutations.
Designwise it could have been done in a single monolithic class. I chose to separate the classes to more closely align with the names in the literature on the subject.
Thanks again for your feedback.





like if I want to get the all the combinations between index = 100~1000,
how can I do that? (foreach cannot do that.)
thank you very much.
Sean.





The algorithm that I used does not lend itself to finding the specific permutation at a given index. For example, the following is NOT valid:
var permutations = ...;
for(int i = 100; i < 1000; ++i) {
var permutation = permutations[i];
}
It would be possible to do the following, but it does require the calculation of the first 100 permutations which are then thrown away:
var permutations = ...;
for(int i = 0; i < 1000; ++i) {
permutations.MoveNext();
}
for(int i = 100; i < 1000; ++i) {
permutations.MoveNext();
var permutation = permutations.Current;
}
Sorry this is not the cleanest nor most efficient way of achieving your goal.







General News Suggestion Question Bug Answer Joke Praise Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

