info prev up next book cdrom email home

Bumping Algorithm

Given a Permutation $\{p_1, p_2, \ldots, p_n\}$ of $\{1, \ldots, n\}$, the bumping algorithm constructs a standard Young Tableau by inserting the $p_i$ one by one into an already constructed Young Tableau. To apply the bumping algorithm, start with $\{\{p_1\}\}$, which is a Young Tableau. If $p_1$ through $p_k$ have already been inserted, then in order to insert $p_{k+1}$, start with the first line of the already constructed Young Tableau and search for the first element of this line which is greater than $p_{k+1}$. If there is no such element, append $p_{k+1}$ to the first line and stop. If there is such an element (say, $p_p$), exchange $p_p$ for $p_{k+1}$, search the second line using $p_p$, and so on.

See also Young Tableau


References

Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.




© 1996-9 Eric W. Weisstein
1999-05-26