Place n indistinguishable items into k distinguishable boxes

[Michael Robertson]

Hi,

I need a generator which produces all ways to place n indistinguishab le
items into k distinguishable boxes.

For n=4, k=3, there are (4+3-1)!/(3-1)!/4! = 15 ways.

(0,0,4)
(0,4,0)
(4,0,0)

(0,2,2)
(2,0,2)
(2,2,0)

(0,1,3)
(0,3,1)
(3,0,1)
(3,1,0)

(1,1,2)
(1,2,1)
(2,1,1)

The generator needs to be fast and efficient.

Thanks.

[Roy Smith]

Re: Place n indistinguishab le items into k distinguishable boxes

In article <fq56vu$aue$1@s keeter.ucdavis. edu>,
Michael Robertson <mcrobertson@ho tmail.comwrote:

Hi,
>
I need a generator which produces all ways to place n indistinguishab le
items into k distinguishable boxes.
>
For n=4, k=3, there are (4+3-1)!/(3-1)!/4! = 15 ways.
>
(0,0,4)
(0,4,0)
(4,0,0)
>
(0,2,2)
(2,0,2)
(2,2,0)
>
(0,1,3)
(0,3,1)
(3,0,1)
(3,1,0)
>
(1,1,2)
(1,2,1)
(2,1,1)
>
The generator needs to be fast and efficient.
>
Thanks.

What course is this homework problem for?

[Michael Robertson]

Re: Place n indistinguishab le items into k distinguishable boxes

Michael Robertson wrote the following on 02/27/2008 06:40 PM:

I need a generator which produces all ways to place n indistinguishab le
items into k distinguishable boxes.

I found:

http://portal.acm.org/citation.cfm?doid=363347.363390

Do anyone know if there are better algorithms than this?

[castironpi@gmail.com]

Re: Place n indistinguishab le items into k distinguishable boxes

On Feb 27, 9:31 pm, Michael Robertson <mcrobert...@ho tmail.comwrote:

Michael Robertson wrote the following on 02/27/2008 06:40 PM:
>

I need a generator which produces all ways to place n indistinguishab le
items into k distinguishable boxes.

>
I found:
>

http://portal.acm.org/citation.cfm?doid=363347.363390

>
Do anyone know if there are better algorithms than this?

Or free?

[castironpi@gmail.com]

Re: Place n indistinguishab le items into k distinguishable boxes

On Feb 27, 8:40 pm, Michael Robertson <mcrobert...@ho tmail.comwrote:

Hi,
>
I need a generator which produces all ways to place n indistinguishab le
items into k distinguishable boxes.
>
For n=4, k=3, there are (4+3-1)!/(3-1)!/4! = 15 ways.
>
(0,0,4)
(0,4,0)
(4,0,0)
>
(0,2,2)
(2,0,2)
(2,2,0)
>
(0,1,3)
(0,3,1)
(3,0,1)
(3,1,0)
>
(1,1,2)
(1,2,1)
(2,1,1)
>
The generator needs to be fast and efficient.
>
Thanks.

Note that the boxes are indistinguishab le, and as such, ( 1, 0, 3 ) ==
( 3, 0, 1 ), but != ( 3, 1, 0 ). How so?

[castironpi@gmail.com]

Re: Place n indistinguishab le items into k distinguishable boxes

On Feb 27, 10:12 pm, castiro...@gmai l.com wrote:

On Feb 27, 8:40 pm, Michael Robertson <mcrobert...@ho tmail.comwrote:
>
>
>
>
>

Hi,

>

I need a generator which produces all ways to place n indistinguishab le
items into k distinguishable boxes.

>

For n=4, k=3, there are (4+3-1)!/(3-1)!/4! = 15 ways.

>

(0,0,4)
(0,4,0)
(4,0,0)

>

(0,2,2)
(2,0,2)
(2,2,0)

>

(0,1,3)
(0,3,1)
(3,0,1)
(3,1,0)

>

(1,1,2)
(1,2,1)
(2,1,1)

>

The generator needs to be fast and efficient.

>

Thanks.

>
Note that the boxes are indistinguishab le, and as such, ( 1, 0, 3 ) ==
( 3, 0, 1 ), but != ( 3, 1, 0 ).  How so?- Hide quoted text -
>
- Show quoted text -

Ah, correction, retracted. -disting-uishable boxes. Copy, but then,
where's ( 1, 0, 3 )?

[Michael Robertson]

Re: Place n indistinguishab le items into k distinguishable boxes

castironpi@gmai l.com wrote the following on 02/27/2008 08:14 PM:

On Feb 27, 10:12 pm, castiro...@gmai l.com wrote:

>>For n=4, k=3, there are (4+3-1)!/(3-1)!/4! = 15 ways.

