Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
43 - ZOJ Monthly, October 2005 - 1007
Graphical Partition

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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 n-node graphs is therefore the same as the number of n-node 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
0

Sample 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


Submit    Status