Re: asking suggestions on the algorithm in compution.Thanks.

From: David B. Chorlian (davidc_at_panix.com)
Date: 10/29/04 

Date: Fri, 29 Oct 2004 16:46:10 +0000 (UTC)

In <9e847e5e.0410290733.2b198d62@posting.google.com> buaanupt@sina.com (ZHANG Yan) writes:

>Thank you very much for your comments. I am very sorry that I have not
>stated the questions very clearly. Hope that the following is more
>clear.

>//////////////////////////////////////////////////////////////////////
>Input: k,A,b
>//k is integer; A is integer; b is integer
>Output:X

>X = 0.0
>for k = 1..A
> for all possible set (m_1,m_2,...,m_k) satisfying m_1+m_2+...+m_k =
>b
> X = X + f_1(m_1) * f_2(m_2) * ... * f_k(m_k)
> end
>end

>//in this algorithm, f_i(m_i) is a function with m_i as input.

Assuming that m_1, ... m_k are integers, look at the problem
for a fixed k. Then each f_k() will be called with the same
arguments added the same number of times as any other f_k().
Then, e.g. each f_k() will be called with the value b once,
with the value b - 1 k - 1 times, with the value b - 2 k - 1
+ (k - 1) * (k - 2)/2 times ...
so this is really a combinatorics problem.

>The difficulty lies in the fact that there are too many possible
>combination of set (m_1,m_2,...,m_k) satisfying m_1+m_2+...+m_k = b.
>So, the number of cycle is ver high.

You don't have to enumerate the combinations, you just have to
count them.

>Can you plz give some suggestions in reduce the computation time and
>complexity? Thank you very much.
>--
>Y.ZHANG 

-- 
David B. Chorlian
Neurodynamics Lab  SUNY/HSCB
chorlian@cns.hscbklyn.edu
davidc@panix.com

Relevant Pages