Opened 13 years ago

Closed 13 years ago

# [with patch, positive review] Permutation from a pair of standard tableaux

Reported by: Owned by: slabbe slabbe major sage-3.4.1 combinatorics robinson schensted sage-combinat

### Description

1. In sage 3.4, the Robinson Schensted algorithm is coded for a permutation :
```sage: p = Permutation([3, 6, 5, 2, 7, 4, 1])
sage: p.robinson_schensted()
[[[1, 4, 7], [2, 5], [3], [6]], [[1, 2, 5], [3, 6], [4], [7]]]
```

Since this algorithm is invertible, it would be nice to allow to construct a permutation from a pair of standard tableaux of the same shape.

1. The Robinson-Schensted is broken on the empty permutation. It should simply return a pair of empty tableaux :
```sage: p=Permutation([])
sage: p.robinson_schensted()
Traceback (most recent call last):
...
ValueError: invalid tableau
```

### comment:1 Changed 13 years ago by slabbe

• Status changed from new to assigned
• Summary changed from Permutation from a pair of standard tableaux to [with patch, needs review] Permutation from a pair of standard tableaux

### comment:2 Changed 13 years ago by slabbe

• Type changed from defect to enhancement

### comment:3 follow-up: ↓ 4 Changed 13 years ago by hivert

Dear Sebastien,

It's good to have this ! Thanks. There are three little problems:

1) The documentation says:

```-  a pair of two standard tableaux of the same shape.
The right tableau must be over the integers 1 to n,
where n is its size.
```

As far as I know a tableau with entries from 1 to n is what is called a *standard tableau*. When there are repeated entries the usual terminology is semi standard tableaux or young tableaux. See eg: http://en.wikipedia.org/wiki/Young_diagram

2) why not call it `robinson_schented_inv` ?

### comment:4 in reply to: ↑ 3 ; follow-up: ↓ 5 Changed 13 years ago by slabbe

Dear Florent,

Dear Sebastien,

It's good to have this ! Thanks.

Cool!

There are three little problems:

Did you forget the third one or is this a joke meaning you are of the second type of mathematician?

1) The documentation says:

```-  a pair of two standard tableaux of the same shape.
The right tableau must be over the integers 1 to n,
where n is its size.
```

As far as I know a tableau with entries from 1 to n is what is called a *standard tableau*.

And increasing in row and column. Right. I agree. I should remove the second sentence above.

So this leads me to a related question. From a permutation, Robinson-Schensted Algo gives a pair of standard tableaux :

```sage: p = Permutation([3, 6, 5, 2, 7, 4, 1])
sage: p.robinson_schensted()
[[[1, 4, 7], [2, 5], [3], [6]], [[1, 2, 5], [3, 6], [4], [7]]]
```

But from the following "non bijective" permutation, we obtain a pair of tableaux (p,q) where p is semi-standard and q is standard. Well, we can say more about p : there are no repeated entry, only possible weigth 1 and 0.

```sage: p = Permutation([3, 6, 5, 2, 117, 4, 1])
sage: p.robinson_schensted()
[[[1, 4, 117], [2, 5], [3], [6]], [[1, 2, 5], [3, 6], [4], [7]]]
sage: t1,t2 = _
sage: t1.weight()
[1, 1, 1, 1, 1, 1, 0, 0, 0, ..., 0, 0, 1]
sage: t2.weight()
[1, 1, 1, 1, 1, 1, 1]
```

Should from_tableaux handle the above pair of tableaux? Actually it does :

```sage: p = Permutation([3, 6, 5, 2, 117, 4, 1]) ; p
[3, 6, 5, 2, 117, 4, 1]
sage: import sage.combinat.permutation as permutation
sage: p.robinson_schensted()
[[[1, 4, 117], [2, 5], [3], [6]], [[1, 2, 5], [3, 6], [4], [7]]]
sage: permutation.from_tableaux(*_)
[3, 6, 5, 2, 117, 4, 1]
```

Then, what should the input of from_tableaux say? Should it say simply a pair of standard tableaux as robinson_shensted doc string says it returns a pair of standard tableaux? Should it say that it handles a pair (p, q) of tableaux where p is semi-standard (weigth 0 or 1) and q is standard?

When there are repeated entries the usual terminology is semi standard tableaux or young tableaux. See eg: http://en.wikipedia.org/wiki/Young_diagram

2) why not call it `robinson_schented_inv` ?

There is a section in permutation.py containing functions constructing a permutation from different objects :

```#############################
# Constructing Permutations #
#############################
def from_permutation_group_element(pge):
def from_rank(n, rank):
def from_inversion_vector(iv):
def from_cycles(n, cycles):
def from_lehmer_code(lehmer):
def from_reduced_word(rw):
```

The name from_tableaux was then natural. Also, I coded the function for a colleague used to mathematica and he told me in mathematica they use `TableauxToPermutation` and `PermutationToTableaux`. I don't mind change it to robinson_schensted_inv or robinson_schensted_inverse(). Do I?

