# Generating combinations

• May 11th 2009, 11:27 PM
82026
Generating combinations
we have integer N = 1*n1+2*n2+3*n3+4*n4+5*n5+6*n6+7*n7+8*n8+9*n9 .
How to calculate total possible number of n1..n9 combinations?
n can be any positive integer including 0.
Also algo to generate all of that combinations?
• May 12th 2009, 06:51 AM
Media_Man
Clarification
Just to clarify your notation here, are you saying:

(1) $\displaystyle N = n^1+2n^2+3n^3+4n^4+5n^5+6n^6+7n^7+8n^8+9n^9$

or

(2) $\displaystyle N = n_1+2n_2+3n_3+4n_4+5n_5+6n_6+7n_7+8n_8+9n_9$

I believe you are referring to (2) here. Are you seeking a computer program that will input N and count all possible solutions $\displaystyle (n_1,n_2,...,n_9)$ - easy - or are you looking for a mathematical formula $\displaystyle f(N)$ that will tell you how many solutions there are - hard?
• May 12th 2009, 10:33 AM
82026
Quote:

Originally Posted by Media_Man
Just to clarify your notation here, are you saying:

(1) $\displaystyle N = n^1+2n^2+3n^3+4n^4+5n^5+6n^6+7n^7+8n^8+9n^9$

or

(2) $\displaystyle N = n_1+2n_2+3n_3+4n_4+5n_5+6n_6+7n_7+8n_8+9n_9$

I believe you are referring to (2) here. Are you seeking a computer program that will input N and count all possible solutions $\displaystyle (n_1,n_2,...,n_9)$ - easy - or are you looking for a mathematical formula $\displaystyle f(N)$ that will tell you how many solutions there are - hard?

Yes, I mean (2). I'm writing computer program where I need to esimate total number of possible solutions for given N and then rank all of them not trying the same combination twice. Actually the problem turns in to finding all possible combinations. Then is easy to count them. But how to eficiently find all possible combinations?
• May 12th 2009, 11:35 AM
Media_Man
The Partition Problem
This question is equivalent to finding all possible partitions of N, restricting the number of terms to 9.

Start with $\displaystyle N = n_1+2n_2+3n_3+4n_4+5n_5+6n_6+7n_7+8n_8+9n_9$

Define $\displaystyle m_i=n_i+n_{i+1}+...+n_8+n_9$ And you can see that $\displaystyle N=m_1+m_2+m_3+m_4+m_5+m_6+m_7+m_8+m_9$. In other words, all possible partitions of the number N with no more than 9 terms. By construction, $\displaystyle n_i=m_{i} - m_{i+1} \geq 0$ .

Example. Let N=8.

$\displaystyle m_1+m_2+m_3+m_4+m_5+m_6+m_7+m_8+m_9$
8
7 + 1
6 + 2
6 + 1 + 1
5 + 3
5 + 2 + 1
5 + 1 + 1 + 1
4 + 4
4 + 3 + 1
4 + 2 + 2
4 + 2 + 1 + 1 $\displaystyle \rightarrow n_1=4-2=2, n_2=2-1=1, n_3=1-1=0, n_4=1-0=1$$\displaystyle \rightarrow 1(2)+2(1)+3(0)+4(1)=8$
4 + 1 + 1 + 1 + 1
3 + 3 + 2
3 + 3 + 1 + 1
3 + 2 + 2 + 1
3 + 2 + 1 + 1 + 1
3 + 1 + 1 + 1 + 1 + 1
2 + 2 + 2 + 2
2 + 2 + 2 + 1 + 1
2 + 2 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

So you see, by indexing each partition of 8, you can directly get a solution to your equation from each one by letting $\displaystyle n_i=m_i - m_{i+1}$ for each i.

I am not familiar with resources from which to get free code, but I'm sure someone somewhere on the net can provide you with the code for a getPartitions(int N) method. You simply want to restrict yourself to those with no more than 9 terms.

*This code is relatively easy to implement, but in number theory, as you may know, the partition function P(n)="the number of partitions of n" is a famously complicated one. I don't think that limiting them to 9 terms makes it any simpler either.
• May 12th 2009, 12:13 PM
82026
Thanks! Will try to implement this in code an see how it works. But idea looks very right!