>>(0,0,4)
>>(0,4,0)
>>(4,0,0)
>>(0,2,2)
>>(2,0,2)
>>(2,2,0)
>>(0,1,3)
>>(0,3,1)
>>(3,0,1)
>>(3,1,0)
>>(1,1,2)
>>(1,2,1)
>>(2,1,1)

>
Ah, correction, retracted. -disting-uishable boxes. Copy, but then,
where's ( 1, 0, 3 )?

I only listed 13 ways...sorry about that. Missing are:

(1, 0, 3) and (1, 3, 0)

[Mark Dickinson]

Re: Place n indistinguishab le items into k distinguishable boxes

Here's a possible solution. I'm sure others will comment on how to
fix up its inefficiencies (like the potentially slow string
concatenations. ..).



def comb(n, k):
if n == k == 0:
yield ''
else:
if n 0:
for x in comb(n-1, k):
yield ' ' + x
if k 0:
for x in comb(n, k-1):
yield '|' + x

def boxings(n, k):
if k == 0:
if n == 0:
yield []
else:
for s in comb(n, k-1):
yield map(len, (''.join(s)).sp lit('|'))

for b in boxings(4, 3):
print b


Output:

[4, 0, 0]
[3, 1, 0]
[3, 0, 1]
[2, 2, 0]
[2, 1, 1]
[2, 0, 2]
[1, 3, 0]
[1, 2, 1]
[1, 1, 2]
[1, 0, 3]
[0, 4, 0]
[0, 3, 1]
[0, 2, 2]
[0, 1, 3]
[0, 0, 4]

[Mark Dickinson]

Re: Place n indistinguishab le items into k distinguishable boxes

On Feb 27, 11:38 pm, Mark Dickinson <dicki...@gmail .comwrote:

            yield map(len, (''.join(s)).sp lit('|'))

That line should have been just:

yield map(len, s.split('|'))

of course.

Mark

[Mark Dickinson]

Re: Place n indistinguishab le items into k distinguishable boxes

On Feb 28, 5:02 am, Michael Robertson <mcrobert...@ho tmail.comwrote:

Thanks again for your efforts here.  This particular problem didn't
appear in any course I took...certainl y 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)])

You'll need to check out and compile the
latest svn sources to make it work, though.
And it doesn't work when k == 0.

Mark

[Arnaud Delobelle]

Re: Place n indistinguishab le items into k distinguishable boxes

On Feb 28, 2:40 am, Michael Robertson <mcrobert...@ho tmail.comwrote:

Hi,
>
I need a generator which produces all ways to place n indistinguishab le
items into k distinguishable boxes.
>
For n=4, k=3, there are (4+3-1)!/(3-1)!/4! = 15 ways.
>
(0,0,4)

[...]

Here is my little function:

---------------
from itertools import chain
from operator import sub

def boxings(n, k):
"""boxings( n, k) -iterator

Generate all ways to place n indistiguishabl e items into k
distinguishable boxes
"""
seq = [n] * (k-1)
while True:
yield map(sub, chain(seq, [n]), chain([0], seq))
for i, x in enumerate(seq):
if x:
seq[:i+1] = [x-1] * (i+1)
break
else:
return
---------------

It is purely iterative. I think it is not too wasteful but I haven't
tried to optimise it in any way.

In the function, 'seq' iterates over all increasing sequences of
length k-1 over {0,1,..n}.

Example:

>>for b in boxings(4, 3): print b

...
[4, 0, 0]
[3, 1, 0]
[2, 2, 0]
[1, 3, 0]
[0, 4, 0]
[3, 0, 1]
[2, 1, 1]
[1, 2, 1]
[0, 3, 1]
[2, 0, 2]
[1, 1, 2]
[0, 2, 2]
[1, 0, 3]
[0, 1, 3]
[0, 0, 4]

... here is another attempt on the same principle:

---------------
def boxings(n, k):
"""boxings( n, k) -iterator

Generate all ways to place n indistiguishabl e 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

--
Arnaud

[Arnaud Delobelle]

Re: Place n indistinguishab le items into k distinguishable boxes

On Feb 28, 4:44 pm, Arnaud Delobelle <arno...@google mail.comwrote:

... here is another attempt on the same principle:
>
---------------
def boxings(n, k):
    """boxings( n, k) -iterator
>
    Generate all ways to place n indistiguishabl e 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]

Re: Place n indistinguishab le items into k distinguishable boxes

On Feb 28, 10:07 am, Mark Dickinson <dicki...@gmail .comwrote:

On Feb 28, 5:02 am, Michael Robertson <mcrobert...@ho tmail.comwrote:
>

Thanks again for your efforts here.  This particular problem didn't
appear in any course I took...certainl y 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.)