### comment:5 in reply to: ↑ 4 Changed 13 years ago by hivert

Did you forget the third one or is this a joke meaning you are of the second type of mathematician?

Both !!! Every people doing combinatorics should know that he is of the second type ! Do you know how to count the number of twin prime numbers ? If not you are of the second type !

Then, what should the input of from_tableaux say? Should it say simply a pair of standard tableaux as robinson_shensted doc string says it returns a pair of standard tableaux? Should it say that it handles a pair (p, q) of tableaux where p is semi-standard (weigth 0 or 1) and q is standard?

Obviously you never tried the following one:

```sage: p = Permutation([1,3,2,2,4,3])
sage: p.robinson_schensted()
[[[1, 2, 2, 3], [3, 4]], [[1, 2, 4, 5], [3, 6]]]
sage: permutation.from_tableaux(*_)
[1, 3, 2, 2, 4, 3]
```

Yes !!! Do it !!! Try It !!!

There is a section in permutation.py containing functions constructing a permutation from different objects : [...] The name from_tableaux was then natural. Also, I coded the function for a colleague used to mathematica and he told me in mathematica they use `TableauxToPermutation` and `PermutationToTableaux`. I don't mind change it to robinson_schensted_inv or robinson_schensted_inverse(). Do I?

In MuPAD we had `schensted` and `schenstedInv`. I'd rather have either `robinson_schensted_inv}}/{{{inverse()` of `from_tableaux_pair`. I think you should ask for a vote on sage-combinat-devel.

Finally, my third remark is that you should raise a `ValueError` with a proper explanation of what is wrong if the two tableaux are not of the same shape:

```sage: permutation.from_tableaux(Tableau([[1,2,3]]), Tableau([[1,2]]))
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)

/home/averell/.sage/temp/tomahawk/7383/_home_averell__sage_init_sage_0.py in <module>()

/usr/local/sage/sage/local/lib/python2.5/site-packages/sage/combinat/permutation.pyc in from_tableaux(p, q)
3112     p = map(list, p)
3113     for n in range(size, 0, -1):
-> 3114         i,j = d[n]
3115         x = p[i][j]
3116         del p[i][j]

KeyError: 3
```

Cheers,

Florent

### Changed 13 years ago by slabbe

Against sage 3.4. This patch is part of sage-combinat tree.

slabbe

### comment:7 Changed 13 years ago by hivert

The review patche solve two remaining issues in the doc

1) The input was claimed to be "a pair (p, q) of tableaux [...]" which suggest that the function accept a *tuple*, whereas it actually needs two objects:

```robinson_schensted_inverse(t1, t2)
```

is correct whereas

```p = (t1,t2); robinson_schensted_inverse(p)
```

if not.

2) the submitted patch tests the result of `robinson_schensted_inverse` on things that are not semi-standard Young tableaux which should not be accepted by the constructor of tableaux. I even don't think that the RSK has any mathematical meaning for those objects, has it ? So I removed the tests and replaced them by a sentences saying that this should not be asked. Note that there is a plan to remove this feature for Tableaux and to add a new class called Fillings.

See the copy of the mail at the bottom of http://wiki.sagemath.org/CombinatorialClass

### comment:8 follow-up: ↓ 9 Changed 13 years ago by saliola

I think it would be better if the user can pass two lists that define tableaux to the constructor instead of having to first create the tableaux. Explicitly, I'd like to write:

```sage: Permutation(([[1,2],[3]], [[1,2],[3]]))
```

```sage: Permutation((Tableau([[1,2],[3]]), Tableau([[1,2],[3]])))
```

especially since

```sage: [[1,2],[3]] in StandardTableaux(3)
True
```

Looking at the code suggests this is possible? Are there any reasons to not do this?

### comment:9 in reply to: ↑ 8 Changed 13 years ago by slabbe

Hi,

I agree with saliola suggestion and I think it is possible. We simply need to have a unique way to understand the input. A list of list of list -> tableau. A list of tuple -> cycles...etc.

I will propose a new patch soon...

slabbe

### comment:10 Changed 13 years ago by slabbe

• Summary changed from [with patch, needs review] Permutation from a pair of standard tableaux to [with patch, needs work] Permutation from a pair of standard tableaux

### Changed 13 years ago by slabbe

This patch applies over the precedent two.

### comment:11 Changed 13 years ago by slabbe

• Summary changed from [with patch, needs work] Permutation from a pair of standard tableaux to [with patch, needs review] Permutation from a pair of standard tableaux

### comment:12 Changed 13 years ago by hivert

• Summary changed from [with patch, needs review] Permutation from a pair of standard tableaux to [with patch, positive review] Permutation from a pair of standard tableaux

Everthing looks good. `All tests passed!` I'm giving a positive review.

Florent

### comment:13 Changed 13 years ago by mabshoff

• Resolution set to fixed
• Status changed from assigned to closed

Merged all three patches in Sage 3.4.1.rc1.

Cheers,

Michael