موضوع مقاله: الگوریتم استینهوس-جانسون-تروتر | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم استینهوس-جانسون-تروتر | مقدمه: الگوریتم استینهوس-جانسون-تروتر الگوریتمی برای یافتن یک شیوه از قرار دادن جایگشت به طول پشت سر یکدیگر است به طوری که هر جایگشت در این ترتیب با جابجا کردن دو عنصر مجاور در جایگشت قبلی‌اش به دست می‌آید. | ## بخش 1: الگوریتم استینهوس-جانسون-تروتر | نام این الگوریتم بر اساس نام سه دانشمند هوگو استینهوس، سلمر مارتین جانسون و هیل‌فریمن تروتر بوده‌است که تقریباً در زمانی نزدیک و به صورت مجزا از هم به این الگوریتم رسیده بودند. این الگوریتم برای ساختن ترتیبی از جایگشت‌ها در قرن ۱۷ام شناخته شد و رابرت سجدویک. اکنون اگر بتوانیم مسیری هامیلتونی در این گراف بیابیم، در این صورت ترتیب پیمایش گراف، همان تعریف مطلوب است. شیوه استقرایی در یافتن دنباله جایگشت‌ها برای که مسئله واضح است و تک جایگشت ترتیب مطلوب است. اکنون فرض می‌کنیم می‌توانیم ترتیبی از جایگشت بیابیم و ترتیبی برای جایگشت‌های به طول پیدا می‌کنیم. برای مثال اگر برای ترتیبی که فرض استقرا به ما می‌دهد، باشد، در این‌صورت و با ساختن ها، ترتیب مطلوب برای به شکل خواهد بود. دو عنصر متوالی از دنباله را در نظر می‌گیریم و نشان می‌دهیم که با یک عملیات جابجایی دو عنصر مجاور به یکدیگر تبدیل می‌شوند. | ## بخش 2: الگوریتم استینهوس-جانسون-تروتر | اگر این دو جایگشت به شکل باشند، در این‌صورت اگر را از دو جایگشت حذف کنیم جایگشت یکسان به دست می‌آید؛ و دو جایگشتی که ما بررسی می‌کنیم از اضافه کردن به دو جایگاه متوالی از به دست می‌آید. اگر اگر این دو جایگشت به شکل باشد، در این صورت در تعریف ما، در هر دو این جایگشت‌ها در یک سمت جایگشت است و بقیه جایگشت (بدون در نظر گرفتن ) جایگشت‌های هستند که طبق فرض استقرا با یک عملیات به یکدیگر تبدیل می‌شوند. برای اینکه اثبات کامل شود، لازم است نشان دهیم که جایگشت‌هایی که تولید می‌کنیم متمایزند. اگر ، در این‌صورت جایگشت‌هایی که با حذف به دست می‌آید هستند که طبق فرض استقرا با یکدیگر متفاوتند لذا دو جایگشت نیز متفاوتند. الگوریتم الگوریتمی که در سال ۱۹۶۳ منتشر شد، دقیقاً ترتیب بالا را تولید می‌کند ولی نیازی به حل مسئله برای مقادیر کمتر و تولید دنباله‌های کوچک‌تر ندارد و به شکلی مستقیم و با شروع از حالت اولیه همه جایگشت‌ها را تولید می‌کند. بزرگترین عددی است که از عدد سمت جهتش، بزرگتر است (یعنی برای اعدادی که جهتشان به‌چپ است آن را با عدد سمت چپش و برای اعدادی که جهت‌شان به‌راست است آن را با عدد سمت راستش مقایسه می‌کنیم) در میان اعدادی که از عدد مربوطه‌شان بزرگترند، بزرگ‌ترین را در نظر می‌گیریم و این عدد را mobile می‌نامیم. سپس این عدد را با عددی که جهتش اشاره می‌کند (یعنی همان عددی که با آن مقایسه شده‌است) جابجا می‌کنیم. | ## بخش 3: الگوریتم استینهوس-جانسون-تروتر | هنگامی که دیگر mobile در جایگشت پیدا نشد، الگوریتم پایان می‌یابد و جایگشت‌های تولید شده در این میان، ترتیب مطلوب ما هستند. پیچیدگی زمانی الگوریتم در این الگوریتم جایگشت تولید می‌شود که برای هر کدام هزینه برای یافتن mobile و جابجایی‌ها و برعکس‌کردن جهت‌ها لازم است؛ لذا هزینه الگوریتم خواهد بود. ارتباط با کد گِرِی کدگری در حالت کلی، ترتیبی از اعداد رقمی در مبنایی دلخواه است، طوری که هر دو عدد مجاور در دقیقاً یک رقم تفاوت داشته باشند. اکنون به هر جایگشت یک دنباله متناظر می‌کنیم و ادعا می‌کنیم که دنباله‌های تولید شده توسط الگوریتمِ (که در مبنای فاکتوریل هستند)، خاصیت کدگری را دارند. را در نظر بگیرید، به سادگی می‌توان دریافت که در جایگشت جایگاه عدد ، برابر با است. اکنون عدد را حذف کنید و به شکلی بازگشتی بقیه اعداد را به شکل یکتا در جایگاه‌هایشان قرار دهید، تا همه اعداد در جایگشت قرار گیرند، در تمامی مراحل فرایند یکتاست، پس تنها یک جایگشت خاص، دنباله متناظرش است. می‌توان نشان داد ترتیبی که الگوریتم جانسون-تروتر تولید می‌کند دنباله‌های می‌سازد که خاصیت کد گری را دارند، یعنی هر دو دنباله متوالی دقیقاً در یک رقم تفاوت دارند. | ## جمع‌بندی | (برای اثبات می‌توانید نشان دهید که اگر دو عضو متوالی از یک جایگشت را جابجا کنیم دقیقاً یکی از تغییر می‌کند) برای ، جایگشت‌ها هستند که دنباله‌های متناظر با آن‌ها برابر با است و همان‌طور که مشاهده می‌شود، دنباله تولید شده خاصیت کد گری را دارد.