Add your own alternative version
Stats
319.2K views 15.8K downloads 188 bookmarked
Posted
13 May 2008

Comments and Discussions



THANKS again; this helps.





Just curious how I can change the code to find out combinations of 2 sets of numbers. E.G.
First set is 110 in which i need 5 numbers, Second set is 15 which i need two numbers. So I would get something like {1,2,3,4,5 1,2} {1,2,3,4,5 1,3} and so on.





It should just be a case of putting two combinations together:
var set1 = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
var set2 = new int[] { 1, 2, 3, 4, 5 };
var combos1 = new Combinations<int>(set1, 5);
var combos2 = new Combinations<int>(set2, 2);
foreach(var combo1 in combos1) {
foreach(var combo2 in combos2) {
var combo = combo1.Concat(combo2);
Console.WriteLine(String.Join(", ", combo));
}
}
If your need is to create a class abstraction around this, you could create a quick wrapper. The code is the same, the only trick is to get the signature of the enumerator correct:
class TwoCombos : IEnumerable<IEnumerable<int>>
{
public IEnumerator<IEnumerable<int>> GetEnumerator()
{
var combos1 = new Combinations<int>(Set1, Set1LowerBound);
var combos2 = new Combinations<int>(Set2, Set2LowerBound);
foreach (var combo1 in combos1) {
foreach (var combo2 in combos2) {
var combo = combo1.Concat(combo2);
yield return combo;
}
}
}
}
Hope this helps.
Cheers, Adrian





Hi Adrian,
I will give this a go. The initial way I tried was similar to your first snippet of code only, I needed to store them to be used later on. For this I used List<> which caused my program to have a memory exception as I'm expected alot of combos.
Cheers.





Hello i wonder if this solution (or any other you may know) can help me to solve the following problem:
Supose we have the following:
1. SEED ARRAY (0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0)
2. K = 8; this means i want possible solutions element length to be MAX 8.
3. Sum of the K elements in a solution sum = 1.
For example:
K=8 at MAX
Solution 1: 0.1,0.9
Solution 2: 0.5,0.4,0.1
Solution 3: 1.0
Solution 4: 0.1,0.2,0.3,0.4
Solution 5: 0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.3
This means any number can be repeated N times.
Can you please tell me if you can help me with this? or at least give me some guides to algorithms other than subset sum (or pointing to a correct one), or any stuff you may think that can help me.





For your case, you could solve it using the Combinations class to perform a search. This would not be the most efficient way to solve this problem in the general case (that is, any possible seed array with any K and any sum). You are correct that this is a variation of subset sum (it certainly doesn't look any simpler at first reading) and therefore is NPComplete and you won't be able to solve this for large N. At any rate, here is an application of the Combinations class in this article that will solve your specific problem rather quickly:
var values = new double[] { 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0 };
var unitCombos = new List<IEnumerable<double>>();
for(var i = 1; i <= 8; ++i) {
var combos = new Combinations<double>(values, i, GenerateOption.WithRepetition);
unitCombos.AddRange(combos.Where(e => e.Sum() == 1.0));
}
foreach (var unit in unitCombos) {
Console.WriteLine(String.Join(", ", unit));
}
Or a more functional implementation:
var values = new double[] { 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0 };
var lowerIndex = new int[] { 1, 2, 3, 4, 5, 6, 7, 8 };
var combos = lowerIndex.SelectMany(e => new Combinations<double>(values, e, GenerateOption.WithRepetition));
var unitCombos = combos.Where(e => e.Sum() == 1.0);
Of course as N (the upper bound) grows, this will be quite inefficient. To get some performance improvements for small N, you could try checking the assumptions. For example, if the seed array is always of the form { 0.1, 0.2, 0.3, ... n } then you could cull the search tree tremendously. Of course, that would not be possible with this library.
Cheers, Adrian





First of all, great article, useful code! Many thanks.
I have a question:
I need to generate combinations and sometimes I want to start generating from a specific combination.
For the input {A B C D}, the output is:
Variations of {A B C D} choose 2: size = 12
{A B}
{A C}
{A D}
{B A}
{C A}
{D A}
{B C}
{B D}
{C B}
{D B}
{C D}
{D C}
How do I get all the variations starting from a specific variation. I want to be able to get all the variations from (let's say) {D A}.
Is any way to do this without iterating trow all the variations before that variation?
Thank you!





Thank you and sure, I can provide a couple of ways to achieve your goals. The first is lengthy and guaranteed to work. The second is quick but relies on an implementation detail that you shouldn't trust in production. The one you choose depends on your usecase.
1. Create a custom object, T, and implement IComparable. Then run the permutations on the custom object. For example:
public class CustomOrderChar : IComparable<CustomOrderChar> {
public char Value { get; set; }
public int CompareTo(CustomOrderChar other) {
}
public override string ToString() {
return Value.ToString();
}
}
2. For a set S of type T, use Variations(S, S.Count()) . This works for two reasons.
a) Permutations of a set is the same as the Variations of a set with the lower index being equal to the upper index. So Permutations(S) === Variations(S, x) where x is count of items in S.
b) The implementation of Variations doesn't assume lexicographic ordering of the inputs and creates a shadow array of values that it uses for its internal permutation. This parallel array implementation is not visible to the user.
The result is then achieved by ordering your input with the first desired output value:
char[] chars = { 'D', 'B', 'C', 'A' };
var perms = new Variations<char>(chars, 4);
foreach(var perm in perms) {
Console.WriteLine("{" + string.Join(", ", perm) + "}");
}
Keep in mind though that Permutations defines a set of values and not an order. If I had found a faster algorithm that delivered the set with no apparent order, I would have used it.
Cheers, Adrian





