递归函数——计数排列和忽略排列

Question

我遇到了这个问题：

我们正在复习我的 class 中的递归，我不太明白，我想知道是否有人可以帮助我解决这个问题

令c(n)为可从整数1到n-1中选择的不同组整数的个数，这样每组中的整数加起来为n（例如，n=4=[1+1+1+1]=[1+1+2]=[2+2]）。写出 c(n) 在以下变体下的递归定义：

a) 你计算排列。例如，1,2,1 和 1,1,2 是两组，每组加起来为 4

b)你忽略排列

我知道排列是指一组数字有多少种排列方式，那么我下面的代码是否正确？我得到的答案是 7? 这是我的 a 部分代码：

int recurse (int n);

int main(){
    int a=4;
    int sum_perm;
    sum_perm=recurse(a);
    cout<<sum_perm-1<<endl; 
    //Can I do -1 here because it should be from a group of integers from 1 to n-1?  
return 0;
}

int recurse(int n)
{
    int sum = 1;
    if (n == 1){
        return 1;
  }
      for(int i = 1; i < n; i++){
              sum += recurse(n - i); 

   }       
return sum;
}

对于 B 部分，如果我不计算排列，我在计算什么？这是我的 b 部分代码：

int without (int n, int max);

int main(){
    int a=4, b =3;
    int sum_without;
    sum_without=without(a,b);
    cout<<sum_without<<endl;

system("Pause");
return 0;
}

int without(int n, int max)

{
    if(n == 1 || max == 1){
        return 1;
}               
    else if (n == max){
        return 1 + without(n, n-1);
        }
    else{
        return without(n,max-1) + without(n-max, max);
        }
}

Answer 1

您没有显示任何代码来生成产生总和的数字组合。 Link 到关于 partitions 的 wiki 文章。

在这种情况下，目标是计算 and/or 排列组合的数量，这可能无需实际生成一组组合。不确定递归在这里是否有帮助，但如果你传递了足够多的变量，你可以将任何循环转换为递归。

示例"partitions"

1 个总和为 1 的组合：

2 个总和为 2 的组合：

1 1
2

3 个总和为 3 的组合：

1 1 1
1 2
3

5 个总和为 4 的组合：

总和为 5 的 7 个组合：

总和为 6 的 11 个数字组合：

1 1 1 1 1 1
1 1 1 1 2
1 1 1 3
1 1 2 2
1 1 4
1 2 3
2 2 2
1 5
2 4
3 3
6

Answer 2

我会推荐直接考虑的组合。虽然这似乎是更困难的情况，但一个简单的规则使它变得微不足道。

Numbers calculated are in decreasing order

这要求您跟踪最后一个数字，但确保您不会计算 1 5 然后 5 1，因为前者是不可能的。

递归函数——计数排列和忽略排列

Recursion function -counting permuation and ignoring permutation

c++

recursion

permutation