
Comments and Discussions



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





Hi Adrian,
This is really an interesting piece of work and I appreciate your understanding of the subject. While time to generate the sequence is certainly not a problem, but to display them at once is a big problem.
I tried to bind the resultant combinations to a listbox or datagrid, but always there has been out of memory exceptions. Or the display time is just too much. I am talking about the data of order of 45_C_7 i.e roughly 45 million combinations
Can you please shed some light on it on how to bind the resultant combinations to a listbox or datagrid
Thanks
Pulkit





Pulkit,
I've never tried putting that many rows in a datagrid or listbox. I reckon that many items is beyond the design of those controls. While I don't have any answers for you, one idea comes to mind:
1. Create a ViewModel around the permutations and only fetch the rows up to the selected page of rows.
2. Use a virtualizing container that supports only fetching a subset of items.
The availability of the container option depends on which framework you're using, e.g. Silverlight, WPF, Modern, etc...
I hope this helps point you in the right direction.
Cheers, Adrian





Hi Adrian,
Thanks for your time.
To display such large data, your idea of Viewmodel will work almost perfectly. But now I am left wondering what would be the best possible & efficient way to dump such a large data into a delimited text file.
Again, your ideas will be well appreciated.
Thanks & Regards,
Pulkit





I was thinking of using Virtualization ListBoxes too for the Anagram app on WindowsPhone, but not sure how I can tell the library (or don't remember) to get me say permutations from index N to N+K (indexing the space of all possible permutations). Similarly goes for Combinations/Variations, without it having to do calculation from index 0 to index N
Computer & Informatics Engineer
Microsoft MVP J# 20042010
Borland Spirit of Delphi 2001
QuickTime, QTVR, Delphi VCL,
ActiveX, COM, .NET, Robotics
http://zoomicon.com
http://zoomicon.wordpress.com





I did try to work through three different algorithms searching for the best performance. However, none of them were going to give us the arbitrary nth permutation. As such, the interface is IEnumerable instead of IList. There is a mechanism for finding the nth element, a brief description is available at http://en.wikipedia.org/wiki/Factorial_number_system[^]. However, using this algorithm for calculating all permutations would be slower than the lexigraphic algorithm that I used.
Cheers, Adrian





Thanks for the pointer, will take a look at that article
Since on the phone and other touch UI people tend to scroll / navigate serially, maybe a way to go back/forward to next n elements would be enough, plus some caching. Not sure how easy the back is (previous n items calculation) without recalculating from the start though
Computer & Informatics Engineer
Microsoft MVP J# 20042010
Borland Spirit of Delphi 2001
QuickTime, QTVR, Delphi VCL,
ActiveX, COM, .NET, Robotics
http://zoomicon.com
http://zoomicon.wordpress.com





Hello there
I wrote a program to generate variations of 6 letters word of given fixed 12 letters
using the Facet.Combinatorics namespace
, but the execution time of the program is too big I could not get the result I left the computer for more than 12 hours and the execution did not finish then I gave up
how could I get my result in a faster way? or my program has a problem ?
here is my code
*******************
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using Facet.Combinatorics;
namespace AnKathab
{
public partial class Form1 : Form
{
string a, b, c, d, E, f, g, h, i, j, k, l;
string[] letters;
int wordLettersCount;
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
a = textBox1.Text;
b = textBox2.Text;
c = textBox3.Text;
d = textBox4.Text;
E = textBox5.Text;
f = textBox6.Text;
g = textBox7.Text;
h = textBox8.Text;
i = textBox9.Text;
j = textBox10.Text;
k = textBox11.Text;
l = textBox12.Text;
letters = new String[12] { a, b, c, d, E, f, g, h, i, j, k, l };
wordLettersCount = Int32.Parse(textBox13.Text);
Variations variations = new Variations(letters, wordLettersCount, GenerateOption.WithoutRepetition);
string vformat = "Variations choose 2: size = {0}";
richTextBox1.Text = (String.Format(vformat, variations.Count));
foreach (IList v in variations)
{
richTextBox1.Text = richTextBox1.Text + v[0] + v[1] + v[2] + v[3] + v[4] + v[5] + " / ";
}
}
private void Form1_Load(object sender, EventArgs e)
{
}
}
}
}
}
private void Form1_Load(object sender, EventArgs e)
{
}
}
}





