List of n balls in m buckets in OCaml

Question

I am trying to find all permutations where n balls are spread into m buckets. I am approaching it through recursion but I am confused on what I should recurse n on since n could decrease by any numbers... (I am recursing on m-1) Any thoughts on how to do this with a functional language approach?

There's a solution in C++ but I don't understand C++. List of combinations of N balls in M boxes in C++

2 question: `1. do you care the order of the balls within one busket?`; `2. are those buckets numbered? i.e., do you care the order of the buckets?` — Jackson Tale, Feb 08 '14 at 22:22
I don't care the order of the balls within one bucket. And yes, I care the order of the buckets. — kikilala, Feb 08 '14 at 22:44
An example of the function ball 1 2 will return [[0;1];[1;0]], ball 5 1 will return [[5]] — kikilala, Feb 08 '14 at 22:46
I answered your question, if you think it is helpful, please mark my answer correct — Jackson Tale, Feb 08 '14 at 23:49

score 2 · Accepted Answer · answered Feb 09 '14 at 19:02

2

There is no need to generate redundant results. The following code is a bit ugly, but it does the job :

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

The idea is simply that you want all lists of the form p::u with u in generate (n - p) (m - 1), with p ranging over 0..n

answered Feb 09 '14 at 19:02

Jbeuh

395
1
6

Yeah, i thought so too, just in this way it is hard to make it tail-recursive – Jackson Tale Feb 10 '14 at 11:22
Tail recursion wouldn't really bring any benefit here (the call tree is very wide, it cannot get deep). – Jbeuh Feb 10 '14 at 18:11
If you try `generate 2000 1000`, then you will know – Jackson Tale Feb 10 '14 at 22:43
Well, there are approximately $10^{827}$ elements in the list I would be trying to generate, so I'm not sure there is a point :). But if you change the code so that it computes the number of solutions and not the actual solutions (using `BigInt`), then you can handle larger values of `n` and `m`. The code I wrote will fail then, not because it's not tail recursivee but because it's not memoized. – Jbeuh Feb 11 '14 at 06:33
What does this mean?? <|>. do you guys mind putting a comment on how you would write it without using <|>, <|. I tried updating my ocaml version but it did not work out. – kikilala Feb 11 '14 at 22:05
`<|> start end` is a function wich returns the list of integers from `start` to `end` (inclusive). It's not a standard OCaml operator : it's defined (as an infix operator) just above the main function. – Jbeuh Feb 12 '14 at 05:55

Jackson Tale · Answer 2 · 2014-02-09T01:33:22.003

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]

Above is the correct code, it is scary because I added several utility functions and make things as tail-recursive as possible. But the idea is very simple.

Here is the algorithm:

Let's say we have 3 buckets, initially it is [0;0;0].
If we throw 1 ball into the 3 buckets, we have 3 cases each of which is a snapshot of the buckets, i.e., [[1;0;0];[0;1;0];[0;0;1]].
Then if we have 1 more ball, for each case above, we will 3 cases, so the resulting case list have 9 cases
Then if we have 1 more ball, .....

In this way, we will generate 3^n cases and many of them may be redundant.

So when generated each case list, we just remove all duplicates in the case list.

 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]]

I just put in into the ocaml interpreter but it keeps complaining about line 6 has type int but an expression was expected of type 'a list list. Do you have any ideas why that is so? — kikilala, Feb 09 '14 at 00:58
@kikilala I don't have any problem compiling it. maybe the code was too long and wide. I reformatted it. Please make sure copy paste all codes — Jackson Tale, Feb 09 '14 at 01:33
compiling in .ml file. My program is not recognizing |>.. What does |> do? — kikilala, Feb 09 '14 at 06:04
@kikilala oh I think you should upgrade to the newest ocaml version 4.00.1. `|>` means put the left hand side part to right hand side part as parameter. So without it you have to write `f x`, with it you can write `x |> f`. New feature of 4.00.1. — Jackson Tale, Feb 09 '14 at 13:52

List of n balls in m buckets in OCaml

2 Answers2