The following code generates all partitions of length k (k-subset partitions) for a given list. the algorithm could be found in this topic.
def algorithm_u(ns, m): def visit(n, a): ps = [[] for i in xrange(m)] for j in xrange(n): ps[a[j + 1]].append(ns[j]) return ps def f(mu, nu, sigma, n, a): if mu == 2: yield visit(n, a) else: for v in f(mu - 1, nu - 1, (mu + sigma) % 2, n, a): yield v if nu == mu + 1: a[mu] = mu - 1 yield visit(n, a) while a[nu] > 0: a[nu] = a[nu] - 1 yield visit(n, a) elif nu > mu + 1: if (mu + sigma) % 2 == 1: a[nu - 1] = mu - 1 else: a[mu] = mu - 1 if (a[nu] + sigma) % 2 == 1: for v in b(mu, nu - 1, 0, n, a): yield v else: for v in f(mu, nu - 1, 0, n, a): yield v while a[nu] > 0: a[nu] = a[nu] - 1 if (a[nu] + sigma) % 2 == 1: for v in b(mu, nu - 1, 0, n, a): yield v else: for v in f(mu, nu - 1, 0, n, a): yield v def b(mu, nu, sigma, n, a): if nu == mu + 1: while a[nu] < mu - 1: yield visit(n, a) a[nu] = a[nu] + 1 yield visit(n, a) a[mu] = 0 elif nu > mu + 1: if (a[nu] + sigma) % 2 == 1: for v in f(mu, nu - 1, 0, n, a): yield v else: for v in b(mu, nu - 1, 0, n, a): yield v while a[nu] < mu - 1: a[nu] = a[nu] + 1 if (a[nu] + sigma) % 2 == 1: for v in f(mu, nu - 1, 0, n, a): yield v else: for v in b(mu, nu - 1, 0, n, a): yield v if (mu + sigma) % 2 == 1: a[nu - 1] = 0 else: a[mu] = 0 if mu == 2: yield visit(n, a) else: for v in b(mu - 1, nu - 1, (mu + sigma) % 2, n, a): yield v n = len(ns) a = [0] * (n + 1) for j in xrange(1, m + 1): a[n - m + j] = j - 1 return f(m, n, 0, n, a) we know that number of k-subsets of a given list is equal to Stirling number and it could be very big for some large lists.
the code above returns a Python generator that could generate all possible k-subset partitions for the given list with calling its next method. accordingly, if I want to get only one of these partitions randomly, I have to either call next method for some random times (which makes it really slow if the Stirling number is big) or use the itertools.islice method to get a slice of size one which is really slow as before.
I'm trying to avoid listing all partitions because it would be waste of time and speed and even memory (because calculations are a lot and memory is important in my case).
the question is how can I generate only one of k-subset partitions without generating the rest ? or at least make the procedure very faster than what explained above. I need the performance because I need to get only one of them each time and I'm running the application for maybe more than ten million times.
I'd appreciate any help.
EDIT: EXAMPLE
list : { 1, 2, 3 }
for k = 3:
{ {1}, {2}, {3} } for k = 2:
{ {1, 2}, {3} } { {1, 3}, {2} } { {1}, {2, 3} } and for k = 1:
{ {1, 2, 3} } consider k = 2, is there any way I can generate only one of these 3 partitions randomly, without generating the other 2? note that I want to generate random partition for any given k not only a random partition of any k which means if I set the k to 2 I would like to generate only one of these 3 not one of all 5.
Regards,
Mohammad
3 Answers
Answers 1
You can count Stirling numbers efficiently with a recursive algorithm by storing previously computed values:
fact=[1] def nCr(n,k): """Return number of ways of choosing k elements from n""" while len(fact)<=n: fact.append(fact[-1]*len(fact)) return fact[n]/(fact[k]*fact[n-k]) cache = {} def count_part(n,k): """Return number of ways of partitioning n items into k non-empty subsets""" if k==1: return 1 key = n,k if key in cache: return cache[key] # The first element goes into the next partition # We can have up to y additional elements from the n-1 remaining # There will be n-1-y left over to partition into k-1 non-empty subsets # so n-1-y>=k-1 # y<=n-k t = 0 for y in range(0,n-k+1): t += count_part(n-1-y,k-1) * nCr(n-1,y) cache[key] = t return t Once you know how many choices there are, you can adapt this recursive code to generate a particular partition:
def ith_subset(A,k,i): """Return ith k-subset of A""" # Choose first element x n = len(A) if n==k: return A if k==0: return [] for x in range(n): # Find how many cases are possible with the first element being x # There will be n-x-1 left over, from which we choose k-1 extra = nCr(n-x-1,k-1) if i<extra: break i -= extra return [A[x]] + ith_subset(A[x+1:],k-1,i) def gen_part(A,k,i): """Return i^th k-partition of elements in A (zero-indexed) as list of lists""" if k==1: return [A] n=len(A) # First find appropriate value for y - the extra amount in this subset for y in range(0,n-k+1): extra = count_part(n-1-y,k-1) * nCr(n-1,y) if i<extra: break i -= extra # We count through the subsets, and for each subset we count through the partitions # Split i into a count for subsets and a count for the remaining partitions count_partition,count_subset = divmod(i,nCr(n-1,y)) # Now find the i^th appropriate subset subset = [A[0]] + ith_subset(A[1:],y,count_subset) S=set(subset) return [subset] + gen_part([a for a in A if a not in S],k-1,count_partition) As an example, I've written a test program that produces different partitions of 4 numbers:
def test(A): n=len(A) for k in [1,2,3,4]: t = count_part(n,k) print k,t for i in range(t): print " ",i,gen_part(A,k,i) test([1,2,3,4]) This code prints:
1 1 0 [[1, 2, 3, 4]] 2 7 0 [[1], [2, 3, 4]] 1 [[1, 2], [3, 4]] 2 [[1, 3], [2, 4]] 3 [[1, 4], [2, 3]] 4 [[1, 2, 3], [4]] 5 [[1, 2, 4], [3]] 6 [[1, 3, 4], [2]] 3 6 0 [[1], [2], [3, 4]] 1 [[1], [2, 3], [4]] 2 [[1], [2, 4], [3]] 3 [[1, 2], [3], [4]] 4 [[1, 3], [2], [4]] 5 [[1, 4], [2], [3]] 4 1 0 [[1], [2], [3], [4]] As another example, there are 10 million partitions of 1,2,3,..14 into 4 parts. This code can generate all partitions in 44 seconds with pypy.
There are 50,369,882,873,307,917,364,901 partitions of 1,2,3,...,40 into 4 parts. This code can generate 10 million of these in 120 seconds with pypy running on a single processor.
To tie things together, you can use this code to generate a single random partition of a list A into k non-empty subsets:
import random def random_ksubset(A,k): i = random.randrange(0,count_part(len(A),k)) return gen_part(A,k,i) Answers 2
How about something like this:
import itertools import random def random_ksubset(ls, k): # we need to know the length of ls, so convert it into a list ls = list(ls) # sanity check if k < 1 or k > len(ls): return [] # Create a list of length ls, where each element is the index of # the subset that the corresponding member of ls will be assigned # to. # # We require that this list contains k different values, so we # start by adding each possible different value. indices = list(range(k)) # now we add random values from range(k) to indices to fill it up # to the length of ls indices.extend([random.choice(list(range(k))) for _ in range(len(ls) - k)]) # shuffle the indices into a random order random.shuffle(indices) # construct and return the random subset: sort the elements by # which subset they will be assigned to, and group them into sets return [{x[1] for x in xs} for (_, xs) in itertools.groupby(sorted(zip(indices, ls)), lambda x: x[0])] This produces random k-subset partitions like so:
>>> ls = {1,2,3} >>> print(random_ksubset(ls, 2)) [set([1, 2]), set([3])] >>> print(random_ksubset(ls, 2)) [set([1, 3]), set([2])] >>> print(random_ksubset(ls, 2)) [set([1]), set([2, 3])] >>> print(random_ksubset(ls, 2)) [set([1]), set([2, 3])] This method satisfies OP's requirement of getting one randomly-generated partition, without enumerating all possible partitions. Memory complexity here is linear. Run-time complexity is O(N log N) due to the sort. I suppose it might be possible to get this down to linear, if that was important, using a more complicated method of constructing the return value.
As @Leon points out, this satisfies the requirements of his option 2 in trying to define the problem. What this won't do is deterministically generate partition #N (this is Leon's option 1, which would allow you to randomly pick an integer N and then retrieve the corresponding partition). Leon's clarification is important, because, to satisfy the spirit of the question, every possible partition of the collection should be generated with equal probability. On our toy problem, this is the case:
>>> from collections import Counter >>> Counter(frozenset(map(frozenset, random_ksubset(ls, 2))) for _ in range(10000)) Counter({frozenset({frozenset({2, 3}), frozenset({1})}): 3392, frozenset({frozenset({1, 3}), frozenset({2})}): 3212, frozenset({frozenset({1, 2}), frozenset({3})}): 3396}) However. In general, this method does not generate each partition with equal probability. Consider:
>>> Counter(frozenset(map(frozenset, random_ksubset(range(4), 2))) ... for _ in range(10000)).most_common() [(frozenset({frozenset({1, 3}), frozenset({0, 2})}), 1671), (frozenset({frozenset({1, 2}), frozenset({0, 3})}), 1667), (frozenset({frozenset({2, 3}), frozenset({0, 1})}), 1642), (frozenset({frozenset({0, 2, 3}), frozenset({1})}), 1285), (frozenset({frozenset({2}), frozenset({0, 1, 3})}), 1254), (frozenset({frozenset({0, 1, 2}), frozenset({3})}), 1245), (frozenset({frozenset({1, 2, 3}), frozenset({0})}), 1236)] We can see here that we are more likely to generate "more balanced" partitions (because there are more ways to construct these). The partitions that contain singleton sets are produced less frequently.
It seems that an efficient uniform sampling method over k-partitions of sets is sort of an unsolved research question (also see mathoverflow). Nijenhuis and Wilf give code for sampling from all partitions (Chapter 12), which could work with rejection testing, and @PeterdeRivaz's answer can also uniformly sample a k-partition. The drawback with both of these methods is that they require computing the Stirling numbers, which grow exponentially in n, and the algorithms are recursive, which I think will make them slow on large inputs. As you mention "millions" of partitions in your comment, I think that these approaches will only be tractable up to a certain input size.
A. Nijenhuis and H. Wilf. Combinatorial Algorithms for Computers and Calculators. Academic Press, Orlando FL, second edition, 1978.
Exploring Leon's option 1 might be interesting. Here's a rough procedure to deterministically produce a particular partition of a collection using @Amadan's suggestion of taking an integer value interpreted as a k-ary number. Note that not every integer value produces a valid k-subset partition (because we disallow empty subsets):
def amadan(ls, N, k): """ Given a collection `ls` with length `b`, a value `k`, and a "partition number" `N` with 0 <= `N` < `k**b`, produce the Nth k-subset paritition of `ls`. """ ls = list(ls) b = len(ls) if not 0 <= N < k**b: return None # produce the k-ary index vector from the number N index = [] # iterate through each of the subsets for _ in range(b): index.append(N % k) N //= k # subsets cannot be empty if len(set(index)) != k: return None return frozenset(frozenset(x[1] for x in xs) for (_, xs) in itertools.groupby(sorted(zip(index, ls)), lambda x:x[0])) We can confirm that this generates the Stirling numbers properly:
>>> for i in [(4,1), (4,2), (4,3), (4,4), (5,1), (5,2), (5,3), (5,4), (5,5)]: ... b,k = i ... r = [amadan(range(b), N, k) for N in range(k**b)] ... r = [x for x in r if x is not None] ... print(i, len(set(r))) (4, 1) 1 (4, 2) 7 (4, 3) 6 (4, 4) 1 (5, 1) 1 (5, 2) 15 (5, 3) 25 (5, 4) 10 (5, 5) 1 This may also be able to produce each possible partition with equal probability; I'm not quite sure. Here's a test case, where it works:
>>> b,k = 4,3 >>> r = [amadan(range(b), N, k) for N in range(k**b)] >>> r = [x for x in r if x is not None] >>> print(Counter([' '.join(sorted(''.join(map(str, x)) for x in p)) for p in r])) Counter({'0 13 2': 6, '01 2 3': 6, '0 12 3': 6, '03 1 2': 6, '02 1 3': 6, '0 1 23': 6}) Another working case:
>>> b,k = 5,4 >>> r = [amadan(range(b), N, k) for N in range(k**b)] >>> r = [x for x in r if x is not None] >>> print(Counter([' '.join(sorted(''.join(map(str, x)) for x in p)) for p in r])) Counter({'0 12 3 4': 24, '04 1 2 3': 24, '0 1 23 4': 24, '01 2 3 4': 24, '03 1 2 4': 24, '0 13 2 4': 24, '0 1 24 3': 24, '02 1 3 4': 24, '0 1 2 34': 24, '0 14 2 3': 24}) So, to wrap this up in a function:
def random_ksubset(ls, k): ls = list(ls) maxn = k**len(ls)-1 rv = None while rv is None: rv = amadan(ls, random.randint(0, maxn), k) return rv And then we can do:
>>> random_ksubset(range(3), 2) frozenset({frozenset({2}), frozenset({0, 1})}) >>> random_ksubset(range(3), 2) frozenset({frozenset({1, 2}), frozenset({0})}) >>> random_ksubset(range(3), 2) frozenset({frozenset({1, 2}), frozenset({0})}) >>> random_ksubset(range(3), 2) frozenset({frozenset({2}), frozenset({0, 1})}) Answers 3
tl;dr:
The k-subset partitions for a given n and k can be divided into types, based on which elements are the first to go into as yet empty parts. Each of these types is represented by a bit pattern with n-1 bits of which k-1 are set. While the number of partitions is huge (given by the second Stirling number), the number of types is much smaller, e.g.:
n = 21, k = 8
number of partitions: S(21,8) = 132,511,015,347,084
number of types: (n-1 choose k-1) = 77,520
Calculating how many partitions there are of each type is simple, based on the position of the zeros in the bit pattern. If you make a list of all the types (by iterating over all n:k bit patterns) and keep a running total of the number of partitions, you can then use a binary search on this list to find the type of the partition with a given rank (in Log2(n-1 choose k-1) steps; 17 for the example above), and then translate the bit pattern into a partition and calculate into which part each element goes (in n steps). Every part of this method can be done iteratively, requiring no recursion.
Here's a non-recursive solution. I've tried to roll my own, but it may (partially) overlap with Peter's answer or existing methods.
If you have a set of n elements, e.g. with n=8:
{a,b,c,d,e,f,g,h}
then k-subset partitions will take this shape, e.g. with k=5:
{a,e} {b,c,h} {d} {f} {g}
This partition can also be written as:
1,2,2,3,1,4,5,2
which lists which part each of the elements goes in. So this sequence of n digits with values from 1 to k represents a k-subset partition of n elements.
However, not all such sequences are valid partitions; every digit from 1 to k must be present, otherwise there would be empty parts:
1,2,2,3,1,3,5,2 → {a,e} {b,c,h} {d,f} {} {g}
Also, to avoid duplicates, digit x can only be used after digit x-1 has been used. So the first digit is always 1, the second can be at most 2, and so on. If in the example we use digits 4 and 5 before 3, we get duplicate partitions:
1,2,2,3,1,4,5,2 → {a,e} {b,c,h} {d} {f} {g}
1,2,2,4,1,5,3,2 → {a,e} {b,c,h} {g} {d} {f}
When you group the partitions based on when each part is first used, you get these types:
1,1,1,1,2,3,4,5 0001111 11111111 1 1 1,1,1,2,12,3,4,5 0010111 11112111 2 2 1,1,1,2,3,123,4,5 0011011 11111311 3 3 1,1,1,2,3,4,1234,5 0011101 11111141 4 4 1,1,1,2,3,4,5,12345 0011110 11111115 5 5 1,1,2,12,12,3,4,5 0100111 11122111 2*2 4 1,1,2,12,3,123,4,5 0101011 11121311 2*3 6 1,1,2,12,3,4,1234,5 0101101 11121141 2*4 8 1,1,2,12,3,4,5,12345 0101110 11121115 2*5 10 1,1,2,3,123,123,4,5 0110011 11113311 3*3 9 1,1,2,3,123,4,1234,5 0110101 11113141 3*4 12 1,1,2,3,123,4,5,12345 0110110 11113115 3*5 15 1,1,2,3,4,1234,1234,5 0111001 11111441 4*4 16 1,1,2,3,4,1234,5,12345 0111010 11111415 4*5 20 1,1,2,3,4,5,12345,12345 0111100 11111155 5*5 25 1,2,12,12,12,3,4,5 1000111 11222111 2*2*2 8 1,2,12,12,3,123,4,5 1001011 11221311 2*2*3 12 1,2,12,12,3,4,1234,5 1001101 11221141 2*2*4 16 1,2,12,12,3,4,5,12345 1001110 11221115 2*2*5 20 1,2,12,3,123,123,4,5 1010011 11213311 2*3*3 18 1,2,12,3,123,4,1234,5 1010101 11213141 2*3*4 24 1,2,12,3,123,4,5,12345 1010110 11213115 2*3*5 30 1,2,12,3,4,1234,1234,5 1011001 11211441 2*4*4 32 1,2,12,3,4,1234,5,12345 1011010 11211415 2*4*5 40 1,2,12,3,4,5,12345,12345 1011100 11211155 2*5*5 50 1,2,3,123,123,123,4,5 1100011 11133311 3*3*3 27 1,2,3,123,123,4,1234,5 1100101 11133141 3*3*4 36 1,2,3,123,123,4,5,12345 1100110 11133115 3*3*5 45 1,2,3,123,4,1234,1234,5 1101001 11131441 3*4*4 48 1,2,3,123,4,1234,5,12345 1101010 11131415 3*4*5 60 1,2,3,123,4,5,12345,12345 1101100 11131155 3*5*5 75 1,2,3,4,1234,1234,1234,5 1110001 11114441 4*4*4 64 1,2,3,4,1234,1234,5,12345 1110010 11114415 4*4*5 80 1,2,3,4,1234,5,12345,12345 1110100 11114155 4*5*5 100 1,2,3,4,5,12345,12345,12345 1111000 11111555 5*5*5 125 SUM = 1050 In the above diagram, a partition of the type:
1,2,12,3,123,4,1234,5
means that:
a goes into part 1
b goes into part 2
c goes into part 1 or 2
d goes into part 3
e goes into part 1, 2 or 3
f goes into part 4
g goes into part 1, 2, 3 or 4
h goes into part 5
So partitions of this type have a digit that can have 2 values, a digit that can have 3 values, and a digit that can have 4 values (this is indicated in the third column in the diagram above). So there are a total of 2 × 3 × 4 partitions of this type (as indicated in columns 4 and 5). The sum of these is of course the Stirling number: S(8,5) = 1050.
The second column in the diagram is another way of notating the type of the partition: after starting with 1, every digit is either a digit that has been used before, or a step up (i.e. the highest digit used so far + 1). If we represent these two options by 0 and 1, we get e.g.:
1,2,12,3,123,4,1234,5 → 1010101
where 1010101 means:
Start with 1
1 → step up to 2
0 → repeat 1 or 2
1 → step up to 3
0 → repeat 1, 2 or 3
1 → step up to 4
0 → repeat 1, 2, 3 or 4
1 → step up to 5
So every binary sequence with n-1 digits and k-1 ones represents a type of partition. We can calculate the number of partitions of a type by iterating over the digits from left to right, incrementing a factor when we find a one, and multiplying with the factor when we find a zero, e.g.:
1,2,12,3,123,4,1234,5 → 1010101
Start with product = 1, factor = 1
1 → increment factor: 2
0 → product × factor = 2
1 → increment factor: 3
0 → product × factor = 6
1 → increment factor: 4
0 → product × factor = 24
1 → increment factor: 5
And again for this example, we find that there are 24 partitions of this type. So, counting the partitions of each type can be done by iterating over all n-1-digit integers with k-1 digits set, using any method (e.g. Gosper's Hack):
0001111 1 1 0010111 2 3 0011011 3 6 0011101 4 10 0011110 5 15 0100111 4 19 0101011 6 25 0101101 8 33 0101110 10 43 0110011 9 52 0110101 12 64 0110110 15 79 0111001 16 95 0111010 20 115 0111100 25 140 1000111 8 148 1001011 12 160 1001101 16 176 1001110 20 196 1010011 18 214 1010101 24 238 1010110 30 268 1011001 32 300 1011010 40 340 1011100 50 390 1100011 27 417 1100101 36 453 1100110 45 498 1101001 48 546 1101010 60 606 1101100 75 681 1110001 64 745 1110010 80 825 1110100 100 925 1111000 125 1050 Finding a random partition then means choosing a number from 1 to S(n,k), going over the counts per partition type while keeping a running total (column 3 above), and picking the corresponding partition type, and then calculating the value of the repeated digits, e.g.:
S(8,5) = 1050
random pick: e.g. 333
type: 1011010 → 1,2,12,3,4,1234,5,12345
range: 301 - 340
variation: 333 - 301 = 32
digit options: 2, 4, 5
digit values: 20, 5, 1
variation: 32 = 1 × 20 + 2 × 5 + 2 × 1
digits: 1, 2, 2 (0-based) → 2, 3, 3 (1-based)
partition: 1,2,2,3,4,3,5,3
and the 333rd partition of 8 elements in 5 parts is:
1,2,2,3,4,3,5,3 → {a} {b,c} {d,f,h} {e} {g}
There are a number of options to turn this into code; if you store the n-1-digit numbers as a running total, you can do subsequent lookups using a binary search over the list, whose length is C(n-1,k-1), to reduce time complexity from O(C(n-1,k-1)) to O(Log2(C(n-1,k-1))).
I've made a first test in JavaScript (sorry, I don't speak Python); it's not pretty but it demonstrates the method and is quite fast. The example is for the case n=21 and k=8; it creates the count table for 77,520 types of partitions, returns the total number of partitions 132,511,015,347,084 and then retrieves 10 randomly picked partitions within that range. This version just iterates over the whole list, so each lookup could take up to 77,520 steps, but with a binary search that would be just Log2(77,520) = 17 steps. (note: the code is zero-based, unlike the explanation above)
function kSubsetPartitions(n, k) { // Constructor this.types = []; this.count = []; this.total = 0; this.elems = n; var bits = (1 << k - 1) - 1, done = 1 << n - 1; do { this.total += variations(bits); this.types.push(bits); this.count.push(this.total); } while (!((bits = next(bits)) & done)); function variations(bits) { var product = 1, factor = 1, mask = 1 << n - 2; while (mask) { if (bits & mask) ++factor; else product *= factor; mask >>= 1; } return product; } function next(a) { // Gosper's Hack var c = (a & -a), r = a + c; return (((r ^ a) >> 2) / c) | r; } } kSubsetPartitions.prototype.partition = function(rank) { var type = 0, range = 1; while (this.count[type] <= rank) ++type; // Replace by binary search with 3/4 bias if (type) { rank -= this.count[type - 1]; range = this.count[type] - this.count[type - 1]; } return translate(this.types[type], this.elems, range, rank); // This translates the 1010101 format and creates the correct partition // for the given rank, using a letter format for demonstration purposes function translate(bits, len, range, rank) { var partition = [["A"]], part, max = 0, mask = 1 << len - 2; for (var i = 1; i < len; i++, mask >>= 1) { if (!(bits & mask)) { range /= (max + 1); part = Math.floor(rank / range); rank %= range; } else part = ++max; if (!partition[part]) partition[part] = ""; partition[part] += String.fromCharCode(65 + i); } return partition.join(" / "); } } var ksp = new kSubsetPartitions(21, 8); document.write("Number of k-subset partitions for n,k = 21,8 → " + ksp.total.toLocaleString("en-US") + "<br>"); for (var tests = 10; tests; tests--) { var rnd = Math.floor(Math.random() * ksp.total); document.write("Partition " + rnd.toLocaleString("en-US", {minimumIntegerDigits: 15}) + " → " + ksp.partition(rnd) + "<br>"); }If you're going to do more lookups than there are partition types, you could already translate the bit patterns into a friendlier version, to speed up the lookups, e.g.:
type = {partition: [1,2,,3,,4,,5], unit: [12,4,1], position: [2,4,6]}
so that you can quickly divide the rank by the units and place the results at the right positions in the partition.
Also, it would be possible to create a version of this code which doesn't store the list of counts, and thus has very limited memory usage; the downside is that you would have to iterate over the partition types once to find the total number of partitions, and then once again for each lookup (though only partially, up to the point when the right partition type is found).
(Work in progress. If anyone can translate this code into Python, be my guest.)
0 comments:
Post a Comment