Greetings!
First of all, every praise for this great article.
We use this your algorithm for multiply every combinations elements and sumarize result in our application.
static decimal g(decimal[] values, int choose) {
if(choose == 1) {
return values.Sum();
}
else {
var sum = 0M;
for(int i = 0; i < values.Count()  1; ++i) {
var p = values[i];
var sub = values.Skip(i + 1).ToArray();
sum += p * g(sub, choose  1);
}
return sum;
}
}
And it's perfect. The maximum combinations we use is 29 combination of 30. The problem is next, if we use 26 combination of 30,
execution is slower than usual, the slowest execution is when we use 29 combination of 30. We tried everything to improve performance, but we failed.
If you have any idea how to improve this already perfect algorithm, we would be very grateful for it?
Many thanks.
Best regards!





I have to confess I'm not sure from your code what you're trying to do. It sounds like an academic problem like one might find on Project Euler.
What is the statement of the problem? It feels like I'm looking at something halfway optimized without any context.
Cheers.





Thank you Sir for your answer.
We will try to explain clearer.
We use your algoritham for taking the sum of the product of the elements of each combination.
static decimal g(decimal[] values, int choose) {
if(choose == 1) {
return values.Sum();
}
else {
var sum = 0M;
for(int i = 0; i < values.Count()  1; ++i) {
var p = values[i];
var sub = values.Skip(i + 1).ToArray();
sum += p * g(sub, choose  1);
}
return sum;
}
}
And it’s work great, maximum decimal values (Combinations without Repetition that ) we use is 20.
EXAMPLE
decimal[] values = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
int choose = 10;
RESULT (sum = 184 756)= exucition is very fast;
This algoritham is very quick, but the problem is next, we have request to implement maximum values which can be used to be 30.
EXAMPLE
decimal[] values = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
int choose = 29;
RESULT (sum = 30) = exucition is very slow;
If you have any ideas to improve exucition, we'd like you to tell us.
Forgive us on bad english.
Best regards!





Ok, I've had a quick look at the performance and it works fine if you were to use the library provided. (also available via NuGet). Here's the code that I've just written:
var combos = new Combinations<decimal>(values, choose);
var result = combos.Sum(e => e.Aggregate(1M, (acc, val) => acc * val));
Given that the length of values is 30 and the choose is 29, there are only 30 combinations. So this runs in 18ms on my machine.
Of course, Combinations tend to run worst (have the largest output set) when the lower index is half the upper index.
As a side note, when the values are all 1's, then the sum of the product is equal to the number of combinations and this can be computed directly using the library or the formula in the article.
Hope this helps, Cheers, Adrian





Once again thank you,
Your suggestion helped us a lot, we were able to improve significantly performance of our apps.
Best regards!





