Introduction to Programming in Python, Aug-Dec 2014
                          Assignment 6
                  Due Tuesday, 4 November, 2014

----------------------------------------------------------------------
NOTE: The usual rules apply about file names for submitting your
      assignment.
----------------------------------------------------------------------

Filename: young.py

Given a sequence of *distinct* numbers, we construct a two
dimensional table as follows:

1. If the next number is larger than all numbers in the first row
   of the table, add it at the right end of the first row.  This
   includes the case when the row is currently empty.

2. Otherwise, let the new number be x and let y be the smallest
   number in the first row that is larger than x.  Replace y by x
   and insert y into the second row using the same rules.

   In other words, if y is larger than every number in the second
   row, add y at the end of the second row.  Otherwise, identify
   the smallest z in the second row that is bigger than y,
   replace y by z and insert z in the the third row using the
   same rules.  And so on ...

For instance, suppose the input sequence is 3,4,9,2,5,1.  We
would build the table as follows:

   Action       Resulting table     Explanation

1. Insert 3     3                   Rule 1: Add 3 at end of row

2. Insert 4     3 4                 Rule 1: Add 4 at end of row

3. Insert 9     3 4 9               Rule 1: Add 9 at end of row

4. Insert 2     2 4 9               Rule 2: 2 bumps 3 
                3                   Rule 1: Add 3 at end of row

5. Insert 5     2 4 5               Rule 2: 5 bumps 9
                3 9                 Rule 1: Add 9 at end of row

6. Insert 1     1 4 5               Rule 2: 1 bumps 2
                2 9                 Rule 2: 2 bumps 3
                3                   Rule 1: Add 3 at end of row

The final table is called a Young tableau for the given
permutation.  More than one permutation may generate the same
tableau.  In this case, you can check that the permutations
3,2,1,4,9,5 and 3,2,1,9,4,5 also generate the same tableau as
3,4,9,2,5,1.  In fact there are 16 different permutations of
these six numbers that generate this particular tableau.

You have to write a Python program that takes as input a Young
tableau and reconstructs all possible input permutations that
give rise to the given tableau.

The input tableau will be given in a text file "young.in"
containing exactly as many lines as there are rows in the
tableau.  Each line will contain a single row of the tableau,
with the numbers separated by a single space.  You can assume
that no numbers are repeated in the tableau.

Your program should print out each valid input permutation for
the given tableau on a separate line on the screen.  The numbers
in the permutation should be separated by single spaces.

----------------------------------------------------------------------

How to solve the problem:
-------------------------

A little analysis shows that each row in the tableau is always
longer than or equal to the next row.  We define a value to be a
"corner" if it is the last element in some row and the current
row is strictly longer than the next row.

The process of adding a number always ends with an application of
Rule 1, and it is not difficult to verify that the new position
created in the tableau must be a corner.

To reconstruct the permutation, we have to invert each insertion.
At each stage, the corner elements are possible candidates to
invert.

For example, in the final tableau above, the corners are 5, 9 and
3.  Hence, one of these must have moved into its position in the
last move.  We pick one of these corners and work backwards.

Suppose we pick the corner element 9.  This 9 must have come from
row 1.  Working backwards, it must have been displaced by 5 (the
biggest number in row 1 that is smaller than 9).  So, at the
previous step we had a tableau

    1 4 9
    2
    3

and the last element of the permutation we are constructing is 5.

Now the corners are 3 and 9 (2 is not a corner, though it is the
last element in its row).  Suppose we pick 3.  3 must have been
bumped by 2, which in turn must have been bumped by 1, so we get
a new tableau

    2 4 9
    3

and the candidate permutation we are building ends with 1,5.

The corners are again 3 and 9.  If we now invert 3 again, we get

    3 4 9              

and the last three elements of the candidate permutation are
2,1,5.

From this stage we have only one corner to choose at each step,
so we successively invert 9, 4 and 3 to get a candidate
permutation

    3,4,9,2,1,5

that gives rise to this same tableau.

Clearly, the permutation that we generate depends on the corner
element that we pick at each stage.

Your program should systematically explore all possibilities and
generate all valid input permutations for the given tableau.

======================================================================