n個球放入m個盒子，使用程序輸出所有的放法？

01-07

需要用程序解決一個問題，其中一個模塊遇到一些困難，將其模型簡化為：
有n個相同的球，m個盒子（編號為1,2,……m），將這n個球放入這m個盒子中，要求輸出所有可能的放置方法（當然，有m^n种放法（感謝@paintsnow 指出，並不是m^n種）），輸出格式為二維數組（如下例子），每行對應每個可能性，每列對應每個盒子中的球數。
例如：3個球，5個盒子，可能的放法有：
30000
21000

11100
10101
……等
查了一些書，感覺需要使用遞歸的方法，但是本人編程底子太差，有點搞不來。
請教各位大神，怎麼設計編程演算法？
如果有大神想要直接貼出代碼，最好是C語言或者MATLAB。
謝謝。
==========分割=========
以下是2016年10月11日15:52更新

截止目前，此問題已有8934次瀏覽，120人關注，14個回答。感謝各路大神的幫助。
感謝@Milo Yip 提供遞歸思路以及C程序代碼。
感謝@羅宸給出的Haskell程序思路及代碼，還有詳細的講解。
感謝@paintsnow 和@yuejunwei 給出的答案數量級的估計。
感謝@hearts zh 給出的演算法原理方面的資料，雖然題主水平有限，看的不是太懂……
感謝@梁少聰提供的非遞歸思路，依然主水平有限，看的不是太懂……
感謝@winner245 給出的三行MATLAB代碼，題主琢磨了半天，仍然知其然不知其所以然……
感謝@hjiayz 給出的（貌似是）C++程序。
感謝第一個回答此問題的@周成提供的暴力解法。

感謝@Partrick 提供的Swift程序。
最後，一併感謝每一個看過這個問題的，回答這個問題的以及評論過這個問題的朋友，謝謝你們的耐心。
========分割線========
以下是本人參考各位的答案自己寫的MATLAB代碼，主要使用的是@Milo Yip 的演算法思路，歡迎各位大神提出寶貴意見。
fillbox.m:
function fillbox_f(n,m) global pb np pb=[]; np=0; r=zeros(1,m); ff(n,m,r); end
ff.m:
function ff(n,m,r) global pb np if m==1 pb(np+1,:)=r; pb(np+1,m)=n; np=np+1; else for i=0:1:n r(m)=i; ff(n-i,m-1,r); end end end
代碼結束。
調用：

fillbox_f(3,5);
結果：
========分割線======
2016年10月11日16:19
圖都貼上了才發現程序還有問題，算錯了，debug……
======分割線======
2016年10月11日17:26
已重新上傳程序代碼

----------2016-10-12日更新-------------

感謝大家茲磁，實在沒想到會有這麼多人對Haskell的代碼感興趣，既然感謝那自然要拿出點誠意，給大家補一個計算方案數的代碼吧，放最後面了。

------------------------------------------------

忍不住要吐槽一句：我不知道是有多無聊的人才會給這個認真回答問題的答案點反對，讓這個答案排在了一些零贊答案的後面。 看不懂可以無視，可以忽略，但請不要傷害認真答題的答主，OK？

------------------原回答---------------------

額，C的 @Milo Yip 大大已經給了，我手癢寫了個Haskell的。。。也許題主能看懂。。

place :: Integer -&> Integer -&> [[Integer]] --place n balls into m boxes place 0 0 = [[]] place n 0 = [] place n m = [k:rs | k &<- [0..n], rs &<- (place (n-k) (m-1))]

效果：

*Main&> place 3 5 [[0,0,0,0,3],[0,0,0,1,2],[0,0,0,2,1],[0,0,0,3,0],[0,0,1,0,2],[0,0,1,1,1],[0,0,1,2,0],[0,0,2,0,1],[0,0,2,1,0],[0,0,3,0,0],[0,1,0,0,2],[0,1,0,1,1],[0,1,0,2,0],[0,1,1,0,1],[0,1,1,1,0],[0,1,2,0,0],[0,2,0,0,1],[0,2,0,1,0],[0,2,1,0,0],[0,3,0,0,0],[1,0,0,0,2],[1,0,0,1,1],[1,0,0,2,0],[1,0,1,0,1],[1,0,1,1,0],[1,0,2,0,0],[1,1,0,0,1],[1,1,0,1,0],[1,1,1,0,0],[1,2,0,0,0],[2,0,0,0,1],[2,0,0,1,0],[2,0,1,0,0],[2,1,0,0,0],[3,0,0,0,0]]

