Add your own alternative version
Stats
140K views 2.6K downloads 52 bookmarked
Posted
11 Jun 2006

Comments and Discussions



Adding a plus sign to the character set will not work, because combinations are orderagnostic. So you will not see “A+BC” and “AB+C” as separate outputs, because they are equivalent.





I thought you were doing permutations. But, no, it may not work; just something to consider and try.





If you actually want all possible constructions of ABC, there are quite a lot: A+B+C, AB+C, A+BC, AC+B, and ABC. I don’t think my library is what you’re looking for. I think you are better off allocating n “groups”, placing each element into a group, and then building the whole by “buying” each group as a construct. So when A, B, and C are all in group 0, you are buying object ABC. When A and B are in group 0 and C is in group 1, you are buying AB+C. There will be duplicates with the simplest approach to implementing this algorithm, but those can probably be eliminated. However, this is not the problem the library described in this article solves.





A recursive c program thats generates all of the combinations nCk in a fast possible way.
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
int nCk(int n,int loopno,int ini,int *a,int k)
{
if(k==0)
return 1;
static int count=0;
int i;
loopno;
if(loopno<0)
{
a[k1]=ini;
for(i=0;i<k;i++)
{
printf("%d,",a[i]);
}
printf("\n");
count++;
return 0;
}
for(i=ini;i<=nloopno1;i++)
{
a[k1loopno]=i+1;
nCk(n,loopno,i+1,a,k);
}
if(ini==0)
return count;
else
return 0;
}
void main()
{
int n,k,*a,count;
printf("Enter the value of n and k\n");
scanf("%d %d",&n,&k);
a=(int*)malloc(k*sizeof(int));
count=nCk(n,k,0,a,k);
printf("No of combinations=%d\n",count);
getch();
}
modified 20Jan12 14:53pm.






Best i m rating it to by 5
If you can think then I Can.





This code is super fast, i translated the combinations and entity classes from c# to vb and it works superb under vb.net, this code has stood the test of time. Many thanks for sharing with us





Hi Hawk777,
Your code is just what I'm looking for, but a bit more, new and rustty in C's, dont know were to start. Is is possible to have a demo of this code?
Yabadabado





There are examples of how to use the library in the article. The ZIP file also contains a fullyworked benchmarking tool which (naturally) calls the library.





Sorry for the trouble, when I run the code in v studio, I got a messages part of it that say I have to add an executable project which reference the library... Should I copy "int[] input = new int[] { 1, 2, 3, 4, 5 }; into the line before "foreach".





Well, you want to do what the message says. Create an executable project (console project or Windows forms project or whatever type), and use the Visual Studio UI to make the executable project "reference" the Combinations project. Then you will copy the int[] input = … line as well as the foreach and its contents into, say, Main .





Hi, Your code is fantastic but I have a little problem. It seems that you do not take care of the order of the subsets. For example, if the input set is {1,2,3,4,5} the produced by your code combinations of 3 are: {1,2,3}...{3,4,5}. But if the order matters, then there are missing combinations such as {3,2,1}. Is there an easy way to fix this?
Thanks in advance
antonis





Look on the second page of comments at the thread titled "Beautiful implemenation! Is it easy to reorder the combinations?" started by trevstar. What you're looking for is permutations as well as combinations; he mentions where he found a permutation generator which could be applied after the combination generator.





First of all thank you for the code.
I have a particular situation.
int[] deepLevels=new int[] { 0, 1, 0};
The second value (1) says that for "B" value there are 2 possible values (0 and 1).
string[] input = new string[] { "A", "B", "C" };
Combinations<string> combinations = new Combinations<string>(input, 2);
How can I use (or modify) the code in order to obtain the following output: ("A{0}","B{0}") ("A{0}","B{1}")
("B{0}","C{0}") ("B{1}","C{0}")
("A{0}","C{0}")
Thanks.





I think what you want is for the letter B to appear only once in any given output array, but for each time B appears, to have it appear in two consecutive arrays. I believe the following code will do what you want, as long as inputStrings has no duplicate elements, though the code is untested as I no longer have a .NET development environment installed.
string[] inputStrings = new string[]{"A", "B", "C"};
int[] deepLevels = new int[]{0, 1, 0};
int[] indices = new int[inputStrings.Length];
for (int i = 0; i < indices.Length; ++i) {
indices[i] = i;
}
Combination<int> combinations = new Combination<int>(indices, 2);
foreach (int[] combination in combinations) {
string[] outputStrings = new string[combination.Length];
for (int i = 0; i < combination.Length; ++i) {
outputStrings[i] = inputStrings[combination[i]];
}
int[] outputLevels = new int[combination.Length];
for (int i = 0; i < outputLevels.Length; ++i) {
outputLevels[i] = 0;
}
for (;;) {
bool carry = true;
for (int i = 0; carry && i < outputLevels.Length; ++i) {
if (outputLevels[i] == deepLevels[combination[i]]) {
outputLevels[i] = 0;
carry = true;
} else {
++outputLevels[i];
carry = false;
}
}
if (carry) {
break;
}
}
}





