Re: List partitioning

bim wrote:
pineapple.link@xxxxxxxxx wrote :
Sounds like a homework assignment.

It's not, I left studies years ago...
I just need a balancing algorithm for a program of mine, and I wonder if it wouldn't be easier to do it in Prolog.

Then maybe a Python version would serve.

NB :

- Python 2.6 (itertools.combinations, product)
- lightly tested

HTH, BB

from itertools import tee,combinations,imap,product

def partEvenly(aSet,nCombis) :
if aSet :
item=min(aSet)
while 1 :
smallSet = nCombis.next()
if item<min(smallSet) : break
if smallSet<=aSet :
furtherCombis, nCombis = tee(nCombis)
for further in partEvenly(aSet-smallSet,
furtherCombis) :
further.append(smallSet)
yield further
else :
yield []

def combi(u,n) :
return imap(set,combinations(u,n))

def partition(n,m) :
aSet = set(range(n))
j,k = divmod(n,m)
if k :
return (x+y
for jU in combi(aSet,j*(m-k))
for x,y in product(*(partEvenly(U,combi(U,J))
for U,J in [(jU,j),(aSet-set(jU),j+1)]))
)
else :
return partEvenly(aSet,combi(range(n),j))

>>> for res in partition(5,2) :
print sorted(sorted(sset) for sset in res)


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

Relevant Pages

  • Re: Just for fun: Countdown numbers game solver
    ... Ops is vanilla, cleverops only returns canonical expressions as defined in Dan's email. ... def getop: return 'n' if isinstance ... yield x + y, ... "Return all ways of reaching target with nums" ...
    (comp.lang.python)
  • Re: Nested generator caveat
    ... Here's what's actually going on in your generator. ... def gen1: ... yield i, gen1 ... the for loop in gen0 is suspended each iteration while we do some ...
    (comp.lang.python)
  • Re: can Python be useful as functional?
    ... def sieve: ... I also know that Python got some useful tool such as map, filter, ... These should be almost the same: listprimes actually lists prime ...
    (comp.lang.python)
  • Re: Ordered Sets
    ... to store the key itself in the Node or the list. ... script that stores only prev and next. ... def discard: ... yield start ...
    (comp.lang.python)
  • Re: Newbie Question: Blocks and Parameters
    ... def my_method ... assigned to it when executing the upto method which invokes a yield? ... value from 1 to count in each iteration, ...
    (comp.lang.ruby)