In general, computing all of the variations is prohibitive in time. Even small numbers of items have a combinatorial explosion of variations; in fact this area is where the term combinatorial explosion comes from.
For example, with 12 items (letters in your case), selecting variations of 12 choose 1 results in 12 items. However, growing to variations of 12 choose 6 V(12,6) results in 665,280 results. This is a nontrivial amount of items to process!
Usually, we look at our problem and try to figure out how we can simplify the problem to process as few of these as possible. This is the process of reducing the search space.
However, when we need to process all of them, we need to ensure that the work done for each variation is small. I think in your code snippet, the biggest time spent will be in the line:
richTextBox1.Text = richTextBox1.Text + v[0] + v[1] + v[2] + v[3] + v[4] + v[5] + " / ";
This will allocate multiple strings on the heap each time and these strings will quickly become megabytes in size. I'm not even sure if the RichTextBox could handle the final 4.5MB document. By my rough estimate, you will allocate and deallocate 11TB of memory before it is finished. To get around this string manipulation problem, use the StringBuilder class to build the string and then assign it once to your RichTextBox . For example:
var sb = new StringBuilder();
foreach(var v in variations) {
foreach(var c in v) {
sb.Append(c);
}
sb.Append("/");
}
richTextBox1.Text = sb.ToString();
Cheers, Adrian





This has been working great for me, until a user (darn those users) fed it 75K items to combine.
The SmallPrimeUtility.Factor method is throwing a Index was out of range. Must be nonnegative and less than the size of the collection. exception when i = 65537
Any suggestings on handling this?
Thanks
UPDATE: I see the issue. It's not with SmallPrimeUtility.Factor() but with the CalculatePrimes(), which populates the PrimeTable which is used in the Factor() method...
Now can I tweak CalculatePrimes()... hum...
If I change CalculatePrimes() from using 65536 to say 131074, besides performance, there any other imapct or unintended impacts?
It seems to work (keyword), but...
modified 3Aug13 15:56pm.





Thanks for the feedback, you have indeed found a boundary condition that I didn't catch originally.
I believe your fix will indeed work but only to the size that you've put in (i.e. 131074). The problem comes about when trying to factor any integer above 65536 that is also prime. Conveniently, the first one is 65537. I believe a faster solution would be to add a few lines as below:
public static List<int> Factor(int i) {
int primeIndex = 0;
int prime = PrimeTable[primeIndex];
List<int> factors = new List<int>();
while(i > 1) {
if(primeIndex >= PrimeTable.Count) {
factors.Add(i);
break;
}
else
if(i % prime == 0) {
factors.Add(prime);
i /= prime;
}
else {
++primeIndex;
prime = PrimeTable[primeIndex];
}
}
return factors;
}
This should also allow the program to work for integers up to int.MaxValue . Since we only need to check factors less than the square root of the input, the maximum value we need to check for Math.Sqrt(int.MaxValue) or 46341. If no factors are found up to this point, then the number is prime and is it's own factor.
Ok, all of that said, I wouldn't write this code this way any more. This entire class is a cheat to allow the multiplication of large integers that would overflow a long . Today, we have System.Numerics.BigInteger and I would probably rewrite it to use that, after a quick performance check of course.
Thanks for catching this and sorry you ran into this problem.
Cheers, Adrian






Simple, fast and worth reading as well.





This question is perhaps misplaced. If so, please feel free to ignore.
Your library works a treat, but I'm using it instead of a calculation. Thing is, I don't know how the calculation should go. Here is what I need:
Data: a set of elements 1..n, each with a number of endpoint 1..q
COUNT all possible variations of all the elements, where the elements together can be ordered with their end point.
Example: 2 element, 1 with 2 end points, and 1 with 3 end points (AB and DEF)
These can be ordered as follows
AB
BA
DEF
DFE
...
AB DEF
AB DFE
AB EDF
....
BA DEF
BA DFE
BA EDF
....
DEF AB
DEF BA
DFE AB
etc.
I use your library to first count all variations, ignoring the end points. For example, with 3 elements, 1 with 3 enpoint, and 2 with 2 endpoints:
2
3
2, 2
2, 3
3, 2
2, 3, 2
2, 2, 3
3, 2, 2
etc....
I then, for every combination above, calculate the product of all factorials and add that to the total.
I can optimize this somewhat by using combinations instead of variations, but with a large number of elements, iterating becomes an issue. Parallelism could also help a bit, but still.....
Hence I would like to calculate the total number of possibilities, without having to cycle through the elements. But I can't figure it out. Anybody cares to try and answer this question?
Many thanks.
modified 23Apr13 7:46am.







General News Suggestion Question Bug Answer Joke Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

