تعداد نا به جایی های جایگشت $\pi= \langle \pi _1, \pi_2, ...,\pi_n \rangle$ به طول $n$ برابر تعداد اندیس های $i$ و $j$ است که $i \lt j$ و $\pi_i \gt \pi_j$. برای مثال تعداد نابه جایی های جایگشت $ \langle1,3,4,2 \rangle $ برابر ۲ و تعداد نا به جایی های جایگشت $ \langle3,2,4,1 \rangle$ برابر ۴ است. تعداد نابه جایی های جایگشت $\pi$ را با $f(\pi)$ نشان می دهیم.

۱۰۰ کارت داریم که پشت هر کارت یکی از اعداد ۱ تا ۱۰۰ نوشته شده است. به بیان دیگر اعداد نوشته شده پشت کارت ها تشکیل یک جایگشت می دهند. هم چنین یک ماشین با ۱۰۰ جایگاه مخصوص کارت با شماره های ۱ تا ۱۰۰ در اختیار داریم. کارت ها را با ترتیب دلخواه در این ۱۰۰ جایگاه طوری قرار می دهیم که در هر جایگاه دقیقا یک کارت قرار گیرد. کارت ها طوری قرار داده شده اند که عدد نوشته شده پشت آن ها را نمی بینیم. دقت کنید که هر وضعیت قرار گرفتن کارت ها در ماشین مشخص کننده ی یک جایگشت $\pi$ است. جایگشت $\pi$ به این صورت مشخص می شود که عدد نوشته شده بر روی کارت موجود در جایگاه $i$ ماشین نشان دهنده ی $\pi_ i$ است. وضعیت ایده آل وضعیتی است که کارت با عدد $i$ در جایگاه به شماره $i$ قرار گیرد. هدف رسیدن به وضعیت ایده آل است. برای رسیدن به این هدف می توان در هر مرحله به صورت زیر عمل کرد:

• دو عدد $i$ و $j$ را به ماشین می دهیم. فرض کنید وضعیت فعلی ماشین مشخص کننده ی جایگشت $\pi$ است. ماشین کارت های موجود در جایگاه $i$ و $j$ را با هم جابه جا می کند. فرض کنید وضعیت ماشین در حالت جدید مشخص کننده ی جایگشت $\acute{\pi}$ است. ماشین علاوه بر جابه جایی کارت های موجود در جایگاه $i$ و $j$ مقدار $f(\acute{ \pi})- f (\pi)$ را نیز در خروجی نشان می دهد.

روشی ارائه دهید که برای هرگونه وضعیت اولیه قرار گرفتن کارت ها در ماشین، آن ها را در ۱۹۸ مرحله به وضعیت ایده آل تبدیل کند.

• سوال بعد
• سوال قبل