排列組合 in Python

還記得高中時的排列組合問題嗎？ 比方說我有 d 個相同的球要放到 N 個位置， 位置沒有編號，總共有幾種放法呢？

這是一個 重複組合 的問題，答案是共有 (N+d-1)!/((N-1)! d!) 種方法。 最近在寫一個程式，就遇到重複組合的問題， 可是不只要把有幾種放法算出來而已，還要列出所有可能的放法。 比如 N=4, d=3，則所有可能的放法如下：

0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
0 0 1 2
0 0 2 1
0 1 0 2
0 1 2 0
0 2 0 1
0 2 1 0
1 0 0 2
1 0 2 0
1 2 0 0
2 0 0 1
2 0 1 0
2 1 0 0
0 0 0 3
0 0 3 0
0 3 0 0
3 0 0 0

因為 N 與 d 是任給的，所以一旦 N 跟 d 很大的時候， 就不可能用手算的方式，把所有的放法列出來， 必須要用有系統的方式來產生這些放法。 最後我用 Python 輕鬆地解決了這個問題：

• 首先給定 d 的話，要把所有 d 的正整數分解都找出來，比如 d=3 的話， 3 可以寫成 3, 2+1, 1+1+1，然後再依 N 是多少去補零，比如 N=4 的話， 我們就有

  3 0 0 0
  2 1 0 0
  1 1 1 0
  

  這 3 種放法。我在 ASPN 找到了 正整數分解 的方法。
• 接下來對每種放法產生所有的排列，比如 3 0 0 0 的所有排列為

  3 0 0 0
  0 3 0 0
  0 0 3 0
  0 0 0 3
  

  我也在 ASPN 找到了 產生所有排列 的方法。
• 最後還剩下一個問題，給定 3 0 0 0，其所有的排列共有 4!=24 種， 但相同的排列要扣掉，所以最後應該只有 4!/3! = 4 種， 排除相同物 的演算法在 ASPN 也可以找到。

把這三個演算法結合就解決了我的問題， 程式碼在這裡。 觀察這三個演算法，我發現三個演算法的程式碼的很短、很巧妙， 正整數分解 跟 產生所有排列 有用到 generator， 而 排除相同物 居然是利用 Python 內建型態 dictionary 的子方法 keys()， Python 真是一個優雅的程式語言。