
Comments and Discussions



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.





thank you for replying...
it helps a lot..^_^





I was using your Permutations<T> class to attempt to generate the Permutations of a List<T> full of enums, when I learned that enum's do not implement IComparable<T>. My solution to make what I wanted to do work was this:
private class SelfComparer<U> : IComparer<U> {
public int Compare(U x, U y) {
if (x is IComparable<U>)
{
return ((IComparable<U>)x).CompareTo(y);
}
if (x is IComparable)
{
return ((IComparable)x).CompareTo(y);
}
throw new ArgumentException("Type does not implement either IComparable<T> or IComparable interfaces");
}
}
modified on Sunday, September 20, 2009 3:50 PM





Reasonably clever little trick. I never thought of supporting enums with this library.





Is it possible to regenerate a permutation by specifying an index ?
Like,
1. AB
2. BA
I want permutation number 2, it returns me BA.
Would it take time to regenerate it ?
Thank you,





Sorry for the late reply, I didn't get a email reminder about this post as my email address changed.
Anyway, there is no way to generate based on a specific index using these classes. I believe that the ability to select the n'th permutation could be done for certain specific inputs, but not as I've implemented it here.
Of course the brute force approach would work as:
permutations.Reset();
for(int i = 0; i < n; ++i) {
permutations.MoveNext();
}
// read n'th permutation here.
Sorry I couldn't be of more help.





Sorry, I didn't subscribe to notify too ...
I am going to look whether it's feasible or not,
Thank you.





This is an excellent group of classes, I put it into a class library and compiled it into a .DLL to reference it from any project.
However, you should upgrade it to even finding every combination including lowercase and capital combinations (mixed too).





I'm not sure I follow your suggestion. The library does support the ability to find all combinations or just those that are lexigraphically distinct. This is done through a constructor parameter. However, since you're referencing lowercase and uppercase, I guessing that you might mean the ability to treat lowercase and uppercase letters as identical when only detecting distinct combinations. If so, I think the best solution would be to use your own type that provides the comparison that you desire. For example:
public class CaselessChar : IComparable<CaselessChar> {
private char payload;
public override int Compare(CaselessChar rhs) {
return payload.ToUpper().Compare(rhs.ToUpper());
}
...
}
Hope this helps.





I mean when it finds every possible combination of characters from a character array, it finds every combination with capital and lowercase letters combined, example:
char[] inputSet = new char[] { "A", "B", "C", "D" };
and then first 4 of the output of using combinations, variations or permutations could be:
ABCD
aBCD
abCD
abcD
etc...





Thanks for taking the time to write this. It was very helpful!





The variations with repeats algorithm comes very close to solving the next question but it seems I'm stretching a tad bit further.
I don't know how to explain the issue so I'll show by example:
A list of 3 integers (values 0  2) with a lower index/size of 2 will return 9 variations:
(0,0)(0,1)(0,2)(1,0)(1,1)(1,2)(2,0)(2,1)(2,2)
What if there were multiple lists of integers (one with a size of 2, one with a size of 4) still keeping the lower index/size at two?
List one contains values (0,1) and list two contains values (0,1,2,3).
The results would be:
(0,0)(0,1)(0,2)(0,3)(1,0)(1,1)(1,2)(1,3)
I'm thinking this may not even be a true form of variations but it's whats required to get the job done.
Thanks





Excellent article, thanks for your efforts!
If I want to generate a list of all unique combinations without repeats, these algorithms work perfectly when we can keep it all in memory. I'm quickly running out of ram. Can these combinations be found while storing them to the hdd?
I'll have billions of combinations in the end.
EDIT:
Found the answer, I just had to store the results with a forloop to rom, simple answer for a simple question
modified on Sunday, June 14, 2009 8:31 PM





I found this page because I have been looking for a way to validate a players hand in a card game that I am making. I am making a Gun Rummy card game and there are countless combinations of cards that can make a valid hand. I have been told that this is one of the most (if not the most) complicated games to validate with a computer.
I have been looking for different solutions for almost a month and still am coming up empty on how to validate a players hand correcly.
Could this article be used to validate a card, hand? Do you have any information on how I could do this validation?





