如何使用递归计算一组自然数的函数

Question

我正在研究一组给定自然数的属性，它似乎很难计算。我构建了一个函数 'fun'，它接受两个输入，一个是基数值，另一个是集合。如果集合为空，则 fun 应该 return 0，因为 fun 取决于集合的乘积，而 fun 取决于补集的所有子集。

这里有一个例子来说明：

S 是给定 S={1,2,3,4} 的集合。函数 fun(2,S) 定义为

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 定义为集合中所有元素的乘积，例如

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

我正在尝试在 MATLAB 中使用递归方法计算函数 fun 但它不起作用。基本情况是基数值应该大于零，这意味着集合中应该至少有一个元素，否则 prod 将为零并且 fun 将 return 为零。

更新伪代码：

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)
n=|s|
temp=1
for i=1 to n
    temp *=s(i) //s(1) is the 1st element of s
end for
return temp
end prod

谢谢。

Answer 1

使用您添加到问题中的伪代码，几乎不可能实现该功能。所有内容都放在一行中，但不完整（至少缺少外部总和）。

1) 以可用于实施的方式形式化您的算法。以下伪代码可能不正确，因为我不完全知道你想要什么，但它应该给出一个如何去做的想法。

fun(i,S)
if i==0
   return 0
else if |S|=1
   return S
else
  r=0
  for s1 in subsets of S with size i
      f=0
      for s2 in subsets of setdiff(S,s') with size <=i
         f=f+fun(s2,|s2|)
      end
      r=r+prod(s1)*f
  end for
end if
end fun

2) 使用数组 [1,2,3,4] 而不是单元格 {1,2,3,4}

3) prod为内置函数，无需重新实现

如何使用递归计算一组自然数的函数

How to compute a function on a set of natural numbers using recursion

recursion

matlab

computer-science

set

dynamic-programming