思路就是，用 place n m 表示把n個球放進m個盒子的所有方案（每個方案用一個列表表示），然後place函數的實現只有三行，每一行枚舉一個base case，就不細說了。。

好吧，考慮到Haskell的語法有點生僻，還是說一下吧。。

第零行，這個是類型簽名，用來聲明place函數的類型，可以忽略，忽略後類型由編譯器自己推斷，不影響運行。

第一行，place 0 0 = [[]]，意思是，把0個球放進0個盒子有一個方案，這個方案用一個空列表表示（因為是0個盒子）

第二行，place n 0 = []，這裡因為n=0的情況被上一行代碼處理了，所以意思是，把n個（n非0）球放進0個盒子，有0個方案

第三行，就是說，把n個球放進m個盒子，相當於在第一個盒子放k個球，在剩下的盒子里，分別放rs個球，而rs是來自將(n-k)個球放進(m-1)個盒子的方案集合中的一個。

你看，這代碼是不是跟白話一樣？

所以吧，編程底子差的話，還是學Haskell這種無腦語言比較合適。 C神馬的，又是假設，又是assert的，太複雜了，看不懂。。。

------------------------------------------------------

看到各位C大大們還在給自己代碼打補丁。咳咳，抱歉，也許我上面說得不夠清楚。。。

其實，那些限制完全不是問題的關鍵，主要是為了調侃效果對吧。

為了弘揚佛法，不對，是Haskell大法，

也為了給大大們節省時間，以及讓小白們不要再浪費生命（去學C），

我決定再補一刀（注意以下對place函數的應用均完全不改變place函數的實現代碼）：

比如我現在不想列印所有方案了，我只想知道方案總數：

*Main&> length (place 3 5) 35

再比如，我覺得列印所有方案太多，我只想看5個：

*Main&> take 5 (place 3 5) [[0,0,0,0,3],[0,0,0,1,2],[0,0,0,2,1],[0,0,0,3,0],[0,0,1,0,2]]

再比如，我想看看這些方案里，出現3的方案（即把3個球放進同一個盒子的方案）有哪些：

*Main&> filter (any (== 3)) (place 3 5) [[0,0,0,0,3],[0,0,0,3,0],[0,0,3,0,0],[0,3,0,0,0],[3,0,0,0,0]]

再比如，我想看看，假如盒子沒有編號，那麼等價的方案去重之後，有哪些方案：

*Main Data.List&> (nub . map sort) (place 3 5) [[0,0,0,0,3],[0,0,0,1,2],[0,0,1,1,1]]

（註明：這裡 *Main Data.List&> 這一坨是GHCI的命令提示符，符號前面的部分表示引入了哪些module，符號後面才是我們輸入的代碼，緊接著的第二行是輸出結果）

再次提醒，這後面的所有應用都不需要改變place這個函數的實現哦。並且這個程序不會出現什麼整數溢出或者數據越界等狀況，只要提供足夠的時間和相對於輸入規模合理的內存，它就能算出結果。

請最後跟我一起念：哈斯K耳大法好。

--------------補一個計算方案數的-------------

（這裡為了效率不得不用了一個看起來比較難懂的memoFix函數，但是基本思路和place函數是一樣的）

import Data.Function.Memoize

placeCount :: (Integral a, Memoizable a) =&> a -&> a -&> Integer placeCount n m = memoFix2 p n m where p p" 0 0 = 1 p p" n 0 = 0 p p" n m = sum [x | k &<- [0..n], let x = (p" (n-k) (m-1))]

效果：

*Main&> placeCount 5 5 126 *Main&> placeCount 10 10 92378 *Main&> placeCount 50 50 50445672272782096667406248628 *Main&> placeCount 100 100 45274257328051640582702088538742081937252294837706668420660 *Main&> placeCount 200 200 51476250067707216486487940160200993378605462690538824117424529787961666186325979299168297759488246475782024298753387060

遞歸解：

#include &

