Combinatorics

[Michael Robertson]

Where is the python equivalent of:

http://search.cpan.org/~fxn/Algorithm-Combinatorics-0.16/Combinatorics.pm

combinations (with and without repetition)
variations (with and without repetition)
permutations
partitions
derangements
etc

I'm guessing sage has this, but shouldn't something like this be part of 
the standard library (perhaps in C)?  I'd understand if derangements and 
partitions were excluded, but the standard combinatorics (replacement 
on/off, repetition on/off) would be quite nice.  It would also be 
helpful to have a general cartesian product function which combined 
elements from an arbitrary number of lists.

It seems that questions for these algorithms occur too frequently.

Am I wishing on a star?

-- 
http://mail.python.org/mailman/listinfo/python-list

Place n indistinguishable items into k distinguishable boxes

[Michael Robertson]

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.
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Place n indistinguishable items into k distinguishable boxes

[Michael Robertson]

Michael Robertson wrote the following on 02/27/2008 06:40 PM:
> Hi,
> 
> I need a generator which produces all ways to place n indistinguishable 
> items into k distinguishable boxes.
> 

My first thought was to generate all integer partitions of n, and then 
generate all permutations on k elements.  So:

4 = 4
   = 3 + 1
   = 2 + 2
   = 2 + 1 + 1

Then for 4,  generate all permutations of x=(4,0,0,..),  |x|=k
Then for 3,1 generate all permutations of x=(3,1,0,..),  |x|=k
Then for 2,2 generate all permutations of x=(2,2,0...),  |x|=k
...

In addition to having to generate permutations for each integer 
partition, I'd have to ignore all integer partitions which had more than 
k parts...this seemed like a bad way to go (bad as in horribly inefficient).

Better ideas are appreciated.
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Place n indistinguishable items into k distinguishable boxes

[Michael Robertson]

Roy Smith wrote the following on 02/27/2008 06:56 PM:
> What course is this homework problem for?

None.  I assume you have an answer to this *trivial* problem...

It's actually a very general question relating to a very specific 
problem I am working on.  Normally, I do not reply to such snide 
remarks, but I'd like to note that this post would never have been made 
if there *were* a Python package which provided these common 
combinatorial methods.
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Place n indistinguishable items into k distinguishable boxes

[Michael Robertson]

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?
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Place n indistinguishable items into k distinguishable boxes

[Michael Robertson]

[EMAIL PROTECTED] wrote the following on 02/27/2008 08:14 PM:
> On Feb 27, 10:12 pm, [EMAIL PROTECTED] 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)
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Place n indistinguishable items into k distinguishable boxes

[Michael Robertson]

[EMAIL PROTECTED] wrote the following on 02/27/2008 08:46 PM:
> Just sort the list in text-ascending order, and it's pretty clear.

Indeed.  After trying Mark's solution, I saw that it sorted in a very 
nice manner.
-- 
http://mail.python.org/mailman/listinfo/python-list

Re: Place n indistinguishable items into k distinguishable boxes

[Michael Robertson]

[EMAIL PROTECTED] wrote the following on 02/28/2008 12:36 AM:
> On Feb 27, 8:47 pm, Michael Robertson <[EMAIL PROTECTED]> wrote:
> Your only casualty here is all the zeroes in (4,0,0,..).  You don't
> want to swap k_2 and k_3 in (4,0,0).  (Is that what permutation
> means?)

Correct.  Though by 'permutation', I meant 'permutations with 
repetitions'---so the algorithm would have handled that.

> 
>> In addition to having to generate permutations for each integer
>> partition, I'd have to ignore all integer partitions which had more than
>> k parts...this seemed like a bad way to go (bad as in horribly inefficient).
>>
>> Better ideas are appreciated.
> 
> Running time on my recursive was K** 2* N, counting the copy, I
> think.  sum( 1..i )== i( i+ 1 )/ 2, O( i** 2 ).  My iterative was
> slower, K** 3* N, unless you save a K or N in the small length of K
> early on, I think.  Did anyone take this course that can tell me?

Thanks again for your efforts here.  This particular problem didn't 
appear in any course I took...certainly similar problems did.
-- 
http://mail.python.org/mailman/listinfo/python-list

open filename with spaces in path

[Michael Robertson]

I'm having trouble opening a file in linux, whose path has spaces in it.

$ mkdir my\ test
$ echo test > my\ test/test.txt
$ python

>>> open('./my test/test.txt')
Exception
>>> open('./my\\ test/test.txt')
Exception

but yet...

>>> import os
>>> os.chdir('./my test')
>>> open('./test')

works just fine.
--
http://mail.python.org/mailman/listinfo/python-list