Say I have a list L. How can I get an iterator over all partitions of K groups?
Example: L = [ 2,3,5,7,11, 13], K = 3
List of all possible partitions of 3 groups:
[ [ 2 ], [ 3, 5], [ 7,11,13] ]
[ [ 2,3,5 ], [ 7, 11], [ 13] ]
[ [ 3, 11 ], [ 5, 7], [ 2, 13] ]
[ [ 3 ], [ 11 ], [ 5, 7, 2, 13] ]
etc...
=== UPDATE ===
I was working on a solution which seems to be working, so I will just copy paste it
# -*- coding: utf-8 -*-
import itertools
# return ( list1 - list0 )
def l1_sub_l0( l1, l0 ) :
"""Substract two lists"""
#
copy_l1 = list( l1 )
copy_l0 = list( l0 )
#
for xx in l0 :
#
if copy_l1.count( xx ) > 0 :
#
copy_l1.remove( xx )
copy_l0.remove( xx )
#
return [ copy_l1, copy_l0 ]
#
def gen_group_len( n, k ) :
"""Generate all possible group sizes"""
# avoid doubles
stop_list = []
#
for t in itertools.combinations_with_replacement( xrange( 1, n - 1 ), k - 1 ) :
#
last_n = n - sum( t )
# valid group size
if last_n >= 1 :
res = tuple( sorted( t + ( last_n, ) ) )
#
if res not in stop_list :
yield res
stop_list.append( res )
# group_len = (1, 1, 3)
def gen( group_len, my_list ) :
"""Generate all possible partitions of all possible group sizes"""
#
if len( group_len ) == 1 :
yield ( tuple( my_list ), )
#
else :
# need for a stop list if 2 groups of same size
stop_list = []
#
for t in itertools.combinations( my_list, group_len[ 0 ] ) :
#
reduced_list = l1_sub_l0( my_list, t )[ 0 ]
#
for t2 in gen( group_len[ 1: ], reduced_list ) :
#
tmp = set( ( t, t2[ 0 ] ) )
#
if tmp not in stop_list :
yield ( t, ) + t2
# avoid doing same thing twice
if group_len[ 1 ] == group_len[ 0 ] :
stop_list.append( tmp )
#
my_list = [ 3,5,7,11,13 ]
n = len( my_list )
k = 3
#
group_len_list = list( gen_group_len( n, k ) )
print "for %i elements, %i configurations of group sizes" % ( n, len( group_len_list ) )
print group_len_list
#
for group_len in group_len_list :
#
print "group sizes", group_len
#
for x in gen( group_len, my_list ) :
print x
#
print "==="
Output:
for 5 elements, 2 configurations of group sizes
[(1, 1, 3), (1, 2, 2)]
group sizes (1, 1, 3)
((3,), (5,), (7, 11, 13))
((3,), (7,), (5, 11, 13))
((3,), (11,), (5, 7, 13))
((3,), (13,), (5, 7, 11))
((5,), (7,), (3, 11, 13))
((5,), (11,), (3, 7, 13))
((5,), (13,), (3, 7, 11))
((7,), (11,), (3, 5, 13))
((7,), (13,), (3, 5, 11))
((11,), (13,), (3, 5, 7))
===
group sizes (1, 2, 2)
((3,), (5, 7), (11, 13))
((3,), (5, 11), (7, 13))
((3,), (5, 13), (7, 11))
((5,), (3, 7), (11, 13))
((5,), (3, 11), (7, 13))
((5,), (3, 13), (7, 11))
((7,), (3, 5), (11, 13))
((7,), (3, 11), (5, 13))
((7,), (3, 13), (5, 11))
((11,), (3, 5), (7, 13))
((11,), (3, 7), (5, 13))
((11,), (3, 13), (5, 7))
((13,), (3, 5), (7, 11))
((13,), (3, 7), (5, 11))
((13,), (3, 11), (5, 7))
===
This works, although it is probably super inneficient (I sort them all to avoid double-counting):
def clusters(l, K):
if l:
prev = None
for t in clusters(l[1:], K):
tup = sorted(t)
if tup != prev:
prev = tup
for i in xrange(K):
yield tup[:i] + [[l[0]] + tup[i],] + tup[i+1:]
else:
yield [[] for _ in xrange(K)]
It also returns empty clusters, so you would probably want to wrap this in order to get only the non-empty ones:
def neclusters(l, K):
for c in clusters(l, K):
if all(x for x in c): yield c
Counting just to check:
def kamongn(n, k):
res = 1
for x in xrange(n-k, n):
res *= x + 1
for x in xrange(k):
res /= x + 1
return res
def Stirling(n, k):
res = 0
for j in xrange(k + 1):
res += (-1)**(k-j) * kamongn(k, j) * j ** n
for x in xrange(k):
res /= x + 1
return res
>>> sum(1 for _ in neclusters([2,3,5,7,11,13], K=3)) == Stirling(len([2,3,5,7,11,13]), k=3)
True
It works !
The output:
>>> clust = neclusters([2,3,5,7,11,13], K=3)
>>> [clust.next() for _ in xrange(5)]
[[[2, 3, 5, 7], [11], [13]], [[3, 5, 7], [2, 11], [13]], [[3, 5, 7], [11], [2, 13]], [[2, 3, 11], [5, 7], [13]], [[3, 11], [2, 5, 7], [13]]]
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With