Excellent article. I'm looking to derive all the possible scales in the 12tone music system. In short, I need to find all the variations of {1, 2} where the sum of the intervals equals 12.
For example, a major scale would be {2, 2, 1, 2, 2, 2, 1}.
The whole tone scale would be {2, 2, 2, 2, 2, 2}.
The diminished scaled would be {1, 2, 1, 2, 1, 2, 1, 2}.
And, of course, there are many more.
As you can see, while each ordered set has a different number of intervals, the sum of all intervals equals 12. What’s more, it would be helpful to optionally require the output to contain a minimal number of 2’s, so that {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, while a valid scale, would be ignored as it has no 2’s.
Would you be able to make any recommendations in terms of formulas or algorithms that would be helpful in successfully meeting this task?
Thanks,
Ozie
modified 19Apr15 20:50pm.






Ozie,
Interesting problem. I won't pretend to understand intervals in music but hopefully can help with the math. I think we need to star by looking at the unique unordered sets that make up the system, this is intuitively easy as the seven sets:
{2, 2, 2, 2, 2, 2}
{1, 1, 2, 2, 2, 2, 2}
{1, 1, 1, 1, 2, 2, 2, 2}
...
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
As another commenter suggested, this is more closely related to the knapsack problem than to permutations.
Once each of these sets are done, we can compute the Permutations of each. For example, the second set would be computed as:
int[] tones = { 1, 1, 2, 2, 2, 2, 2 };
var perms = new Permutations<int>(tones);
foreach(var perm in perms) {
Console.WriteLine(String.Join(", ", perm));
}
The first half should just be to loop through the seven sets and then calculate the permutations of each.
I hope this helps in some small way.
Cheers, Adrian





Thank you very much!
Ozie





Thank you for your great work, not only the code but also the detailed explanation is extremely useful!
I have the following problem that I cannot find a reference to in the "classic" permutation/combination/variation scheme:
input set {A,A,B,B}
output:
{A,A,B}
{A,B,A}
{A,B,B}
{B,A,A}
{B,A,B}
{B,B,A}
This is similar to permutations with repeated elements in the input set, BUT the output set is smaller.
It might seem that variations with repetitions would do the job, but it is not the same as it would add {A,A,A} and {B,B,B} for instance.
Any ideas or hints on how I could treat this problem?
Thanks in advance for your time.
Kindly,
Michele





I most likely overread it but I cant seem to find what im looking for,
I am looking for the Interface that i need to implement so that I can use this Methods on an object.
I got a structure like,
List;
myObject contains an Integer Value that has to be "shuffeld"
for Example i got 3 objects, with 1 2 3 as values
I would like to get the Variations
myObjc(val 1) myObjc(val 2) myObjc(val 3)
myObjc(val 1) myObjc(val 3) myObjc(val 2)
myObjc(val 2) myObjc(val 1) myObjc(val 3)
myObjc(val 2) myObjc(val 3) myObjc(val 1)
myObjc(val 3) myObjc(val 1) myObjc(val 2)
myObjc(val 3) myObjc(val 2) myObjc(val 1)
I hope it's understandable what im trying to explain
Wishes
modified 5Mar15 7:44am.





Hi (a bit late maybe),
Have a look at the Permutations class, it is exactly what you refer to.
You would need to
 inherit IComparable on your myObject class definition
 implementat IComparable using the Integer within MyObject
 use Permutations < MyObject >
Hope it helps
modified 7Apr15 17:29pm.





Hi,
Im using yours code and works quckly but when I need add one more operation it is very slow
I neeed every 10 combination of 20. it is about 185 000 comb
I need multiply every combinations elements and result sumarize > this proces works very slow....
Is there any idea how to improve this program to accelerate execution.
decimal[] Values = // list of 20 decimal values from 1,1 to 9,9
GenerateOption opt = GenerateOption.WithoutRepetition;
Combinations<decimal> comb = new Combinations<decimal>(Values, 10);
foreach (IList<decimal> c in comb)
sum += c.Aggregate((a, b) => a * b);





One of the fun things about combinatorics is that problems that work nicely for small sets end up taking forever for larger set. This is known as "combinatorial explosion", where just adding a few extra values causes processing time to increase dramatically because the number of additional combinations increases geometrically or exponentially.
This is fun, because when we bump into these issues, we need to find clever algorithms instead of brute force approaches.
In your algorithm:
static decimal f(decimal[] values, int choose) {
Combinations<decimal> comb = new Combinations<decimal>(values, choose);
decimal sum = 0;
foreach(IList<decimal> c in comb) {
sum += c.Aggregate((a, b) => a * b);
}
return sum;
}
you're taking the sum of the product of the elements of each combination. Once you're past 20 or so elements, it will get progressively slower. The first thing I'd do in this situation is solve a simpler problem and see if that knowledge can help us solve the larger problem. I chose the following:
decimal[] values = { 2, 3, 4, 5 };
int choose = 2;
{2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5} & {4, 5}
Here we see that the combinations fit into our sum of products as:
(2 * 3) + (2 * 4) + (2 * 5) + (3 * 4) + (3 * 5) + (4 * 5) = 71
I then observe that I can factor out the first term from successive sets like the following:
2 * (3 + 4 + 5) + 3 * (4 + 5) + 4 * (5) = 71
See, we don't actually have to calculate all of the combinations to solve the problem. By factoring out the 2 first, I've significantly reduced the computation requirements. This was just my first optimization which appears to speed it up by a factor of 5 or so. There is still a lot of computation happening, but the following is the code that speeds it up:
static decimal g(decimal[] values, int choose) {
if(choose == 1) {
return values.Sum();
}
else {
var sum = 0M;
for(int i = 0; i < values.Count()  1; ++i) {
var p = values[i];
var sub = values.Skip(i + 1).ToArray();
sum += p * g(sub, choose  1);
}
return sum;
}
}
Of course, this is not a complete solution, just a partial one. There are surely more efficient algorithms than this.
Cheers, Adrian






the code u hav done for combination is really fast n great.. i tried a code using vb6 classic but it was too slow.. thanks for the enlighting..





Awesome! Just the stuff I need.
(Variation with repetiton)







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.

