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

Comments and Discussions




Hi!
First, great job Adrian!
Could you comment how I could extend Permutations to use condition for accepting only part (small portion) of all permutations.
I use permutation of objects. There are several set of objects and the order of objects in the original sets must remain same in the permutations.
I could improve performance greatly by producing just acceptable permutations in first place..
This is just for an idea of an object, setId tells in which group the object belongs and the index tells the object's order in the group.
public class A : IComparable {
int m_setId;
int m_index;
// some other content
// ...
//
public A(int setId, int index)
{
m_setId = setId;
m_index = index;
}
public int CompareTo(object obj)
{
// ...
}
//...
}





Hartsi,
I think I understand your problem and believe that Permutations can be coerced to do the job for you. This collection will not repeat values on the input. However, we want to make sure that the enclosing Set is the trigger for not repeating and not the individual values. The next trick is to read out the values from the set in order when displaying them instead of displaying the whole set  this should fix your order condition. An example, use the following Set class to define a List that has a Next method that can report the values in order. Also, it wraps output values so it can be reused for each permutation:
class Set : List<string>, IComparable<Set> {
public Set(string[] values) : base(values) { }
public string Next() {
var value = this[currentIndex];
currentIndex = (currentIndex + 1) % Count;
return value;
}
private int currentIndex = 0;
public int CompareTo(Set other) {
return key.CompareTo(other.key);
}
private Guid key = Guid.NewGuid();
}
This is just a utility collection for getting the inner values out, I expect you'd replace this with your own container and logic. The guid is just used to give the set something to compare against for the proper operation of IComparable.
Next, the logic for constructing two sets of two values would be:
static void Main(string[] args) {
var setA = new Set(new string[] { "A1", "A2" });
var setB = new Set(new string[] { "B1", "B2" });
var sets = new Set[] { setA, setA, setB, setB };
var perms = new Permutations<Set>(sets);
foreach(var perm in perms) {
var display = "{ " + String.Join(", ", perm.Select(e => e.Next())) + " }";
Console.WriteLine(display);
}
}
The display string uses the Next method to display the inner values instead of the entire set. The result is:
{ A1, A2, B1, B2 }
{ A1, B1, A2, B2 }
{ A1, B1, B2, A2 }
{ B1, A1, A2, B2 }
{ B1, A1, B2, A2 }
{ B1, B2, A1, A2 }
Which I believe is what you are looking for.
Cheers, Adrian





Thanks Adrian!
I think I can use this as base for my code. The result is just what I wanted. So I should have all sets as many times as they have items in the var sets?





How to do Permutations, Combinations, and Variations for multiple input set





I'm not sure I understand your question. Permutations are defined against a set, so I'm not clear what a permutation of multiple sets would be? If it is just a permutation of the sets, then the generic aspect of the library will work. If it is the permutations of the items in the set, the it should suffice to union the sets and then perform the permutation.
Could you clarify what your intended outcome is?
Cheers, Adrian





You are bigger than life!





You are bigger than life!





Hi Adrian and community.
First thanks for the library: powerful stuff.
My use case is complex and I'm hoping the library can handle it.
I need to produce all address combinations composed of ordered components.
Below, a long and short address is exampled, composed of short / long dimensions taken from an address component list. However, the processing system expects addresses to mix long / short components.
A variation on the long address below would be "374555 Birchmount Rd Milliken Markham York Regional Municipality Ontario Canada L3R" where the route component draws from the short representation of route.
Assuming I start with long / short string arrays as below, how would I use the library to produce all combinations / variations of addresses while preserving the order of a fully qualified address (so Birchmount Road 374555 Milliken Markham York Regional Municipality Ontario Canada L3R would not be a valid variation).
THANKS for the help here.
Long Address:
374555 Birchmount Road Milliken Markham York Regional Municipality Ontario Canada L3R
Short Address:
374555 Birchmount Rd Milliken Markham York Regional Municipality ON CA L3R
short = {374555, Birchmount Rd, Milliken, Markham, York Regional Municipality, Markham, York Regional Municipality, ON, CA, L3R}
long = {374555, Birchmount Road, Milliken, York Regional Municipality, Ontario, Canada, L3R}
street_number: 374555 (short), 374555 (long)
route: Birchmount Rd (short), Birchmount Road (long)
neighborhood: Milliken (short), Milliken (long)
locality: Markham (short), Markham (long)
administrative_area_level_2: York Regional Municipality (short), York Regional Municipality (long)
administrative_area_level_1: ON (short), Ontario (long)
country: CA (short), Canada (long)
postal_code_prefix: L3R (short), L3R (long)





