
ZOJ Problem Set  2576
A partition {A1,A2, ... ,An} is called graphical if there exists a graph G having degree sequence {A1,A2, ... ,An}. The number of graphical partitions on nnode graphs is therefore the same as the number of nnode graphs with no isolated points. It is possible for two topologically distinct graphs to have the same degree sequence. The following figure shows the graphical partitions on n = 1, 2, 3, ... edges. XKA graphical partition is defined based on regular graphical partition, the only difference is that the graph used to generate the sequence can contain multiple edges connected on two same points. Now you are asked to calculate all the XKA graphical partitions on n edges. The following figure shows the XKA graphical partitions on n = 1, 2, 3, ... edges. Input: There are multiple test cases, each case consists of a integer N (1 <= N <= 10) which is the number of edges. A test case with N = 0 indicates the end of input. Output: For each test case, output all the possible XKA graphical partitions. You should sort the elements in each partition first, and then sort the partitions before output them. After each test case, output a blank line. Sample Input:1 2 3 0Sample Output: {1,1} {1,1,1,1} {1,1,2} {2,2} {1,1,1,1,1,1} {1,1,1,1,2} {1,1,1,3} {1,1,2,2} {1,2,3} {2,2,2} {3,3} Author: ZHENG, Jianqiang Source: ZOJ Monthly, October 2005 