World's most popular travel blog for travel bloggers.

# [Solved]: Algorithm to compute a recursive function on a given set

, ,
Problem Detail:

I am working on a property of a given set of natural numbers and it seems difficult to compute. There is a function 'fun' which takes two inputs, one is the cardinal value and another is the set. If the set is empty then fun should return 0 because fun depends on the product of the set and fun on all subsets of the complement set.

For clarification here is an example:

S is a set given S={1,2,3,4}. The function fun(2,S) is defined as

fun(2,S)=prod({1,2})*[fun(1,{3}) + fun(1,{4}) + fun(2,{3,4})] +           prod({1,3})*[fun(1,{2}) + fun(1,{4}) + fun(2,{2,4})] +           prod({1,4})*[fun(1,{3}) + fun(1,{2}) + fun(2,{2,3})] +          prod({2,3})*[fun(1,{4}) + fun(1,{1}) + fun(2,{1,4})] +          prod({2,4})*[fun(1,{1}) + fun(1,{3}) + fun(2,{3,1})] +          prod({3,4})*[fun(1,{1}) + fun(1,{2}) + fun(2,{1,2})] 

prod is defined as the product of all elements in a set, for example

prod({1,2})=2;  prod({3,2})=6;  

I am trying to write the pseudo code for this problem using recursive method but it's not working. The base case is the cardinal value should be more than zero that means there should be at least one element in the set other wise prod will be zero and fun will return zero.

Pseudo code:

fun(i,S) if |S|=1 && i!=0    return prod(S) else if i==0    return 0      else   prod(subset s', s' is a subset of S and |s'|=i)*(sum over fun((for i=1 to m),{S-s'}), m=|S-s'|) //I don't know how to write code for this part and need help. end if end fun   prod(s) if |s|=0   return 1 else   n=|s| end if temp=1 for i=1 to n     temp *=s(i) //s(1) is the 1st element of set s end for return temp end prod 

Update:I tried to form a mathematical expression of the function fun $fun(m,s)=\sum_{\sigma_{p}\subset s;|\sigma_p|=m}\left [\prod_{i}i\in \sigma_p \sum_{j=1}^{|s-\sigma_p|}\sum_{\gamma_p\subset (s-\sigma_p);|\gamma_p|=j}fun(j,\gamma_p)\right ]$

Where $|s|\geq 1$ and $m\geq 1$

$fun(m,s)=0$ if $s$ is a null set.

#### Answered By : D.W.

You haven't told us what the function is, so we can't give you an algorithm.

However, here's what I can say. There are two general techniques that are often applicable to this setting:

1. Use dynamic programming (or memoization). This will avoid you having to evaluate fun(k,S) more than once for any pair (k,S).

2. Look for mathematical identities that give you different ways to express your function. Sometimes you can find different ways to express your function (e.g., by factoring out common terms or somesuch); if so, look for these, and see if any of them leads to a more efficient algorithm than the others.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/40834

3.2K people like this