在OCaml中的m個桶中的n個球的列表

Question

我試圖找到所有的排列，其中n個球分散到m個桶中。我正在通過遞歸來處理它，但是我對我應該緩存的內容感到困惑，因爲n可能會減少任何數字......（我正在遞歸m-1）有關如何使用函數式語言方法實現這一點的任何想法？

在C++中有一個解決方案，但我不瞭解C++。 List of combinations of N balls in M boxes in C++

Answer 1

沒有必要產生多餘的結果。下面的代碼是有點難看，但它的工作：你想要的形式p::u的所有列表與generate (n - p) (m - 1)u

let (<|>) s e = 
    let rec aux s e res = 
    if e - s < 0 then res 
    else aux (s + 1) e (s :: res) in 
    List.rev (aux s e []) 

let rec generate n m = 
    let prepend_x l x = List.map (fun u -> x::u) l in 
    if m = 1 then [[n]] 
    else 
    let l = List.map (fun p -> prepend_x (generate (n - p) (m - 1)) p) (0 <|> n) in 
    List.concat l 

的想法很簡單，用p範圍超過0..n

Answer 2

let flatten_tail l = 
    let rec flat acc = function 
    | [] -> List.rev acc 
    | hd::tl -> flat (List.rev_append hd acc) tl 
    in 
    flat [] l 

let concat_map_tail f l = 
    List.rev_map f l |> List.rev |> flatten_tail 

let rm_dup l = 
    if List.length l = 0 then l 
    else 
    let sl = List.sort compare l in 
    List.fold_left (
     fun (acc, e) x -> if x <> e then x::acc, x else acc,e 
    ) ([List.hd sl], List.hd sl) (List.tl sl) |> fst |> List.rev 

---

(* algorithm starts from here *) 
let buckets m = 
    let rec generate acc m = 
    if m = 0 then acc 
    else generate (0::acc) (m-1) 
    in 
    generate [] m 

let throw_1_ball bs = 
    let rec throw acc before = function 
    | [] -> acc 
    | b::tl -> 
     let new_before = b::before in 
     let new_acc = (List.rev_append before ((b+1)::tl))::acc in 
     throw new_acc new_before tl 
    in 
    throw [] [] bs 

let throw_n_ball n m = 
    let bs = buckets m in 
    let rec throw i acc = 
    if i = 0 then acc 
    else throw (i-1) (concat_map_tail throw_1_ball acc |> rm_dup) 
    in 
    throw n [bs] 

---

以上是正確的代碼，這是可怕的，因爲我增加了一些實用功能，使事情尾遞歸越好。但這個想法很簡單。

這裏的算法：

1. 比方說，我們有3個桶，它最初是[0; 0; 0。
2. 如果我們向3個桶投擲1個球，我們有3個例子，其中每個 是桶的快照，即[[1; 0; 0]; [0; 1; 0]; [0; 0; 1]]。
3. 然後，如果我們有更多的球，對於每種情況的上方，我們將3例， 因此所得到的情況下，列表中有9案件
4. 然後，如果我們有更多的球，.....

通過這種方式，我們將生成3^n個案，其中許多可能是多​​餘的。

所以當生成每個案例列表時，我們只是刪除案例列表中的所有重複。

---

utop # throw_n_ball 3 2;; 
- : int list list = [[0; 3]; [1; 2]; [2; 1]; [3; 0]] 

utop # throw_n_ball 5 3;; 
- : int list list = [[0; 0; 5]; [0; 1; 4]; [0; 2; 3]; [0; 3; 2]; [0; 4; 1]; [0; 5; 0]; [1; 0; 4];[1; 1; 3]; [1; 2; 2]; [1; 3; 1]; [1; 4; 0]; [2; 0; 3]; [2; 1; 2]; [2; 2; 1]; [2; 3; 0]; [3; 0; 2]; [3; 1; 1]; [3; 2; 0]; [4; 0; 1]; [4; 1; 0]; [5; 0; 0]]