0hc.net Menu
Home Overview
About Menu

Boxes and Balls

Problem: Produce all distributions of n balls in m boxes.
Example: m=4 n=2: [2,0,0,0] [1,1,0,0] [0,2,0,0] [1,0,1,0] [0,1,1,0] [0,0,2,0] [1,0,0,1] [0,1,0,1] [0,0,1,1] [0,0,0,2] Solutions:


import System.Environment perm m n = f (m-1) 0 [] where f l s xs | l>0 = [0..n-s] >>= \x-> f (l-1) (s+x) $ x:xs | otherwise = return $ n-s:xs main = getArgs >>= mapM_ print . (\xs-> case xs of [x,y]->perm x y; _->[]) . map read


local List = require "pl.List" function perm(m, n) function f(l, s, xs) if l>0 then for x=0, n-s do f(l-1, s+x, List(xs):put(x)) end else res:append(xs:put(n-s)) end end res=List() f(m-1, 0, List()) return res end if #arg==2 then perm(tonumber(arg[1]), tonumber(arg[2])):foreach(print) end


#include <iostream> #include <list> #include <algorithm> #include <functional> #include <cstdlib> using namespace std; template <typename T> void print(list<T> xs){ cout << "["; if(xs.size()>0){ cout << xs.front(); for_each(++xs.begin(), xs.end(), [](T x){cout << "," << x;});} cout << "]" << endl;} template <typename T> list< list<T> > perm(int m, T n){ list< list<T> > res; function<void(int, T, list<T>)> f = [n, &res, &f](int l, T s, list<T> xs){ if(l>0) for(T x=0; x<=n-s; ++x){ list<T> ys=xs; ys.push_front(x); f(l-1, s+x, ys);} else { xs.push_front(n-s); res.push_back(xs);}}; list<T> a; f(m-1, 0, a); return res;} int main(int argc, char **argv){ if(argc==3) for(auto x:perm(atoi(argv[1]), atoi(argv[2]))) print(x); return 0;} Or without recursion:


import sys def perm(m,n): xs, ys, res, i, k = [0]*n, [], [], 0, 0 while True: ys=[0]*m for x in xs: ys[x]+=1 res.append(ys) k=xs[i]+1 while k>=m: i+=1 if i>=n: return res k=xs[i]+1 for j in xrange(i,-1,-1): xs[j]=k i=0 return res if len(sys.argv)==3: for x in perm(int(sys.argv[1]), int(sys.argv[2])): print(x)


local ffi = require "ffi" function perm(m,n) local xs, ys, res, i, k, amt = ffi.new("int["..n.."]"), nil, {}, 0, 0, ffi.typeof("int["..m.."]") while true do ys=amt() for j=0,n-1 do ys[xs[j]]=ys[xs[j]]+1 end table.insert(res, ys) k=xs[i]+1 while k>=m do i=i+1 if i>=n then return res end k=xs[i]+1 end for j=i,0,-1 do xs[j]=k end i=0 end end if #arg==2 then local m = tonumber(arg[1]) for _,x in pairs(perm(m, tonumber(arg[2]))) do for i=0,m-1 do io.write(x[i]," ") end print() end end And some optimization:


#include <stdio.h> #include <stdlib.h> static int *a; int f(int s, int k){ if(!s) return 0; else if(a[s]){ --a[s]; ++a[s-1]; return 1;} else{ int p=s-1; while(p && !a[p]) --p; if(p){ ++a[p-1]; a[s]=a[p]-1; a[p]=0; return 1;} else return 0;}} int main(int argc, char **argv){ if(argc==3){ int m=atoi(argv[1]), n=atoi(argv[2]); //int i; a=calloc(sizeof(int),m--); a[m]=n; do{ /*for(i=0; i<m+1; ++i) printf("%d ",a[i]); puts("");*/}while(f(m,n)); free(a);} return 0;}
0hc.net    © 2001-2014 Harald Wolfsgruber