برای مرتب‌سازی، عمل «ابرجابه‌جایی» را چنین تعریف می‌کنیم. در هر ابرجابه‌جایی، یک زیررشتهی دلخواه از دنباله‌ی داده‌شده را معکوس می‌کنیم. برای مثال دنباله‌ی $\left< 1,4,3,2,5\right>$ با یک ابرجابه‌جایی مرتب می‌‌شود. کافی است زیررشتهی $\left<4,3,2\right>$ را معکوس کنیم. ولی برای مرتب‌سازی دنباله‌ی $\left<4,2,3,1\right>$ دو ابرجابه‌جایی نیاز داریم. ابتدا کل دنباله را معکوس می‌کنیم تا به $\left<1,3,2,4\right>$ برسیم. سپس زیررشتهی $\left<3,2\right>$ را معکوس می‌کنیم. حداقل تعداد ابرجابه‌جایی که برای مرتب‌سازی هر دنباله‌ی دلخواه به طول ۴ کافی است، چند است؟
راهنمایی
فرض کنید اعداد $1$ تا $i$ در جایگاه درست خود قرار دارند. آیا می‌توان عدد $i+1$ را در جایگاه درستش قرار داد به طوری که در نهایت، اعداد $1$ تا $i$ نیز همچنان در جایگاه درست خود قرار داشته باشند؟
پاسخ
گزینه‌ی ۲ درست است.
با حالت‌گیری و رسیدن به دنباله‌ی $\left<3,1,4,2\right>$ جواب به دست می‌آید.