Add your own alternative version
Stats
134K views 2.5K downloads 52 bookmarked
Posted
11 Jun 2006

Comments and Discussions



Sorry, just started my first programming class so please excuse my knowledge or lack there of. But what language is this code? Im assuming C#?





yes, its CSharp  and for further confirmation, if you download the source and inspect the file extensions the 'source'/guts is .cs (ok, someone could be obtuse I guess and put c++ code in a .cs file, but ....)





Hi,
I have 80 C 20 combinations, and there are 3535316142212174320 combinations in this.
I need to pick up one random combination ... ElementAt use INT as input, but I need double???
So how to pick random combination from this large set?
THANK YOU





I’m not sure which code you’re looking at, because none of the classes in my zip file provide an ElementAt method. My code isn’t really amenable to random access into the set of combinations.
If you want one single random combination, why not just place all 80 elements in an array, generate a random permutation, copy out the first 20 elements, sort them if you want, and return them?





Hi,
thank You for fast answer. I've build Your code, get Combinations.dll and use it like this :
int[] Elements = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80 };
Combinations<int> C = new Combinations<int>(Elements, 20);
Random RNDGen = new Random(DateTime.Now.Millisecond);
long RNDCombination = (long)Math.Floor(RNDGen.NextDouble() * 3535316142212174320);
And now I want to get that combination like :
int[] RNDComb = C.ElementAt(RNDCombination);
But .ElementAt() takes int as input index. Am I making some mistake ??? How could I get some combination from Your class, lets say 233423435th combination.
Thank You





Again, there is no ElementAt method! Not one that takes an int, none. The algorithm used in my library can’t efficiently generate an arbitrary combination, only iterate through all combinations. I already told you in my previous message how to generate a random combination, which doesn’t use this library; that solution I described is efficient and I recommend you use it.





Your code is perfect for getting all combinations for a given set of inputs. For a program that need to calculate best rating option by combining various groups I have a requirement to put back the combinations together, objecive is to find all potential combinations.
for example if the inputs are ABC , I have to generate all combinations A, B, C, AB, AC, BC and ABC. This can be achieved by your code. I have to make cost computations for each of those options.
Now I have to select the cheapest option for putting combination together.
A + BC
B+AC
C +AB
ABC
Do you have any suggestions on how I can use your code to best accomplish this. Basically I have to concatenate combinations to a length of 3 without repeating any elements.
Appreciate your help.






@Piebaldconsult, Saw your article yesterday, but was not sure how to quickly use it. This one is packaged very well. But I am seeing performance issues once I get past 12 inputs. Will try your logic and see.





OK, let me know how it goes. Good luck.





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 combinations = new Combinations(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 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}.







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.