Hi, Hawk777, It' a very useful software and the speed of runing is very fast. I want to use a progressbar when runing, so how to count collection sizes before run?
Thanks.





There's no closedform formula, because the answer depends on how many duplicate items there are in the input.
If there are no duplicates, then there are (n!)/(r!(nr)!) lengthr combinations from an input corpus of n elements.
If the corpus may have duplicates, I don't know the formula to compute the number of combinations. There probably is one though.





Hi. I’m basically a drafter and software that I’m using allows open API. Sometimes is necessary to write a little code. This code here could really help with what I’m trying to do. Problem is that c# is not the place that I feel comfortable yet. If you would help I would really appreciate. Since a project with an output type of class library cannot be started directly I need to create let’s say a windows form and reference it to the Combination class as well as to the Benchmark class. Is this correct? After I’ve done this I threw a button on form, double clicked on it and wrote the part of the code that you have at the top of page by “using code” and it didn’t recognize it. Can you help me out here with this? Please, please.. Thanks. JL





Hi, Unfortunately I haven't done any Windows or .NET programming for a few years now, so I'm a little rusty. I'll do my best, though.
First, you don't need to reference the Benchmark code. That code is only for doing performance benchmarks of the library. If all you want to do is generate combinations, you don't need it.
Second, of course, you need to be writing your Windows Forms program in C# to use the samples in the article (i.e. you can't be using VB.NET). You should be able to call the generator from VB.NET, but you'll have to write the calling code in VB.NET, which the samples in the article aren't.
As far as I know, the code should work right. When you say "it didn't recognize it", that doesn't mean very much. What was the error message?





Well, here is what I was doing... Currently working in C# 2010 Express by the way... I’ve created new windows form project. So far so good. In Project menu click on add reference.. Referenced it to ..combinations\bin\debug\combinations.dll that I previously downloaded from web to my pc and had unzipped. Later I created a ‘button’ on the form. Double clicked it and wrote this: int[] input = new int[] { 1, 2, 3, 4, 5 }; Combinations <int> combinations = new Combinations <int>(input, 3); foreach (int[] combination in combinations) { } And getting error message in message list. To be exact 2 lines, 2 errors, both are same and are saying: The type or namespace name ‘Combinations’ could not be found (are you missing a using directive or an assembly reference?) I’m sure it’s going to be an easy one for you.. Can you, please? Thank you. Joe





Write the following at the top of the source file, outside any functions:
using CH.Combinations;






Looks gr8 stuff. Friend i am basically C# developer. In C# and in any other coding language too, many a times we came across a situation to find out number of possible cases based upon two set of values say
A variable A may have 2 possible values in code 1) Null 2) Not Null And same for Variable B Now if we look for possible combination of A and B it will be only one i.e. AB but cases will be 4 i.e 2(possible cases of A)*2(Possible cases of B).
And you can have these values for the combination of AB cases
1) A(Null) B(Not Null) 2) A(Null) B(Null) 3) A(Not Null) B(Null) 4) A(Not Null) B(Not Null)
You can take this as SET A has 2 possible values abd SET B has 2 possible values And we have to make all possible combination of two selecting one value from each set.
Can u write a program or guide me to how to achieve this.
Thanks In advance





You're trying to generate the Cartesian product of two sets. Simply write a pair of nested loops:
int[] setA = {1, 2};
int[] setB = {3, 4, 5};
for (int i = 0; i < setA.length; i++) {
for (int j = 0; j < setB.length; j++) {
}
}
The inside of the inner loop will be invoked six times, with the values (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), and (2, 5).





Thanks but What if set A has 3 possible outcomes and Set B has 5 possible outcomes and we have to select 2 from Set A and 3 from Set B randomly to generate all possible combinations having total count of 5 in single output.





If I can understand what you're asking correctly, you want to select the Cartesian product of the set of all cardinality2 subsets of A and the set of all cardinality3 subsets of B.
To do this, you want two nested loops, both of which can use my combination generator, something like this:
Combinations<int> combsA = new Combinations<int>(A, 2);
Combinations<int> combsB = new Combinations<int>(B, 3)
foreach (int[] combA in combsA) {
foreach (int[] combB in combsB) {
}
}
modified on Saturday, December 19, 2009 3:41 PM





