CS293 Assignment 3-Partitions Solution

This problem is about representing partitions of the set {0,1,2,...,n−1}. A partition of a set is a collection of disjoint non-empty subsets of the set, whose union is the whole set. In other words, every element in the set belongs to exactly one of the subsets, and each subset is non-empty. Such a partition can be represented uniquely by what is called a restricted growth sequence p0,p1,...,pn−1, that satisfies p0 = 0 and 0 ≤ pi ≤ 1+max0≤j<i pj for i > 0. Here, pi denotes the ‘part number’ of the subset containing i. The parts are numbered in increasing order of their smallest elements. The part containing 0 is always 0. If element i is in the same part as some smaller element j, pi = pj, but if it is the smallest element in its part then i will be in a new part with number 1 + max0≤j<i pj. Thus the partition {{0,3},{1,2}} would be represented by the sequence 0,1,1,0. Given this representation, we can define an ordering on the partitions based on the lexicographic ordering of the sequences.
A partition p0,p1,...,pn−1 is less than q0,...,qn−1 if there exists an index i such that pi < qi and pj = qj for all 0 ≤ j < i. The rank of a partition is the number of partitions that are less than it. The partition 0,0,...,0 will have rank 0, and the partition 0,1,2,...,n−1 will have the highest rank. The rank of 0,1,1,0 is 8.
You have to write a function that will take a restricted growth sequence as input, and output its rank. You have to also write a function that will take the rank and output the corresponding sequence. Such functions are useful because we can work with just numbers instead of partitions.
Input/Output. The first line of input will specify n and the number of test cases t. The next t lines will contain one test case each. Each test case will be of the form R p0 p1 ... pn−1 or U r. Here p0,p1,...,pn−1 is a restricted growth sequence whose rank is to be computed, and r is the rank for which the corresponding sequence is to be found. R and U indicate the type of operation to be performed. n will be at most 20 and t will be at most 106.
Hint. To know how many sequences are less than a given sequence, we need to know for any given partial sequence, how many sequences of length n start with that sequence. For example, if a sequence starts with 0,1 any sequence starting with 0,0 will be less than it. If we can count this easily, we can find the rank. The crucial observation is that the number of sequences starting with a given sequence depends only on the length and maximum value of the sequence. If we can compute this number for each possible value of the maximum and length and store it, we can use it whenever needed, without recomputing it. This is a technique called dynamic programming that is used heavily in designing efficient alogorithms.
Can you compute these numbers easily using induction?
Submission. Submit a single file named RollNo 3.cpp .
1