Random Partition of a Sequence

Here’s a mildly interesting puzzle: suppose you have an ordered sequence (e.g. the numbers 1 to 10). How would you randomly divide it into partitions such that any possible partition is equally likely? Your partitions can have anywhere between one and ten elements. One example partition could be [1 2 3 4] [5] [6 7] [8] [9 10].

Before I give you the solution, here are a couple of hints:

There are four possible partitions of three elements:
```
[1] [2] [3]
[1 2] [3]
[1] [2 3]
[1 2 3]
```
If you were to run your function a large number of times, you would expect each one of those to occur close to 25% of the time.

In Clojure, you could test your random partition function like this:

(frequencies
 (take 100000
       (repeatedly #(random-partition [1 2 3]))))

And if your function worked properly, you’d expect your output to look like:

{((1 2 3)) 24726, ((1) (2) (3)) 25049, 
((1) (2 3)) 25077, ((1 2) (3)) 25148}

A good way to look at this problem is to first calculate the number of possible partitions. If we think of the sequence as a piece of tape that we can cut, we realize that for three elements there are two places to cut. More generally, for N elements there are N-1 cutting points. At every point we can choose to cut or not to cut, which means that there are 2^(N-1) possible partitions.

With this in mind a straightforward solution to the problem is:

traverse the sequence from left to right
toss a coin at every cutting point
leave it alone if it’s heads, cut if it’s tails

Note that you don’t even need to know the length of the sequence in advance. In fact, you could start cutting an infinite sequence and grab the first few random pieces (i.e. stop after a certain number of tails).

Here’s my Clojure implementation of this algorithm:

(defn random-partition [xs]
  (lazy-seq
   (when (seq xs)
     (loop [i 1]
       (if (zero? (rand-int 2))
         (recur (inc i))
         (let [[a b] (split-at i xs)]
           (cons a (random-partition b))))))))

And a much more concise one based on partition-by, courtesy of Gary Fredericks via the #clojure irc channel on Freenode:

(defn random-partition [xs]
  (partition-by (fn[_] (rand-nth [true false])) xs))

You can take 10 random pieces of the natural numbers with:

(take 10 (random-partition (range)))

and expect a result like:

((0) (1) (2) (3) (4 5 6 7) (8 9 10) (11 12) (13 14 15) (16 17) (18 19))

Please do not use this puzzle as an interview question 🙂

Leave a Reply Cancel reply