Velocity Reviews > Place n indistinguishable items into k distinguishable boxes

# Place n indistinguishable items into k distinguishable boxes

Arnaud Delobelle
Guest
Posts: n/a

 02-28-2008
On Feb 28, 4:44*pm, Arnaud Delobelle <(E-Mail Removed)> wrote:

> ... here is another attempt on the same principle:
>
> ---------------
> def boxings(n, k):
> * * """boxings(n, k) -> iterator
>
> * * Generate all ways to place n indistiguishable items into k
> * * distinguishable boxes
> * * """
> * * seq = [n]*k + [0]
> * * while True:
> * * * * yield tuple(seq[i] - seq[i+1] for i in xrange(k))
> * * * * i = seq.index(0) - 1
> * * * * if i >= 1:
> * * * * * * seq[i:k] = [seq[i] - 1] * (k - i)
> * * * * else:
> * * * * * * return

Actually this is better as it handles k=0 correctly:

def boxings(n, k):
seq, i = [n]*k + [0], k
while i:
yield tuple(seq[i] - seq[i+1] for i in xrange(k))
i = seq.index(0) - 1
seq[i:k] = [seq[i] - 1] * (k-i)

--
Arnaud

castironpi@gmail.com
Guest
Posts: n/a

 02-28-2008
On Feb 28, 10:07*am, Mark Dickinson <(E-Mail Removed)> wrote:
> On Feb 28, 5:02*am, Michael Robertson <(E-Mail Removed)> wrote:
>
> > Thanks again for your efforts here. *This particular problem didn't
> > appear in any course I took...certainly similar problems did.

>
> And here's the obligatory not-very-obfuscated one-liner:
>
> from itertools import combinations as c; boxings=lambda n,k[s[i
> +1]+~s[i] for i in range(k)] for s in [[-1]+list(t)+[n-~k] for t in
> c(range(n-~k),k-1)])

This calls for an obfuscation metric, several books, and two personal
references. What is ~k doing in there twice?

(Aside: throw in an obligatority one too. Sigh.)