排列的递归解决方案

嘿我有一个问题，我需要创建两个函数，countWithPerms（）和ignorePerms（）这两个函数必须是递归解决方案。 countWithPerms（）会计算实际排列的数量，而ignorePerms（）只会计算重复排列的数量。所以如果我将3传入函数countWithPerms（）会发现3 =（2 + 1）=（1 + 2）=（1 + 1 + 2） 1），因此countWithPerms（3）为3，因为它计数3种方式来总结3.由于（1 + 2）和（2 + 1），countIgnorePerms（3）为2，因此它们都不会计入countWithPerms中是正好写在相反的顺序。排列的递归解决方案

大量例子是countWithPerms（7）是63，而countIgnorePerms（7）为14

我已经做countwithPerms，但我完全被卡住的countIgnorePerms。

int countWithPerms(int n) 
{ 
    if(n == 1) 
      return 0; 
    else 
      n--; 
    return (countWithPerms(n) + 1) + 
      (countWithPerms(n)); 
} 

    int ignorePerms(int sum, int xmin){ 
    if(sum == 1) 
      return 0; 

     else 
     for(int i=0; i<sum;i++){ 
      sum += sum-xmin; 
      2*ignorePerms(sum,xmin)+1; 

       return sum; 
    } 
}

来源

2014-02-17 Aaron B

你正在计数分区，而不是排列。 – aschepler

ignorePerms（）被称为[整数分区]（http://en.wikipedia.org/wiki/Partition_（number_theory））和countWithPerms（）被称为[整数组成]（http://en.wikipedia.org/维基/ Composition_（number_theory））。 – Ante

我想你是在排列的地方计算操作。 – Shravan40

不考虑排列计数的思想是只考虑有序的解决方案。

要做到这一点，除了n还有什么是附录必须具有的最小值xmin。例如

3 = 1 + 2

将是确定（因为2> = 1），但

3 = 2 + 1

是不能接受的（因为1 < 2）。

所以这个想法是写一个函数来回答“在第一个附录中有多少个非减少项的和可以给出规定的total不小于min_addendum？”。

如果min_addendum是大于total显然答案是0
如果total是1，那么只有一个总和
否则第一个可能的总和total，那么你应该算作总结
- min_addendum +其他不减少的总和，第一个不小于min_addendum合计total-min_addendum
- min_addendum+1 +其他非递减项的和，所述第一不小于min_addendum+1共计total-min_addendum-1
- min_addendum+2 +其他非递减项的和，所述第一不小于min_addendum+2共计total-min_addendum-2
- ...

来源

2014-02-17 17:48:37 6502

xmin需要设置为什么？ N-1？ –

最初，您将它作为0传递（因为您可以接受任何附录作为第一个），而在递归调用中，您需要传递刚刚添加的值（以确保序列是有序的）。 – 6502

嗯，Im仍然有点困惑，所以我在n被传回后传入，但函数知道n的剂量必须是<然后计算n –

排列的递归解决方案

回答

相关问题