void f(int* r, int* p, int n, int m) { if (m == 1) { for (; r != p; ++r) printf("%d ", *r); printf("%d ", n); } else for (*p = 0; *p &<= n; ++*p) f(r, p + 1, n - *p, m - 1); } void g(int n, int m) { int r[m]; // C99 VLA f(r, r, n, m); } int main() { g(3, 5); }

r 用於記錄當前的結果，p 是寫入該緩存的位置。那麼，f(r, p, n, m) 的意義就是把 n 個球放進 m 個盒子，如果只有1個盒子了就列印結果（最後一個盒子有 n 個球）；如果有&>1個盒子，就放入 0 至 n 個球至當前的盒子，把餘下的球和盒子以遞歸調用 f()。

更新實現。原答案往下拉。

看起來很複雜，其實Q7和部分Q2在題主的題目條件下可以簡化（原答案是一個更泛化的演算法）。

稍微實現如下（已經按題主題目簡化了）：

該演算法的好處：

（1）可以修改成更generalized的問題（見演算法解答）

（2）無需遞歸，即可以解決幾乎無限的解（當然需要時間），不受遞歸層次限制。

（3）快，沒有遞歸，肯定快不少（雖然對小問題來說沒意義）。

該演算法實現其實並不難懂。自己用一個小數字手動算一下就理解了。

#include &


void f(int numBalls, int numBins)

{

  int q[numBins];

  int x = numBalls;
  int i = 0;

  int j = 0;
  for (i = 0; i &< numBins; i++) { q[i] = 0; }

  while (1) {
    //Q2
    j = 0;
    q[0] = x;

    while (1) {
      //Q3
      for (i = numBins - 1; i &>= 0; i--) {

        printf("%d ", q[i]);

      }

      printf("

");
      //Q4

      if (j == 0) {

        x = q[0] - 1;

        j = 1;

      } else if (q[0] == 0) {

        x = q[j] - 1;

        q[j] = 0;

        j++;

      }
      //Q5

      if (j &>= numBins) {

        return; // finished, exit

      } else if (q[j] == numBalls) {

        x = x + numBalls;

        q[j] = 0;

        j++;

        if (j &>= numBins) {

          return; // finished, exit

        }

      }
      //Q6

      q[j]++;

      if (x == 0) {

        q[0] = 0;

        continue; // goto Q3

      } else {

        break; // goto Q2

      }

} } } int main() { f(3, 5); return 0; }

============

taocp解答。。

本問題屬於 n-multicombinations of m things。

該問題的演算法在taocp Chapter 7.2.1.3 練習題里。

答案如下：

更新：借鑒評論區 @Falccm 的辦法，可以繼續簡化為 one-liner：

function y = f2(n,m) y = filter([1 -1],1,[nchoosek(1:m+n-1,m-1) zeros(nchoosek(m+n-1,n),1)+m+n],[],2) - 1; end

另外，上述nchoosek(1:m+n-1,m-1)的調用換成FEX上的VChooseK(1:m+n-1,m-1)能快很多，但VChooseK不能計算組合數，所以第二個nchoosek(m+n-1,n)不能用VChooseK替換，但即便如此，第二個nchoosek也只是計算一個標量組合數，並不會拖慢效率。

---------------------------------------------------------------------

@圖圖：

從我最開始的三行代碼、到評論區 @Falccm 的兩行代碼、再到我更新的一行代碼，思路都是一樣的。有兩種方法來理解：第一種是借用@paintsnow 黑白子的思路，即把n+m-1個白球排成一列，任意選取其中m-1個球染成黑色作為分割線，則正好將所有白球分割成m份（包括首尾兩端），因此每一個分割里的白球數目就可以看作是一個盒子中放的球的數目。最後，只要找出在n+m-1個位置中選取m-1個分割線的所有組合即可。

第二種理解方法（答主是依照此思路）：將「n個相同球放入m個不同盒子」看作是將n分解成m個非負整數求和，每一種分解方法對應一種球的放法。具體的分解辦法是：將n個1和m-1個分隔符任意放入m+n-1個方格中，則n個1被自動分隔成m份，每一份里1的個數對應了一個盒子中放置球的個數。

以上兩種思路其實是一致的，都是在m+n-1個位置里放入m-1個分隔符，再計算每一份里的個數即可。分隔符的位置可以通過nchoosek(1:m+n-1,m-1)來產生, 前面我提供的三行代碼里，就是先將分隔符儲存為數字1（通過accumarray實現），而每一份里的數字元素存儲為0。通過filter實現了分隔符1的位置間的逐差運算，從而得到每一份分割里的0元素個數，它就是每一個盒子里所放球的個數。

後來 @Falccm 的兩行代碼改進在於：沒有必要真正將1（分隔符）寫入存儲（即accumarray那一步可以避免），直接根據nchoosek(1:m+n-1,m-1)產生得到的1位置做逐差即可，只不過 @Falccm 是用diff代替了filter來實現逐差，這樣，就需要在逐差向量首尾都補充1個元素才能在結果里包含兩端的個數（filter逐差的話，會自動得到首端的個數，但仍需在尾部需要補1個元素來計算尾部的個數）。

最後的一行代碼與上面的兩行代碼思路完全相同，即都不需要真正去存儲分隔符。仍然使用filter來實現逐差，最終將代碼壓縮至了一行。

--------------------------------------------------------------------

補充一個MATLAB實現(n個相同球放入m個不同盒子)：

function y = f(n,m) r = nchoosek(1:n+m-1,m-1); subs = {r(:) repmat((1:size(r,1)).",m-1,1)}; y = reshape(filter([1 -1],1,find([accumarray(subs,1); ones(1,size(r,1))])),m,[])."-1; end

&>&> f(2,4)

ans =

0 0 0 2

0 0 1 1

0 0 2 0

0 1 0 1

0 1 1 0

0 2 0 0

1 0 0 1

1 0 1 0

1 1 0 0

2 0 0 0

來練個手。。。

根據隔板法，一种放法和C(n+m-1,n)的一種可能一一對應，那麼找出所有的C(n+m-1,n)就可以找出所有的放法，下面用一個0~2^(n+m)的整數來表示組合的所有可能性

非遞歸版本哦

//putBalls.js "use strict"; function next(n) { var lastOne = n^n(n-1); var rest = n/lastOne; var ones = ((rest ^ (rest | rest + 1)) - 1) &>&>&> 1; return n + lastOne + ones; }


function interp(n, length) { // interprate combination to array

    var str = n.toString(2);

    var remainLength = length - str.length;

    var zeros = Array.from(str.split("1"), (v, k)=&>{return v.length});

    zeros[0] += remainLength;

    return zeros;

}

module.exports = function* putBalls(n, m) { var max = Math.pow(2, m + n - 1) - 1; // n balls and m - 1 boards var current = Math.pow(2, m - 1) - 1; // m - 1 boards for(; current &< max; current = next(current)) { yield interp(current, m + n - 1); } } &> putBalls = require("./putBalls.js") [Function: putBalls] &> iterator=putBalls(3,5) {} &> for(let next=iterator.next();!next.done;next=iterator.next()){console.log(next)} { value: [ 3, 0, 0, 0, 0 ], done: false } { value: [ 2, 1, 0, 0, 0 ], done: false } { value: [ 2, 0, 1, 0, 0 ], done: false } { value: [ 2, 0, 0, 1, 0 ], done: false } { value: [ 2, 0, 0, 0, 1 ], done: false } { value: [ 1, 2, 0, 0, 0 ], done: false } { value: [ 1, 1, 1, 0, 0 ], done: false } { value: [ 1, 1, 0, 1, 0 ], done: false } { value: [ 1, 1, 0, 0, 1 ], done: false } { value: [ 1, 0, 2, 0, 0 ], done: false } { value: [ 1, 0, 1, 1, 0 ], done: false } { value: [ 1, 0, 1, 0, 1 ], done: false } { value: [ 1, 0, 0, 2, 0 ], done: false } { value: [ 1, 0, 0, 1, 1 ], done: false } { value: [ 1, 0, 0, 0, 2 ], done: false } { value: [ 0, 3, 0, 0, 0 ], done: false } { value: [ 0, 2, 1, 0, 0 ], done: false } { value: [ 0, 2, 0, 1, 0 ], done: false } { value: [ 0, 2, 0, 0, 1 ], done: false } { value: [ 0, 1, 2, 0, 0 ], done: false } { value: [ 0, 1, 1, 1, 0 ], done: false } { value: [ 0, 1, 1, 0, 1 ], done: false } { value: [ 0, 1, 0, 2, 0 ], done: false } { value: [ 0, 1, 0, 1, 1 ], done: false } { value: [ 0, 1, 0, 0, 2 ], done: false } { value: [ 0, 0, 3, 0, 0 ], done: false } { value: [ 0, 0, 2, 1, 0 ], done: false } { value: [ 0, 0, 2, 0, 1 ], done: false } { value: [ 0, 0, 1, 2, 0 ], done: false } { value: [ 0, 0, 1, 1, 1 ], done: false } { value: [ 0, 0, 1, 0, 2 ], done: false } { value: [ 0, 0, 0, 3, 0 ], done: false } { value: [ 0, 0, 0, 2, 1 ], done: false } { value: [ 0, 0, 0, 1, 2 ], done: false } { value: [ 0, 0, 0, 0, 3 ], done: false } undefined

很慚愧這個東西如果直接寫成C的話只能算m+n &< 64，超過了next裡面就要用simd，或者手動多次運算，複雜度變成O((m+n)/64)

時間複雜度：耗時在interp，O((m+n)C(m+n-1,n))，對於超大的整數，next從常數變成線性，複雜度不變

@Milo Yip 大神已經給出完美解法了==我補充點經驗

關於這種問題，快速估計出答案的數量級，能夠很好地幫助我們設計演算法。

原問題其實相當於把n+m-1個白球排成有序的一列，然後把其中m-1個球染成黑色作為分割線，相鄰兩個黑球之間或者兩端的白球列就可以看作是一個盒子中放的球。那麼方案數C為 $inom{n+m-1}{n}$ .

由於這個組合數是和階乘同階的，所以是不能通過有限次線性循環（即每次循環的次數是N或者M的線性函數）來完成的。

很明顯，既然我們已經知道了總數，那麼必然存在參數為m的函數F(n)，對於給定的從1..C的n，對應唯一的序列。但是在實際的程序設計中，這部分你也經常得去拼字元串，因為1..C的順序可能並不利於緩存可復用的局部結果。因此直接遞歸，簡潔明快又不容易出錯。

該問題同構於https://en.wikipedia.org/wiki/Partition_(number_theory)

以下三種思路,都可以一行內搞定

{n,m}={5,3}; Join@@((Permutations@PadLeft[#,n])/@IntegerPartitions[m,n]) Cases[Tuples[Range[0,n-1],n],a_List/;Total@a==m] Pick[#,Plus@@@#-m,0][Tuples[Range[0,m],n]]

允許用Mathematica的專有函數還可以更短一點

FrobeniusSolve[ConstantArray[1,5],3]

對於解得個數有個估計上界 $[p(n) = frac{{{e^{pi sqrt {frac{{2n}}{3}} }}}}{{4nsqrt 3 }}]$

有編號的話解的個數上界就是2^p(n)

有的人不要無賴秀智商,這個問題一點都不簡單...

來個中規中矩的Python吧。

def put_balls_into_boxes(n, m, l, idx): if m == 0: l[idx] = n print(l) return


    for i in range(n+1):

        l[idx] = i

        put_balls_into_boxes(n-i, m-1, l, idx+1)

n = 3 m = 3 l = [0 for i in range(0, m)] put_balls_into_boxes(n, m-1, l, 0)

[0, 0, 3]

[0, 1, 2]

[0, 2, 1]

[0, 3, 0]

[1, 0, 2]

[1, 1, 1]

[1, 2, 0]

[2, 0, 1]

[2, 1, 0]

[3, 0, 0]

#include & #include &

void print_array(char *p, int n) { int i; for(i = 0; i &< n; i++) printf("%2d", p[i]); printf(" "); } void pattern(char *p, int n, int start, int left) { if(left == 0){ print_array(p, n); return; } int i; for(i = start; i &<= n - 1; i++){ p[i]++; pattern(p, n, i, left - 1); p[i]--; } } int main(int argc, char **argv) { if(argc != 3){ printf("Usage: %s & & ", argv[0]); return 0; } int left = atoi(argv[1]); int n = atoi(argv[2]); char *p = calloc(n, sizeof(char)); pattern(p, n, 0, left); free(p); return 0; }

$ ./a.out 2 4 2 0 0 0 1 1 0 0 1 0 1 0 1 0 0 1 0 2 0 0 0 1 1 0 0 1 0 1 0 0 2 0 0 0 1 1 0 0 0 2

首先問題描述里關於共有N^M(N的M次冪)种放置方法的說法是錯誤的，當N個球M個盒子都各不相同時才是N^M種，球都相同時分配方式要少得多，請搜索小學奧數的「插板法」：

鑒於某些盒子內可能分不到球，所以要先額外補充M個（也就是盒子的數量）「雪球」，並將題目等價轉換為每個盒子至少分配到一個球（雪球也是球，但分配完畢後就融化消失），這樣題目就成了N+M個球要分成M份，也就是N+M個球之間的N+M-1個間隙中放置M-1個隔板。以3個球5個盒子為例，就是3+5-1=7個間隙中放置5-1=4個隔板將3+5=8個球分成5份，也就是C(7,4)，7個中選4個的組合，數量為35。

Erlang版程序如下：

Eshell V7.2.1 (abort with ^G) 1&> P = fun F(N,1) -&> [[N]]; F(N,M) -&> [[H|T] || H &<- lists:seq(0,N), T &<- F(N-H,M-1)] end. #Fun& 2&> P(3,5). [[0,0,0,0,3], [0,0,0,1,2], [0,0,0,2,1], [0,0,0,3,0], [0,0,1,0,2], [0,0,1,1,1], [0,0,1,2,0], [0,0,2,0,1], [0,0,2,1,0], [0,0,3,0,0], [0,1,0,0,2], [0,1,0,1,1], [0,1,0,2,0], [0,1,1,0,1], [0,1,1,1,0], [0,1,2,0,0], [0,2,0,0,1], [0,2,0,1,0], [0,2,1,0,0], [0,3,0,0,0], [1,0,0,0,2], [1,0,0,1,1], [1,0,0,2,0], [1,0,1,0,1], [1,0,1,1|...], [1,0,2|...], [1,1|...], [1|...], [...]|...] 3&> length(v(2)). 35 4&>

#include & struct list { int val; struct list * pre; }; void print(struct list * n,struct list * d,int z){ int i; if (n==NULL){ for(;z&>0;z--) printf("0 "); while(d!=NULL){ printf("%d ",d-&>val); d=d-&>pre; } printf(" "); return; }


	struct list d1;

	d1.val=n-&>val;

	d1.pre=d;

	print(n-&>pre,d1,z);

	if (z&>0) {

		struct list d2;

		d2.val=0;

		d2.pre=d;

		print(n,d2,z-1);

	}

}
void loop(struct list * n,int sum,int lv,int m,int z){

	if (sum==0) {

		if (z&>=0) print(n,NULL,z);

		return;

	}

	if (lv&>m) return;

	int i=0;

	struct list nn[sum];

	for(;i&
$ ./t

0 0 1 1 1

0 1 0 1 1

1 0 0 1 1

0 1 1 0 1

1 0 1 0 1

1 1 0 0 1

0 1 1 1 0

1 0 1 1 0

1 1 0 1 0

1 1 1 0 0

0 0 0 1 2

0 0 1 0 2

0 1 0 0 2

1 0 0 0 2

0 0 1 2 0

0 1 0 2 0

1 0 0 2 0

0 1 2 0 0

1 0 2 0 0

1 2 0 0 0

0 0 0 2 1

0 0 2 0 1

0 2 0 0 1

2 0 0 0 1

0 0 2 1 0

0 2 0 1 0

2 0 0 1 0

0 2 1 0 0

2 0 1 0 0

2 1 0 0 0

0 0 0 0 3

0 0 0 3 0

0 0 3 0 0

0 3 0 0 0

3 0 0 0 0


首先,這顯然是c程序
然後補一下思路.
首先求出和為n總長度小於等於m的所有自然數組合,然後如果長度小於m,補插0.

用所謂的隔板法(插空法)
允許若干個人（或位置）為空的問題例1將20個大小形狀完全相同的小球放入3個不同的盒子，允許有盒子為空，但球必須放完，有多少種不同的方法？
分析：本題中的小球大小形狀完全相同，故這些小球沒有區別，問題等價於將小球分成三組，允許有若干組無元素，用隔板法.
解析：將20個小球分成三組需要兩塊隔板，因為允許有盒子為空，不符合隔板法的原理，那就人為的再加上3個小球，保證每個盒子都至少分到一個小球，那就符合隔板法的要求了（分完後，再在每組中各去掉一個小球，即滿足了題設的要求）。然後就變成待分小球總數為23個，球中間有22個空檔，需要在這22個空檔里加入2個隔板來分隔為3份，共有C（22，2）=231種不同的方法.
點評：對n件相同物品（或名額）分給m個人（或位置），允許若干個人（或位置）為空的問題,可以看成將這n件物品分成m組，允許若干組為空的問題.將n件物品分成m組，需要m-1塊隔板，將這n件物品和m-1塊隔板排成一排，佔n+m-1位置，從這n+m-1個位置中選m-1個位置放隔板，因隔板無差別，故隔板之間無序，是組合問題，故隔板有Cn+m-1 m-1種不同的方法，再將物品放入其餘位置，因物品相同無差別，故物品之間無順序，是組合問題，只有1种放法，根據分步計數原理，共有Cn+m-1 m-1×1=Cn+m-1 m-1種排法
所以直接算最後的一個公式出結果就好了
隔板法_百度百科

Abstract：本文提供Python版本的非遞歸形式的普通做法及瘋狂版的一句話做法。
普通版本運用了隊列的思想。
一句話版本用了大量map／reduce和lambda函數。
非遞歸版本：
#Authored by Peng Zhenghao

#Ordinary non-recursive version

def N_balls_in_M_boxs_NonRecursive(n,m):

    result=[[x] for x in range(n+1)]
    while len(result[0])&
一句話版：
from functools import reduce

#Authored by Peng Zhenghao

#Lunatic non-recursive version

def N_balls_in_M_boxs_NonRecursive(n,m):

    return list(filter(lambda g: sum(g)==n,reduce(lambda list,y: reduce(lambda p,q: p+q,(map(lambda x: [x+[i] for i in range(n-sum(x)+1)],list))),[[[x] for x in range(n+1)]]+[0]*(m-1))))



自己回去寫了個java版，沒做負數過濾public class NballMbox {

      public void iterator(int balls , int boxes , String s){

		if(balls == 0){

			for(int i = 0 ;i&< boxes ;i++)
				s = s+ 0;
			System.out.println(s.toString());
			return;
		}
		for(int i =balls;i &>=0;i--){

			String s1 = s+i;

			if(boxes == 1){

				System.out.println(s1.toString());

				return;

			}

			else

				this.iterator(balls-i, boxes-1, s1);

		}

	}

       public static void main(String[] args) {

		NballMbox nm = new NballMbox();

		nm.iterator(4, 2, "");

	}

｝


遞歸思想就是：
每個遞歸只管當前盒子里放幾個，至於剩下的小球交給下一個遞歸，直到盒子為1或者小球為0。
盒子為1就把剩下的小球都放進來，小球為0就把剩下的盒子都輸出0
PS: 小球為0的判定是為了減少遞歸次數，如果M&>&>N的話節省的遞歸還是很客觀的。

@Milo Yip 大神給出了一個遞歸的解法。更優雅的辦法是不用遞歸，用循環來做。碰巧昨天我遇到一個類似的問題。
題主的情況屬於Partial Permutation
STL中的next_permutation屬於全排列。建議大家看下next_permutation的實現，非常優雅。
next_permutation的核心思路是維持一個相對順序。
對於輸入序列 1 2 3 4 5 ,觀察next_permutation的輸出序列
1 2 3 4 5
1 2 3 5 4 
1 2 4 3 5
1 2 4 5 3
1 2 5 3 4
1 2 5 4 3
1 3 2 4 5
每一輪新的枚舉開始時，當前枚舉位置後的元素會維持一個順序。(抱歉，我不能表述清楚，再次請大家去cppreference上看實現)
按著這個思路，我們可以實現一個Pnk的部分排列程序。
#include &

#include &

using namespace std; 
vector&&>  vPartialPermutation;

vector& a;

const int n = 5;

const int k = 3;

void print(vector& sample){

	for(auto it : sample){

		cout &<&< it; 
	}
	std::cout &<&< std::endl;
}

void print(vector&&> vPartialPermutation){

	for(auto iter : vPartialPermutation){

		for(auto item : iter)

			std::cout &<&< item;
		std::cout &<&< std::endl;	
	}
}
 
void createData(){
	for(int i=0; i&< n; i++)
		a.push_back(i+1);
}
void swap(int x, int y) {
        int t = a[x];
        a[x] = a[y];
        a[y] = t;
}
void reverseRightOf(int start) {
        int i = start + 1;
        int j = n - 1;
        while (i &< j) {
            swap(i, j);
            ++i;
            --j;
        }
 }
bool computeNext() {
        int i = k - 1;
        int j = k;
        // find smallest j &> k - 1 where a[j] &> a[k - 1]

        while (j &< n  a[i] &>= a[j]) {

            ++j;

        }

        if (j &< n) {
            swap(i, j);
        } 
		else {
            reverseRightOf(i);
            --i; 
            while (i &>= 0  a[i] &>= a[i + 1]) {

                --i;

            }

            if (i &< 0) {
                return false;
            }
            --j;
            while (j &> i  a[i] &>= a[j]) {

                --j;

            }

            swap(i, j);

            reverseRightOf(i);

        }

        return true;

    }
int main(int argc, char **argv){

	createData();

	do{

		vPartialPermutation.push_back(a);

	}while(computeNext());

	std::cout &<&< vPartialPermutation.size() &<&< std::endl;
	return 0;
}

參考資料
std::next_permutation
A Simple, Efficient P(n,k) Algorithm

寫一個c#代碼，並不是什麼新思路，就是最簡單的方法：
1.放一個球到第一個盒子里，然後再放一個球,再放一個球......
2.如果某一個盒子中球滿了（等於n）之後就把該盒子中的球全部拿走，然後放一個球到它的下一個盒子中
3.各個盒子里球的總數等於n時輸出那時的情況
4.第m+1個盒子中有球時退出循環
代碼如下:
using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace n_ball_in_m_box

{

    class Program

    {

        static int kind;

        static void Main(string[] args)

        {

            int[] a = new int[100];

            Console.WriteLine("幾個球?");

            int n = Convert.ToInt32(Console.ReadLine());

            Console.WriteLine("幾個盒子?");

            int m = Convert.ToInt32(Console.ReadLine());

            Console.WriteLine($"{n}個球放入{m}個盒子中有如下情況:");

            while (a[m] == 0)

            {

                int i = 0, sum = 0;

                foreach (int x in a)

                    sum += x;

                if (sum == n)

                {

                    kind++;

                    while (i &< m)
                        Console.Write(a[i++] + " ");
                    Console.WriteLine();
                }
                i = 0;
                a[0]++;
                while (a[i] == n + 1)
                {
                    a[i++] = 0;
                    a[i]++;
                }
            }
            Console.WriteLine($"共有{kind}種情況");
        }
   }
}

3個球，4個盒子時運行情況：

@醬紫君你刪了我和@羅宸 的評論不說還要說別人秀智商。。。
自己看看你發的 wiki 的第一段：
Two sums that differ only in the order of their summands are considered the same partition. (If order matters, the sum becomes a composition.)
題主這裡顯然是認為不同順序是不同的分法的，也就是（上邊的composition的鏈接）：
Composition (combinatorics)
簡單來說就是隔板法，n個球分m組，每組最少0個，那麼就相當於n+m個球分m組，每組最少1個，也就是說n+m-1個空隙插入m-1塊板,所以應該是Binomial[n+m-1,n-1]
你說你算 m=n=50隻要0.08秒（已經被他編輯掉了，但是 @羅宸 肯定看到了），你可先算下有多少種分法：
Binomial[50 + 50 - 1, 50 - 1] = 50445672272782096667406248628
不知道你什麼電腦算這麼多解只要0.08秒啊
--------------------------------------------------------------------
@醬紫君 居然又匿名了啊： 
你的「有編號的解的個數上界是 2^p(n) 」是什麼鬼啊？是不是給的足夠大不錯就行了？就好像我說 n 個數排列的方式的上界是 n^n？
明明可以精確計算的數目用你給一個莫名其妙的上界？上界不好算的明明是「不同順序視為同一個解」的情況，而題主的例子顯然表明他要的是「不同順序視為不同解」的情況，就一個隔板法就解決的事情，還說什麼「這個問題一點都不簡單」，沒錯，對於沒學過高中數學排列組合的人來說這個確實「一點都不簡單」總結下來， @醬紫君 先是自己的答案有問題，別人幫你指正，然後別人的評論全部刪掉，關閉評論，不留痕迹的改掉答案（雖然改到現在為止還改得有問題），然後再進行人身攻擊，到底是誰「無賴」？到底是誰「秀智商」？
而且這樣的回答居然還被大V @Milo Yip 贊同了？匪夷所思23333

模型更特殊化一點，n1個球，n2個盒子，且給定每個盒子的最大裝球數記為序列m. 調用MATLAB程序的函數fill_box如下，[A,B]=fill_box(10,3,[3 4 5])得到的A、B即是方案數以及對應方案。

……看了一圈，沒人用Heap』s algorithm么？

lua版本

function p(d,t,n,m)

	if m == 1 then

		t[d]=n

		return print(table.concat(t,","))

	end

	for i=0,n,1 do

		t[d]=i

		p(d+1,t,n-i,m-1)

	end

end

p(1,{},2,4)


0,0,0,2

0,0,1,1

0,0,2,0

0,1,0,1

0,1,1,0

0,2,0,0

1,0,0,1

1,0,1,0

1,1,0,0

2,0,0,0



  推薦閱讀：


※為什麼電腦正在運行的文件無法刪除？
※C++中如何把一個變數的值作為另一個變數的名？
※如果程序語言的賦值變為左值賦予右值會更好嗎？
※想從事遊戲製作/設計行業，需要學哪些編程語言？
※C 語言程序變數作用域的實現機制是什麼？
TAG:演算法 | 編程 | MATLAB | C編程語言 | 程序 |