查找總和給定數字'n'的'p'數字的排列數

我想解決一個動態規劃問題，部分問題涉及到查找一組'p'數字的排列數將總結爲數字'n'。 p數字組中的每個數字應該在0到n之間（包括0和n）。查找總和給定數字'n'的'p'數字的排列數

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

{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方法。

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

我的基本情況是

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

在P = 3米的地方

（例如n（4,0）是3，它是{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）

我不確定我是否正在朝着正確的方向前進，因爲上述方法不會讓我得到正確的答案。請指導我正確的方向。

來源

2013-06-28 quirkystack

這可能是一個功課問題？ – 2013-06-28 23:32:50

排列部分似乎幾乎完全分開 - 加法是交換和關聯。看起來你可以使用DP來解決一個更簡單的問題：找出總和爲'n'的'p'數的集合數，其中每個集合的成員都有範圍'[0，n]'。然後一旦你有了這些集合，你就可以很容易地計算排列（只記得刪除重複的排列！例如，如果兩個「1」無法區分，那麼'011'只有'3！/ 2！'排列。） – rliu

@MikeW它不是家庭作業..正在嘗試[這]（https://www.hackerrank.com/challenges/count-scorecards）問題 – quirkystack

與我的評論相反，如果我們同時計算集合的數量和這些集合的排列，這個問題實際上更容易解決。

如果我們只需要count而不是實際生成每個集合，我們可以直接使用一些簡單的組合。讓我們來解決p = 3, n = 5我們的例子，假設我們有n = 5球：

o o o o o

現在的問題是等同於多少種方法我們分裂球成3組，其中每組可有[0, 5]球？試想一下，如果我們有可以單獨放置在任何地方的棍棒：所有五個球之前，所有五個球之後，以及任意兩個球之間。例如：

| 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集。請注意，我們只需要p - 1即可生成p數字（第一個棒之前的所有球是第一個組，最後一個棒之後的所有球是最後一個組，兩個棒之間的任何球是其他組）。

所以現在我們的問題是我可以用多少種方式安排我的n球和p - 1支桿？你可以把它想象成有n + (p - 1)插槽，你只是挑選n斑點的球......其餘的都是棍棒去的地方。

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

所以：這樣我們就可以應用組合數學的基本公式它的思考（它使用金額的不言自明的規則和產品的規則...不知道我曾經見過的證據證明）我們的例子是7!/5!/2! = 21。你可以看到在你的例子中它將是6!/4!/2! = 15。你錯過了一些排列組合（例如，{0, 3, 1}）。

你也可以通過一個簡單的遞歸方程來解決這個問題。基本上

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

並記憶一些f的值。這個想法是，你選擇S的第一個成員的值，然後下一個遞歸調用選擇S的下一個成員，依此類推。基本情況可能類似於f(0, p) = 1和f(n, 0) = 0，否則您可以使用遞歸情況。雖然如果你自己實際上不需要這些集合，封閉的表單顯然會有更多的表現。

來源

2013-06-29 01:30:39 rliu

查找總和給定數字'n'的'p'數字的排列數

回答

相關問題