It is possible to use the library to solve your particular problem. However, it is by using the Variations With Repetitions. Algorithmically this is the least interesting of the permutations since it is basically just a bunch of nested loops. Here's a terse example of it in action:
int[] values = new int[] { 0, 1 };
var variations = new Variations<int>(values, 8, GenerateOption.WithRepetition);
var shortAddress = new string[] { "7455", "Birchmount Rd", "Milliken", "Markham", "York Regional Municipality", "ON", "CA", "L3R" };
var longAddress = new string[] { "7455", "Birchmount Road", "Milliken", "Markham", "York Regional Municipality", "Ontario", "Canada", "L3R" };
var shortAndLongAddresses = shortAddress.Zip(longAddress, (f, s) => new string[] { f, s });
var addressArrays = variations.Select(e => e.Zip(shortAndLongAddresses, (f, s) => s[f]));
var addresses = addressArrays.Select(e => String.Join(" ", e)).Distinct();
foreach(var address in addresses) {
Console.WriteLine(address);
}
This is a bit of a forcefit of the algorithm, but it gets you there.
Hope this helps. Cheers, Adrian





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)





Permutations, Combinations, and Variations using C# Generics[^]
I use :
char[] inputSet = "ABC123".ToCharArray();
Combinations<char> combinations = new Combinations<char>(inputSet, 6);
string cformat = "Combinations of {{A B C D E F}} choose 3: size = {0}";
Console.WriteLine(String.Format(cformat, combinations.Count));
foreach (IList<char> c in combinations)
{
Console.WriteLine(String.Format("{{{0} {1} {2} {3} {4} {5}}}", c[0], c[1], c[2], c[3], c[4], c[5]));
}
Result : {A B C 1 2 3} , result fail .
Can result i need : {A B C 1 2 3} , {1 2 3 A B C}, {A 1 2 B C 3}
Can you help me fix





Looking at what you're trying to get includes values from permutations and not combinations. Try changing Combinations to Permutations and removing the lower index (the 6).





Hi,
First thing first, a great algorithm.
I have a problem with the similar way. All i need is the following list.
aaa
aab
aac
aad
aba
abb
abc
abd
aca
acb
acc
acd
ada
adb
adc
add
baa
bab
bac
..
..
..
..
Hope that you got the requirement, for each alpha in the given input, ie., char[] inputSet = { 'a', 'b', 'c','d' }; the list should display all the possible chars words with 3 chars in length.
Regards,

Every thing is perfect, as long as you share





I think what you're looking for is just the Variations with Repetition. The following should provide youth list:
var variations = new Variations<char>("abcd".ToCharArray(), 3, GenerateOption.WithRepetition);





Hi guys, i tried this code to generate every permutation of "abc"
IList<Char> chars = "abc".ToList();
List<string> allCombinations = new List<String>();
for (int i = 0; i <= chars.Count; i++)
{
var combis = new Facet.Combinatorics.Combinations<Char>(
chars, i, Facet.Combinatorics.GenerateOption.WithRepetition);
allCombinations.AddRange(combis.Select(c => string.Join("", c)));
}
but it skips some permutation. (ba, ca, cb, aba...)
here's my outuput
a
b
c
aa
ab
ac
bb
bc
cc
aaa
aab
aac
abb
abc
acc
bbb
bbc
bcc
ccc
what can i do?
thanks in advance and by the way this code is helping me a lot!





At first glance, it looks like your problem is that you're using the Combinations class when you want the Permutations class. In the combinations class, the order of items in the output set are irrelevant, therefore {a, b} == {b, a}. Since "ab" is already in your output, then "ba" won't be. Try swapping Permutations for Combinations and I think you'll be alright.
Cheers, Adrian





Thanks for your help. I tried to change my code as you said but it still doesn't work.
Now i get a list of permutation of "abc" but the length is always three...
I can post my output if can help