Thanks for your algorithm, it was hard googling for the specific solution and you make it clear as day.
I've got a prob... Is there any way to generate the combinations with a larger list? I'm quickly running out of memory, even when the stored data type is a single byte. I'd love to write every possible combination to the hdd if possible instead of storing the combinations in ram.
Thanks in advance!





Memory must be large enough to store the input dataset and ONE combination. There's no reason to store all combinations in memory; why are you doing that if you don't want to? In my first block of sample code at the top of the page, just replace
// Do something with "combination".
with code to write "combination" to disk.





Is there any way to ask the Combination class for the number of combinations it will generate, before actually asking it to do the generation?
THanks Michael





While I believe there's a fairly straightforward mathematical way to do this (not a closedform formula, though, since it depends on the distribution of duplicates), the answer is that no, the posted code doesn't provide this feature.





Ok... Say I have a variable set that will ideally be uploaded dynamically from an excel table...
I want to have every combination of the set where m = 2... to .... (n1) (or optionally = n)
To clarify, if you have a set of 5 intergers (1, 2, 3, 4, 5):
Where m = 2
{1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4,5}
Where m = 3
{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, and {3, 4, 5}
Where m = 4
{1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5}
(optional) Where m = 5 {1, 2, 3, 4, 5}
Having all these outputs looped into one form. Thanks for your input and expertise.





Code to do this is presented directly in the article, at the end of the Using the Code section. As to the complexity analysis of doing this, you can compute it from the complexities of the individual operations listed further down.
However, if your input values are, in fact, a SET (there are no duplicates), then what you are actually looking for is an algorithm to generate all subsets of a set. This is a much easier problem: simply loop through all the numbers from 0 to 2^{n}1 inclusive. Treat each number as an nbit string, where a 1 bit means to include the corresponding element of the set and a 0 bit means to exclude it.
Note: if you want your subsets to be proper, loop up to 2^{n}2 instead of 2^{n}1. If you don't want the empty set, start from 1 instead of 0.





Great code!
I took the liberty of modifying the code to allow selecting r items from the input n where r > n, by simply copying each item in the input r times back into the input. I.e. when input is {A,B,C} and r = 4, I convert input to {A, A, A, A, B, B, B, B, C, C, C, C }. Is there a more "elegant" way of doing this?
Also, I would like to disallow repetitions in the results, i.e. when the input is { A, B, C } and r = 2, I would like to get { A, B }, { A, C }, { B, C } and NOT { A, A }, { B, B }, {C, C }, { A, B }, { A, C }, { B, C }. Can I modify the Combination<t> class to do this? Or should I rather use the code at http://www.codeproject.com/cs/algorithms/combinatorial_in_csharp.asp which does this?
regards
 modified at 2:25 Wednesday 1st August, 2007 to include the correct link





Stein R wrote: Great code!
Thanks! Glad people are finding it useful.
Stein R wrote: I took the liberty of modifying the code to allow selecting r items from the input n where r > n, by simply copying each item in the input r times back into the input. I.e. when input is {A,B,C} and r = 4, I convert input to {A, A, A, A, B, B, B, B, C, C, C, C }. Is there a more "elegant" way of doing this?
Not without extensive changes to the algorithm. Duplicating the input items is exactly what I suggested to Mr. Leng two threads down. Note that in some situations you might want to do this duplication even if r ≤ n, for instance if you want to see any number of copies of each input item in the output.
Stein R wrote: Also, I would like to disallow repetitions in the results, i.e. when the input is { A, B, C } and r = 2, I would like to get { A, B }, { A, C }, { B, C } and NOT { A, A }, { B, B }, {C, C }, { A, B }, { A, C }, { B, C }. Can I modify the Combination class to do this? Or should I rather use the code at http://www.codeproject.com/cs/algorithms/combinatorial_in_csharp.asp which does this?
This is exactly what my code does. The code
int[] source = {1, 2, 3};
foreach (int[] combo in new Combinations<int>(source, 2)) {
}
produces the combinations {1,2}, {1,3}, and {2,3}.





Thank you for your quick reply.
I read your answer to Mr. Leng, but did not relate that to my problem. But you are correct, that is also the solution for me.
As for repetition, you are also correct. However, when implementing the change to duplicate input elements, I made a mistake, and the input was ALWAYS duplicated, and thus the output always returned duplicate elements. I fixed this error, and made a parameter to the Combinations<> class that specifies if elements in output should be repeated or not.
Serves me right for writing a post after working 8 hours...
again, thank you for your wonderful example
regards





I was using DoBenchmarkEnumerator(10, 5, 0) to test the code and found out that some combinations are missing from the output. For example, I did not get combination of 01243. Can you comfirm?





{0,1,2,4,3} is not returned because it is equivalent to {0,1,2,3,4}. This is a combination generator, not a permutation generator. In combinations, order is irrelevant in determining whether two outputs are equivalent. If you want both 01234 and 01243 to be returned, you probably want to use a combination generator (such as my code) to generate all e.g. length5 combinations of 10 elements, then use a permutation generator to generate all permutations of each length5 combination.





Viry nice article!
It will be nice to extend the algorithm to allow duplicates elements in the combination. e.g. {1,1} is a valid length2 combinations. Any idea on how to do this?





A large part of the complexity in my algorithm comes from making sure duplicates work right. The following code:
int[] source = { 1, 1, 2, 3 };
foreach (int[] combo in new Combinations<int>(source, 2)) {
for (int i = 0; i < combo.Length; i++)
Console.Write("{0} ", combo[i]);
Console.WriteLine();
}
will print out the following text:
1 1
1 2
1 3
2 3
Or were you looking for something else?





I am talking about the duplicates in output:
for the input {1,2}, I expect to get {1,1}, {1,2},{2,1},{2,2}.





There seem to be two separate issues you want addressed:
1. You want each element in the input to be returned not just zero or one times, but anywhere from 0 to r times. My code does not address this, but you can do it yourself by making a new array containing each input element copied r times, which exploits my code's ability to properly deal with duplicates in the input. For instance, you could pass {1,1,2,2} for your example.
2. You want both {1,2} and {2,1} to be returned. These are not combinations, these are permutations. A combination generator by definition considers these outputs to be equivalent, and therefore generates only one of them. You need a different algorithm to generate permutations. If you want your output to be smaller than your input, you could certainly use my algorithm to generate all the combinations of the desired size, then, for each combination, permute it using a different algorithm.
Assuming the chosen permutation algorithm considered duplicate elements as being equivalent, implementing both of my suggestions should give you exactly what you're looking for.
Anything else I can help with?





The following code will trigger an Assert although it is a perfectly valid request :
Combinations<int> comb = new Combinations<int>(new int[] { 1, 2, 3 }, 3);
foreach (int[] c in comb)
{
GC.KeepAlive(c);
}
The following Assert triggers in method MoveFirst() :
Debug.Assert(currentIndex < _Combinations._Elements.Elements.Count);
Commenting out the Assert line fixed the problem. I don't think the Assert should be there at all...





Actually, the assert was there for a reason, but you found an improperlyhandled corner case: the assert shouldn't be checked if the FOR loop is about to be fallen out of. I've sent a new source archive to CP for upload which moves the assert to the beginning of the FOR loop, where it actually matters.





I just got an email from the CodeProject staff. The new source archive is up.





I love the algorithm and the code. It works really well, but is there a quick modification that could be done to also include the reordered sets? That is, I want to include for 1,2,3,4,5 5C3 the combinations {1,2,3}, {2,1,3}, {3,1,2}, etc.
Thanks again for the great article.
Trevor B





What you're looking for is not combinations, it's permutations. You can use my code to generate all combinations of length 3, then use a permutation generator of some sort (I think there are one or two on CodeProject) to permute the combinations. For example:
Combinations<int> combinations = new Combinations<int>(input, 3); foreach (int[] combination in combinations) { Permutations<int> permutations = new Permutations<int>(combination); foreach (int[] permutation in permutations) { // Do something with this permutation. } }
or some such. Hope that's useful.





Thanks for the info. I found an example in the MSDN Magazine/Dec 2006 in Test Run on doing permutations for strings. A quick change to that code to make it a generic, gave me what I was looking for.
Thanks for the quick response.
Trevor B





Hi, Trevor
Because I am also interested in permutations, can you please send me your implementation? My email is: antonis74@gmail.com
Thanks in advance
antonis





I never wrote a permutation generator. As I said in my original reply to trevstar, "I think there are one or two [permutation generators] on CodeProject". That doesn't mean they're mine. Typing "permutation" into the Algorithms and Recipes search box brings up a few articles, of which perhaps this one might suit your purposes. If you were using C++, of course, you could just use the STL's builtin std::sort and std::next_permutation functions.





What is the best way to rewrite the classes without using C# Generics? Thanks.







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.

