I am trying to find formula which would calculate the number of possible unique combinations which I can later write in programming language. Please excuse my choice of words or terms (and lack of proper math formulas) as my math skills are somewhat limited.
General description and rules:
- you have "n" items which can be "merged" together
- you need at least 2 items to "merge" new one
- if you merge items the original ones are consumed and can't be reused for further "merge"
- at each step you can "merge" only 2 items at once
- it doesn't matter if you merge "a+b" or "b+a" as the resulting new item will be same
- you can continue "merging" the items until you are left with only 1 item
- it's should be calculated using combinations without repetition (order in pair doesn't matter) and maybe permutation?
- there is probably one formula which is valid for any number of "n"
What I have now:
- main part of the formula is combin(n,k) where k=2
- I don't know how to make general formula, so I will write down examples and specific formulas
n=1: n<2, result is 0 n=2: combin(n,2)=1 n=3: combin(n,2)+(combin(n,2)*(n-2))=3+3=6 n=4: combin(n,2)+(combin(n,2)*(n-2))+(combin(n,2)*(n-2)*(n-3))=6+12+12=30 n=5: following same logic..
At this stage I have thought that I have covered all combinations, so I have tried to manually list them for verification. For n<=3 it worked fine, but for n=>4 I have realised that I am missing what I internally called "inner" combinations. Here is my try to represent all n=4 combinations, where the "inner" ones are the last 3:
a+b a+c a+d b+c b+d c+d ab+c ab+d ac+b ac+d ad+b ad+c bc+a bc+d bd+a bd+c cd+a cd+b abc+d abd+c acb+d acd+b adb+c adc+b bca+d bcd+a bda+c bdc+a cda+b cdb+a ab+cd ac+bd bc+ad
This gave me 33 combinations whereas I was expecting only 30, so my assumption is that either the formula is wrong (more complicated) or some of the combinations listed above are in fact duplicate although it doesn't seems so.
I was trying to wrap my head around this, googling many examples of combinations and trying to fit them to my problem, but without any luck. Also I was trying to consult it with some friends of mine, but none offered any real insight, so I am trying my luck here as my knowledge in this field of math is limited.
I have currently implemented version with above formula, but it's not very effective solution as I am running out of memory at certain number of items and "depth". Depth is my internal term and parameter which I am using to limit the number of combinations the program is checking. I guess it can be considered as number of iterations? The reason why I am running out of memory is that I am storing the result of previous "depth" and calculating next one. I know there should be a better way how to do it and after reading some more articles about combinatorics I am starting to think about it as a tree structure. This should give me possibility to reduce the memory footprint to minimum and be going through the combinations like through branches. This in theory should also allow me to implement some multi-threading and take advantage of multi core processors.
- Is the formula correct or not?
- If it's correct how it can be simplified?
- If it's wrong how should look correct one?
- Any general idea how to program it?
I would be grateful for any help regarding this problem and if something is unclear or missing please let me know.