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


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:

if |S|=1 && i!=0
   return prod(S)
else if i==0
   return 0     
  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 

if |s|=0
  return 1
end if
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.

  • 1
    $\begingroup$ So what you refer to as prod is often written in mathematics as $\Pi$, i.e., $prod(\{2,3,4\}) = \Pi_{i \in \{2,3,4\}} i = 2 \cdot 3 \cdot 4$. However, since 1 is the multiplicative identity, $\Pi \emptyset = 1$. So you should set up your base case accordingly, i.e. prod([]) = 1. $\endgroup$ – Pål GD Mar 29 '15 at 1:06
  • $\begingroup$ Its no clear what the function fun does, can you write the formula equivalence $\endgroup$ – jonaprieto Mar 29 '15 at 7:33
  • $\begingroup$ You're apparently looking for an algorithm to compute some function, but you haven't told us what the function is. Please edit the question to add the specification of your function fun. At present, you have only given us an example (an example of how to compute the function for one example input), but an example is not a definition or specification of the function. We can't tell you what algorithm to use if you don't tell us what your function is. $\endgroup$ – D.W. Mar 29 '15 at 19:45
  • $\begingroup$ I update with the expression of fun. Sorry for my late reply. $\endgroup$ – precision Mar 31 '15 at 2:11

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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.