Solution: Random partition
Let’s first load our randomization gun.
import random
random.seed(42)
rand = lambda : random.uniform(0, 1)
Random integer generation
Here is one possible solution to turning our float-based randomizer to an integer-based one. The idea is to separate the interval [0, 1) into bins of equal length, and then see which bin the random number falls into.
def random_int(a, b):
"""random integer in [a, b) that makes use of rand""" ##]
nbin = b - a # number of bins
lbin = 1.0/nbin # length of each bin
r = rand() # random number in [0, 1) ##]
return a + int(r/lbin) # which bin does r fall into?
Random partition generation
First, there is the issue of the empty set. You can either allow it to be a block in a partition or not. Not allowing it makes the programming problem a little bit easier, so we will go with that.
Here are two possible ways of generating a random parition of a given set (list):
- We shuffle the given list; and then start taking random sized blocks out of it until we run out of elements.
- We again shuffle the given list; this time we first randomly select the number of blocks in our partition, let’s say n; and then we randomly select n indices out of the list to determine the block boundaries.
We first define the shuffling function, which will be used in both methods.
def pick(lst):
"""pick maps a lst to (random element of lst, remaining elements of lst)"""
index = random_int(0, len(lst))
return (
lst[index],
lst[:index] + lst[index+1:]
)
def shuffle(lst):
"""return a random permutation of lst"""
if not lst:
return []
else:
x, rest = pick(lst)
return [x] + shuffle(rest)
Method 1
def take_from(n, lst):
"""returns the tuple (first n elms of lst, rest of lst).
Requires: n <= len(lst)
"""
assert n <= len(lst)
return (lst[:n], lst[n:])
def partition(lst):
"""return a random partition of lst"""
return _partition(shuffle(lst))
def _partition(lst):
if not lst:
return []
else:
block_size = random_int(1, len(lst) + 1)
block, rest = take_from(block_size, lst)
return [block] + _partition(rest)
Method 2
For this method we need a function to randomly pick n indices from a list of length m, where n <= m. This can be done by the pieces we already have, as I will show shortly; but there are other ways to do it as well.
def pick_indices(lst, n):
"""picks n non-zero indices from lst, and returns them in sorted order."""
assert n < len(lst)
return sorted(
take_from(n,
shuffle(
# we get a shuffle of the non-zero indices of lst
list(range(len(lst)))[1:])
)
#take_from returns a tuple, so we take the first element of the tuple
[0]
)
def partition2(lst):
"""return a random partition of lst"""
return _partition2(
# send the shuffle of lst
shuffle(lst),
# provide the list of random indices to determine the block boundaries
pick_indices(
lst,
# the number of blocks is a random integer between 1 and len(lst) inclusive.
# but the indices we will pick will be separators, so for k blocks you need k-1 separators,
# therefore we pick a random integer between 1 and len(lst) -1 inclusive.
random_int(1, len(lst))
)
)
def _partition2(lst, ind_lst, start=0):
if len(ind_lst) == 0:
return [lst[start:]]
else:
return [lst[start:ind_lst[0]]] + _partition2(lst, ind_lst[1:], ind_lst[0])
Further questions
Are these methods really random? Do the partition sets they generate obey what we would expect from a truely random partition selection? The answer requires more work on counting and probability to first determine the random distributions of partitions, and perhaps more programming to make experiments and empirically verify whether the code conforms to the expected distributions. Or perhaps there is a way to be certain without running any tests? (Un)fortunately, the term is over, so these will be the concern of future students of this course.