تعداد نا به جایی های جایگشت $\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 $ برابر 2 و تعداد نا به جایی‌های جایگشت $ \langle3,2,4,1 \rangle$ برابر 4 است. تعداد نابه جایی‌های جایگشت $\pi$ را با $f(\pi)$ نشان می‌دهیم.

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

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

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