Sorting and generating reduced words

摘要

We introduce a partial order on the set of all reduced words of a given permutation ω, called directed-braid poset of ω. This poset enables us to produce two algorithms: One is a sorting algorithm applied to any reduced word of ω and aims to obtain the natural word (i.e. lexicographically largest reduced word); the other one is a generation algorithm applied to the natural word and returns the set of all reduced words of ω.