Aha, I think I see where you are going. Here's a code snippet that I think will do what you want (I've been away from a computer for a couple of days):
IList<Char> chars = "abc".ToList();
List<string> allCombinations = new List<String>();
for(int i = 0; i <= chars.Count; i++) {
var combis = new Combinations<Char>(chars, i);
foreach(var combi in combis) {
var permis = new Permutations<Char>(combi);
allCombinations.AddRange(permis.Select(c => string.Join("", c)));
}
}
It is the permutation of each combination for each lower index. I hope this helps.
Cheers, Adrian





This really helped me out!





Btw, this is a great article, sir..
I have a program that counts a permutation solutions from specific consumer demand number in my factory.
for example if demand is 4, so my code is :
public static void PrintPerm(int demand)
{
int[] pattern = FillPatterns(demand);
for (int i = 1; i <= demand; i++)
{
Variations<int> variation = new Variations<int>(pattern, i, GenerateOption.WithRepetition);
foreach( IList<int> list in variation)
{
if (SumItems(list) == demand)
{
Console.WriteLine(string.Join(", ", list));
}
}
}
}
private static int[] FillPatterns(int demand)
{
int[] result = new int[demand];
for(int i = 0; i < result.Length; i++) result[i] = i + 1;
return result;
}
private static int SumItems(IList list)
{
int result = 0;
for(int i = 0; i < list.Count; i++) result += list[i];
return result;
}
assuming the output is should like this :
{4} where 4 = demand
{2, 2} where 2 + 2 = demand
{1, 3} where 1 + 3 = demand
{3, 1} where 3 + 1 = demand
{1, 2, 1} where 1 + 2 + 1 = demand
{2, 1, 1} where 2 + 1 + 1 = demand
{n?, n?, n?} where n + n + n = demand
{1, 1, 1, 1} where 1 + 1 + 1 + 1 = demand
As you see, your combinations is perfectly works, but i got the problem to deal with big demand, such as 40 demands or 50 demands and more, as much as the consumer reservation.
Could you help me to deal with a demand number, sir ?
Very thanks, any help would be appreciate and sorry for my english.





I have to confess I don't fully understand your problem.
In general though, combinatorial problems cannot be solved using a bruteforce algorithm. Instead we need to find a mechanism for simplifying the problem.
In this case, my instinct would be to solve the problem by recursively breaking the problem down into smaller problems. This allows you to prune the search tree whenever the sum exceeds the 'demand'. For example, if we're looking for combinations of [1..10] that sum to 10 and we've structured it as a search tree, then once we navigate to the node 7, subnode 8, there is no point looking at the nodes below that.
I hope this helps...





Very glad for your fast respond, sir.
About my problem, i should describe now :
The important parameters of the product booking in my factory is :
D = due date;
d = demand;
T = batch time of a machine (different permachines);
S = space time of workers (different perdivision)
For example :
D = 10 (days); d = 5 (demand)
T = 1 (day); S = 1 (day)
At first step, i must to find what the valid of combinations from the demand parameters for the machine usages :
After that all valid combinations is collected, I step to find the best combinations for the machines, but that not the main problem. The main problem is, "how to handle the large demand when find the valid combinations ?"
I spent more than 2 hours, when finding 450 demands I've trying the other algorithms, but only the permutations with repetition that nearly solves my project ..
I also have to try using Mathcad and MATLAB, they could solves this problem to find a best combinations very fast, but without a combination arrays representation, only the best one. I really need an array of combinations, because each best of combinations perarrays will used as Y and time as X axis in graph /product booking as the timeline of a machines combination like this :
Now, as you say, I think I'm forgot to prune the search tree, I realize that, I really appreciate your suggest. But could you give me some example to prune the search ? Anyway, you always feel free to ignore my question.
Again, thanks for the help and suggestions, sir.
Regards.





This helped me understand a lot of things I didn't before.
Thank you!!





Hi Adrian,
I wish to thank you for this very interesting work. I wish also inform you that I employed a snippet of your code in my first C# application. I refer to the Dijktsra's lexicographic permutation method that you implemented. If you want to know what I mean, you can check the "Binpacking.cs" file contained in the source code at www.codeproject.com/Articles/706136/CsharpBinPackingCuttingStockSolver.
Regards
Alberto





Thanks, I'm glad this was useful for you.
Cheers, Adrian







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.

