Hi,
I need a generator which produces all ways to place n indistinguishable
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. 12 1995
In article <fq**********@skeeter.ucdavis.edu>,
Michael Robertson <mc*********@hotmail.comwrote:
Hi,
I need a generator which produces all ways to place n indistinguishable
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 wrote the following on 02/27/2008 06:40 PM:
I need a generator which produces all ways to place n indistinguishable
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?
On Feb 27, 9:31*pm, Michael Robertson <mcrobert...@hotmail.comwrote:
Michael Robertson wrote the following on 02/27/2008 06:40 PM:
I need a generator which produces all ways to place n indistinguishable
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?
On Feb 27, 8:40*pm, Michael Robertson <mcrobert...@hotmail.comwrote:
Hi,
I need a generator which produces all ways to place n indistinguishable
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 indistinguishable, and as such, ( 1, 0, 3 ) ==
( 3, 0, 1 ), but != ( 3, 1, 0 ). How so?
On Feb 27, 10:12*pm, castiro...@gmail.com wrote:
On Feb 27, 8:40*pm, Michael Robertson <mcrobert...@hotmail.comwrote:
Hi,
I need a generator which produces all ways to place n indistinguishable
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 indistinguishable, 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 )? ca********@gmail.com wrote the following on 02/27/2008 08:14 PM:
On Feb 27, 10:12 pm, castiro...@gmail.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)
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)).split('|'))
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]
On Feb 27, 11:38*pm, Mark Dickinson <dicki...@gmail.comwrote:
* * * * * * yield map(len, (''.join(s)).split('|'))
That line should have been just:
yield map(len, s.split('|'))
of course.
Mark
On Feb 28, 5:02*am, Michael Robertson <mcrobert...@hotmail.comwrote:
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)])
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
On Feb 28, 2:40*am, Michael Robertson <mcrobert...@hotmail.comwrote:
Hi,
I need a generator which produces all ways to place n indistinguishable
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 indistiguishable 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 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
--
Arnaud
On Feb 28, 4:44*pm, Arnaud Delobelle <arno...@googlemail.comwrote:
... 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
On Feb 28, 10:07*am, Mark Dickinson <dicki...@gmail.comwrote:
On Feb 28, 5:02*am, Michael Robertson <mcrobert...@hotmail.comwrote:
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.) This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: james.dixon |
last post by:
Hi
I was wondering if anyone else had had this problem before (can't find
anything on the web about it).
I have three select elements (list boxes - from here on I'll refer to
them as 'the...
|
by: Colleyville Alan |
last post by:
I am trying to use a list box to allow users to select items, the results
are queried based on the selection and written to a spreadsheet. If the
item already exists on their current spreadsheet,...
|
by: Kay |
last post by:
Hello,
I have two list boxes on my form, one initially displays blank, and through
javascript it is possible to move items from one box to another, this works
fine, I followed an article titled...
|
by: Kay |
last post by:
Hello,
I have two list boxes on my form, one initially displays with items and the
other displays blank, by clicking a button, it is possible to move items
from one box to another and vice a...
|
by: kent |
last post by:
Hi All,
On my form, I have 2 listboxes that get populated with the correct items.
I have 4 buttons between the 2 boxes. The first 2 buttons are used to move
the selected item
back and forth...
|
by: TS |
last post by:
This is getting very frustrating. I placed the same question before twice and
got no response. Hopefully I'll get one this time.
What I want to do is to restrict the items in one of the cbo boxes...
|
by: karachiite1 |
last post by:
How can I remove an Item and all its subitems on double_click in a
ListViewControl such a way that I will add the same removed items to three text boxes in a text boxes on the same form. My listview...
|
by: prn |
last post by:
Hi folks,
I've got another (inherited) puzzle that I don't understand.
A report that I need to modify contains a subreport that lists a variable number of items in its detail section and then...
|
by: DolphinDB |
last post by:
Tired of spending countless mintues downsampling your data? Look no further!
In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
|
by: isladogs |
last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM).
In this month's session, we are pleased to welcome back...
|
by: isladogs |
last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM).
In this month's session, we are pleased to welcome back...
|
by: Vimpel783 |
last post by:
Hello!
Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
|
by: jfyes |
last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
|
by: ArrayDB |
last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
|
by: CloudSolutions |
last post by:
Introduction:
For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
|
by: Shællîpôpï 09 |
last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
|
by: Faith0G |
last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
| |