I think there would be some application of these algorithms when validating hands, but since the end result desired is just a boolean, iterating through millions of options would not be highly desirable. So, I can think of two direct applications of these classes that would determine if a hand had all 10 cards melded, neither of which I would use. And finally one that I would think would be effecient enough to use in a game.
As I understand the problem, identifying the melds can be difficult since a single card could be used in more than one meld. For example the seven cards {4H, 4D, 4S, 4C, 5C, 6C, 7C} could break into two different fully melded hands, first {{4H, 4D, 4S}, {4C, 5C, 6C, 7C}} and second {{4H, 4D, 4S, 4C}, {5C, 6C, 7C}}. There are also other melds in these seven cards that don't resolve fully melded hands, such as {4D, 4S, 4C}.
The first brute force method (that I wouldn't use) would be to take all Permutations of 10 cards, check the first three cards for a valid meld, the next three for a valid meld and finally the last four for a valid meld. This loop would iterate 10! = 3,628,800 times each time the hand changed.
The second, less forceful method (that I probably wouldn't use) would be to take the Combinations of 10 choose 3 cards and check for the first meld. This outer loop would only execute (10 choose 3) = 120 times. If and only if a meld is found, evaluate the remaining 7 cards with another Combination of 7 choose 3 cards. This inner loop would only iterate 35 times and would not be needed most of the time. Finally, check the last 4 cards for a meld to make the final determination. Worst case, the product of the two loops would be 4200 checks, but in practice would be much fewer.
Finally, we can make some observations about the cards that would make our lives easier if we apply some sorting and scanning. If we sort by rank (and ignore suit) we can easily determine the melds that are sets of like ranks, call these m1. (Note that a set of 4 will produce 5 possible melds). If we resort by suit and then rank, we can easily determine the melds that are runs, call these m2. (Note that a run of 4 will produce 3 possible melds). Then, we can union these two sets of melds together to see all possible melds in the hand. Worst case, a hand will have 10 possible melds at once. If three or more melds are found, use a Combination across the melds choosing 3 melds. If the count of unique cards within the combinationof3 meldset is 10, then the hand is fully melded. This algorithm is likely the most complex, but would have the best average case performance. Note also that the hard work of finding the melds in the sorted sequence is not handled by the classes presented here.
Hope this helps,
Adrian





I have the idea down but the fact that none of the programmers I have talked to thus far know how to play the game prevents them from providing me with a coded example.
I have tried several times and just can't wrap my head around it. I have a prototype application that probably isn't efficant but it gets the job done up until the last step and then it pukes.
I have also written a basic documentation that assigns a guaranteed unique numeric value to each card by drawing up an in memory card table. I think this is a better solution because it allows for working with numbers directly, maybe even binary level comparing.
I cannot post attachments here, but I wish I could get the document to you so you could see my idea. Its been a month of this issue and I'd just like to move on. I've set here for hours with a deck of cards in my hand. But when trying to represent this, my code always comes up short by missing a few combinations here or there, or using too much CPU. My current code uses nearly 20% of the CPU when I stress the prototype.
Not many people have created a successfull Gin Rummy validator, Google doesn't provide much help on this issue, and most of the people I have talked give up sayin that Gin Rummy is probably one of the most complicated card games to validate because of the millions of possible card hands someone could have.
My goal is to make a bunch of computerized card games that will help kids learn how to find shapes, colors, and memorize patterns. But my first goal is to complete this game. The validation of the other card games I have in mined, that are focused to kids will be very easy for me to implement.
I think you can send me an email from this website, if you are interested. Then I would be able to reply to your email with an attachment. If you don't have time I can understand that as well. It seems you understand the problem better then most because it seems like you already know how to play the game.





You've hit on a couple of areas that are of interest to me, both traditional games and children's learning. I've created a proof of concept bit of code that you can review that implements my third option. It is available at http://download.akison.com/GinRummy.zip, I hope it is useful. If you want to post your code somewhere for me to review I would also be willing to do that.
I've tested the code and it appears to handle all of the permutations of validating Gin Rummy properly, but I haven't written any unit tests.
As to performance, on my 5yearold PC it can evaluate about 18,000 hands per second when there are three or more melds, and over 126,000 per second with less than 3 melds. Of course, the key to the performance is evaluating as few combinations as possible, rather than using the combinations class to give all combinations. Regardless, I used the Combinations class both in the algorithm and during test.
Hope this helps,
Cheers, Adrian
modified on Saturday, October 24, 2009 11:40 PM





Hi,
Thanks for the help. I just downloaded the code, but it will take some time for me to learn how it is working. It seems you are a much better programmer then I am as your code it a lot more complex.
I have a working example, for the most part, that I've been working on for quite a while. It is very slow and a shotty job but it works I guess. However, its not going to be good enough for a game, it takes about 6 seconds to validate a couple hands.
I posted my code, please let me know after you have downloaded it: http://www.KennethRJones.com/downloads/grum.zip.

Edit:
I've taken some time to look over the code, and its making me feel kind of dumb that I didn't think of this before. I was making it so complicated.
I have no idea what is going on inside that Combinatorics folder, that code is still beyond me. But the rest of it makes sense. I'm sure I could understand it all but it would take a lot of time.
I ran the program a couple times and it appeared to me that it was making a couple mistakes every now and then, but it was moving so fast I had a hard time catching them. I'm going to save the output to a file and see if anything stands out.
I am wondering if line 22 in Hand.cs is correct. It doesnt seem right to me, unless I am reading it wrong. Should it be referring to the card count here instead?
Card c4 = i < i  3 ? Cards[i + 3] : null;
I will need to make a few modifications to the program, there are a few rules I need to add. I'm not sure how to go about implementing them yet, but you have given me a huge boost in getting started. Once I get the code down I should be able to make the changes.
Right now it only checks for fully melded hands, which wont entirely work for the game because I want players to have the option to knock. So they can lay down a hand that is paritally melded as long as the total deadwood is less then 10 points.
Deadwood being the point value of all the cards that are unmelded in the hand. So I will need to track what cards from the hand are not melded, figure out the deadwood value and then choose the best hand (i.e. the hand with the lowest score in rummy).
* Maybe the mistakes I was seeing is because the output on the console window does not seem to hold any sorted order. I get output like:
AH 2H 3H 4H 7D 6S 6C 7H 6H 7S
I need to add sorting the the finial product I guess, so that melds cannot be split apart in the output. It should read.
AH 2H 3H 4H 6S 6H 6C 7H 7D 7S
At least this way, if I were to display the cards on screen to the user, they would be able to see what melds the game found for them.
I'm sure I can add the new rules myself, now that you got me started. I'll see what I can do. Thanks again for all the help.
modified on Sunday, March 22, 2009 6:50 PM





Thank you very much for the excellent and wellcommented code Adrian. I am in the process of creating a game which uses permutation and random numbers to generate almost completely random word games on each use. I'll post it up on The Code Project if I think it's good enough.
James





Hi, Thanks by code, very usefull..
I'm making any tests and see that have a strange behavior in Enumerator's in multithreading enviroment, and I'm calling MoveNext and Current in a critical section (lock statment).. A MoveNext return false to a thread e true to all other threads, then after it return false to a another thread and true to all others.......
Any idea?!?
Thank's
Nulll...





I did not do any testing in a multithreaded environment, but after thinking about it for a minute I don't see why it wouldn't work, as long as you prevent multiple thread access to MoveNext and Current . I presume this is where you are using lock .
If you were to post a snippet of code that clearly identifies the problem I would take a look to see if I could come up with any ideas to assist you or to make the enumerators thread safe.
Cheers, Adrian





Thank you for your great code.
However, I have a need for a special variant of the Combinationscode.
If I have the set A,B,C and I want to find all sets of five from that (i.e. with repetitions), I also want to impose a limit on how many of each element is used.
Normally the the results would be:
A,A,A,A,A
A,A,A,A,B
A,A,A,A,C
A,A,A,B,B
down to
C,C,C,C,C
But lets say that any given set may not contain more than 2 A's and 3 C's.
Then A,A,A,A,A and C,C,C,C,B woould not be a valid set, but A,A,C,C,C and A,A,B,B,C would be.
Today I find all combinations and then throw away those that violate the rules, but is there a more elegant (and faster) way of doing this.
grateful for any help
regards
Stein





Thanks for your comments. I've spent a bit thinking about your problem and do not see an immediately obvious solution to your problem. I've gone down 3 blind alleys when thinking about it. If I figure something out, I'll let you know.







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

First Posted  13 May 2008 
Views  272,878 
Downloads  13,622 
Bookmarked  180 times 

