寻找的'P'号的总和排列的数字的给定数'N' [英] Finding number of permutations of 'p' numbers that sum to a given number 'n'

问题描述

我试图解决一个动态规划问题，部分问题涉及寻找 一组的'p'的数字，将总结为数字n的排列的数量。 在集合P数的各个数字应该介于0到n的包容性。

I am trying to solve a dynamic programming problem and part of the problem involves finding number of permutations of a set of 'p' numbers that will sum up to a number 'n'. Each number in the set of p numbers should be between 0 to n inclusive.

例如如果n = 4和P = 3，我有以下12排列

For example if n = 4 and p = 3, I have the following 12 permutations

{4,0,0},{0,4,0},{0,0,4}
{2,2,0},{2,0,2},{0,2,2}
{1,3,0},{1,0,3},{0,1,3}
{1,1,2},{1,2,1},{2,1,1}

我开始与该DP方法。

I started with this DP approach.

n(i,j) represents number of ways of representing n using i,j in p positions 

我的基本情况是

My base case would be

n(i,0) = n(0,i) = p   

（例如n（4,0在P）= 3个地方是3，它为{4,0,0}，{0,4,0}，为0,0,4}

(for example, n(4,0) in p=3 places is 3 which is {4,0,0},{0,4,0},0,0,4}

递归情况

n(i,j) = n(i,j-1)*n(i-1,j)

（例如：N（1,2）= N（1,1）* N（0,2）的递归到n（1,0）* N（0,1）* 2）

(example : n(1,2) = n(1,1) * n(0,2) which recurses to n(1,0) * n(0,1) * 2)

我不知道如果我继续在正确的方向上面的方法不会导致我一个正确的答案。请指引我正确的方向前进。

I am not sure if I am proceeding in the right direction as the above approach doesn't lead me to a correct answer. Please guide me in the right direction.

推荐答案

相反，我的意见，这个问题其实很容易解决，如果我们计算的组数和那些套在同一时间的排列。

Contrary to my comment, this problem is actually easier to solve if we count the number of sets and the permutations of those sets at the same time.

如果我们仅仅需要的计数的而不是实际上产生每个组的，我们可以如此直接用一些简单的组合学做。让我们来解决 P = 3，N = 5 我们的例子，假设我们有 N = 5 球：

If we only need to count instead of actually generating each of the sets, we can do so directly with some simple combinatorics. Let's fix p = 3, n = 5 for our example and imagine that we have n = 5 balls:

o o o o o

现在的问题就相当于，有多少种方法我们才能分裂球成 3 ，每个组可以有 [0，5组] 球？试想一下，如果我们有对 - 1 = 2 坚持，我们可以单独放置在任何地方：所有的五个球前，所有五个球后，和之间的任何两个球。例如：

Now the question is equivalent to, how many ways can we split the balls into groups of 3 where each group can have [0, 5] balls? Imagine if we had p - 1 = 2 sticks that we could individually place anywhere: before all five balls, after all five balls, and between any two balls. For example:

| o o | o o o => (0, 2, 3)
o | | o o o o => (1, 0, 4)
o o o o | | o => (4, 0, 1)

注意的问题是如何等价？总之，我们可以把那些棍棒，我们也可以划分我们的 N 球放入 P 集。请注意，我们只需要对 - 1 坚持以生成 P 号（所有的球之前，第一棒是第一组，最后一棒后，所有的球都是在最后一组，二节棍之间的任意球是其他组）。

Notice how the questions are equivalent? Anyway we can put those sticks, we can also partition our n balls into p sets. Notice that we only need p - 1 sticks to generate the p numbers (all the balls before the first stick are the first group, all the balls after the last stick are the last group, any balls between two sticks are the other groups).

所以，现在我们的问题是，有多少种方法我可以安排我的 N 球和对 - 1 棒？你可以把它看作是具有 N +（P - 1）插槽和你是刚刚采摘 N 点的球......其余的都在那里了棍子去。它这样想的，我们可以应用组合数学的基本公式（它使用金额的不言自明的规则和产品的规则...不知道我曾经见过的证据证明）：

So now our question is how many ways can I arrange my n balls and p - 1 sticks? You can think of it as having n + (p - 1) slots and you are just picking the n spots for the balls... and the rest are where the sticks go. Thinking of it this way we can apply a basic formula of combinatorics (it's proven using the axiomatic rule of sum and rule of product... not sure I've ever even seen the proof):

(n + (p - 1)) Choose n = (n + (p - 1))! / n! / (p - 1)!

因此​​，在我们的例子中，它的 7！ / 5！ / 2！ = 21 。你可以看到，在你的榜样，这将是 6！ / 4！ / 2！ = 15 。你错过了一些排列（例如， {0，3，1} ）。

So in our example, it's 7! / 5! / 2! = 21. And you can see that in your example it would be 6! / 4! / 2! = 15. You missed a few permutations (for example, {0, 3, 1}).

您还可以通过一个简单的递归式解决这一带DP。基本上

You can also solve this with DP by a simple recursive equation. Basically

`f(n, p) = Sum over i = 0 to n, f(n - i, p - 1)`

和memoize的一些的值F的。我们的想法是，你挑你的设置的第一个成员的值取值再接下来递归调用挑选 S的下一个成员等。该基地的情况下可能会是这样的 F（0，P）= 1 和 F（N，0）= 0 否则，您可以用递归的情况下。封闭的形式显然是一个很大的高性能但如果你实际上并不需要设置自己。

and memoize some of the values of f. The idea is, you pick the value for the first member of your set S and then the next recursive call picks the next member of S and so on. The base cases would probably be something like f(0, p) = 1 and f(n, 0) = 0 and otherwise you can use the recursive case. The closed form is obviously a lot more performant though if you don't actually need the sets themselves.

这篇关于寻找的'P'号的总和排列的数字的给定数'N'的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！