Suffix permutation
Input:
σ, a permutation on [1,n]
Output:
the smallest word in the lexicographic order,
such that σ is its suffix (standard) permutation
Remark:
μ(i)=σ(σ-1(i)+1)


T
r
y

i
t


i] 1 2 3 4 5 6 7 8 9
σ[i]
σ-1[i]  n 
μ[i]

k←1
word[σ-1[1]]←Σ[1]
for i←1 to n-1
if μ(i) < μ(i+1) then
ri←'≤'
else
ri←'<'
k←k+1
word[σ-1[i+1]]←Σ[k]
return word
Reference
J.-P. Duval and A. Lefebvre
Words over an ordered alphabet and suffix permutations
RAIRO, Theoretical Informatics and Applications
10, pp. 249-259, 2002

Valid XHTML 1.0 Strict CSS Valide !