در سوال قبل به ازای هر جایگشت مطلوب، کمینهی تعداد مراحل لازم برای رسیدن به جایگشت مرتب شده (از کوچک به بزرگ) را در نظر بگیرید. در میان این مقادیر، بیشینه چیست؟
راهنمایی
دقت کنید برخی جایگشتها به طبع روش حل بخش قبل، نیاز به فرد عمل برای تبدیل شدن به جایگشت مرتب شده دارند و برخی دیگر نیاز به زوج عمل.
راهنمایی
کافی است پس از توجه به زوجیت تعداد گامهای صورت گرفته، کاری کنید که عدد ۱ به ابتدای جایگشت انتقال یابد.
راهنمایی
نشان دهید میتوان کار فوق را در حداکثر دو مرحله انجام داد.
پاسخ
گزینهی ۱ درست است.
ترتیب دوری هر جایگشت مطلوب، مرتّب شده یا وارون آن است (طبق سوال قبل). اگر جایگشت مرتّب شده بود، ابتدا با یک حرکت ترتیب آن را وارون میکنیم. حال با یک حرکت میتوانیم نقطهی شروع جایگشت را برابر ۱ کنیم و جایگشت مرتّب میشود.