Add your own alternative version
Stats
157.9K views 2.8K downloads 52 bookmarked
Posted
11 Jun 2006

Comments and Discussions


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.





I don't have much knowledge in the world of C#, but I been looking for this code everywhere. Do you think you can post a completed version of the generator?





Hi,
The code is complete. You should just be able to use the Download Source Code link, unzip the downloaded file, and use my generator in your own code right away. You can just read the very top few paragraphs of the article (Using the Code) to get started on using the generator in your own project.
Chris





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?






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.

