Iterator over all partitions into k groups?
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]]]
A simple alternative view of this problem is the assignment of one of the three cluster labels to each element.
import itertools
def neclusters(l, k):
for labels in itertools.product(range(k), repeat=len(l)):
partition = [[] for i in range(k)]
for i, label in enumerate(labels):
partition[label].append(l[i])
yield partition
as with @val's answer, this can be wrapped to remove partitions with empty clusters.