الگوریتم استینهوس-جانسون-تروتر کیست؟ توضیح بده.
الگوریتم استینهوس-جانسون-تروتر الگوریتمی برای یافتن یک شیوه از قرار دادن formula_1 جایگشت به طول formula_2 پشت سر یکدیگر است به طوری که هر جایگشت در این ترتیب با جابجا کردن دو عنصر مجاور در جایگشت قبلی‌اش به دست می‌آید.نام این الگوریتم بر اساس نام سه دانشمند ، سلمر مارتین جانسون و بوده‌است که تقریباً در زمانی نزدیک و به صورت مجزا از هم به این الگوریتم رسیده بودند.این الگوریتم برای ساختن ترتیبی از جایگشت‌ها در قرن ۱۷ام شناخته شد ورابرت سجدویکنیز به سرعت و سادگی این الگوریتم اشاره کرده‌است.دیدگاه از منظر گراف‌ها.ابن مسئله معادل یافتن یک مسیر هامیلتونی در یک گراف است.گراف را به این شکل می‌سازیم که برای هر یک از formula_3 جایگشت موجود یک راس قرار دهیم و سپس بین دو راس یال می‌گذاریم اگر با یک‌بار جابجا کردن دو عنصر مجاور بتوانیم یکی را به دیگری تبدیل کنیم، به این گراف، می‌گویند.مثلاً برای formula_4، جایگشت formula_5 به formula_6 یال دارد ولی بهformula_7 یال ندارد.اکنون اگر بتوانیم مسیری هامیلتونی در این گراف بیابیم، در این صورت ترتیب پیمایش گراف، همان تعریف مطلوب است. الگوریتم مورد بحث نیز یک مسیر معتبر ارائه می‌دهد.شیوه استقرایی در یافتن دنباله جایگشت‌ها.فرض کنید ترتیب در فرض استقرا formula_12 باشد. اکنون formula_13 را به این شکل تعریف می‌کنیم.اکنون ترتیب مطلوب برای جایگشت‌های به طول formula_16 را به این شکل می‌سازیم.formula_25برای مثال اگر برای formula_26 ترتیبی که فرض استقرا به ما می‌دهد، formula_27 باشد، در این‌صورت formula_28 و با ساختن formula_29ها، ترتیب مطلوب برای formula_30 به شکلformula_31formula_32formula_33formula_34formula_35formula_36خواهد بود.اثبات.اکنون درستی این دنباله را نشان می‌دهیم. دو عنصر متوالی از دنباله را در نظر می‌گیریم و نشان می‌دهیم که با یک عملیات جابجایی دو عنصر مجاور به یکدیگر تبدیل می‌شوند.فرض کنید دو جایگشت formula_37 و formula_38 را در نظر بگیریم دو حالت متصور است.برای اینکه اثبات کامل شود، لازم است نشان دهیم که جایگشت‌هایی که تولید می‌کنیم متمایزند. برای مثال formula_51 را در نظر بگیرید.الگوریتم.الگوریتمی که در سال ۱۹۶۳ منتشر شد، دقیقاً ترتیب بالا را تولید می‌کند ولی نیازی به حل مسئله برای مقادیر کمتر و تولید دنباله‌های کوچک‌تر ندارد و به شکلی مستقیم و با شروع از حالت اولیه همه جایگشت‌ها را تولید می‌کند.برای هر عدد در جایگشت یک جهت تعریف می‌شود که یا به‌راست است یا به‌چپ. در ابتدا جایگشت formula_59 است و همه جهت‌ها به چپ هستند.سپس در هر گام یک "mobile" تعریف می‌کنیم که به این صورت محاسبه می‌شود.هنگامی که دیگر "mobile" در جایگشت پیدا نشد، الگوریتم پایان می‌یابد و جایگشت‌های تولید شده در این میان، ترتیب مطلوب ما هستند.فرایند را برای formula_30 ببینید.formula_61"mobile" = ۳formula_62"mobile" = ۳formula_63"mobile" = ۲formula_64"mobile" = ۳formula_65"mobile" = ۳formula_66دیگری "mobile" وجود ندارد. الگوریتم پایان می‌یابد.مجدداً درستی الگوریتم با استقرا ثابت می‌شود.پیچیدگی زمانی الگوریتم.در این الگوریتم formula_67 جایگشت تولید می‌شود که برای هر کدام formula_68 هزینه برای یافتن "mobile" و جابجایی‌ها و برعکس‌کردن جهت‌ها لازم است؛ لذا هزینه الگوریتم formula_69 خواهد بود.ارتباط با کد گِرِی.کدگری در حالت کلی، ترتیبی از اعداد formula_2 رقمی در مبنایی دلخواه است، طوری که هر دو عدد مجاور در دقیقاً یک رقم تفاوت داشته باشند.اکنون به هر جایگشت یک دنباله متناظر می‌کنیم و ادعا می‌کنیم که دنباله‌های تولید شده توسط الگوریتمِ (که در هستند)، خاصیت کدگری را دارند.برای هر جایگشت یک دنباله formula_71، تعریف می‌کنیم که به این شکل حساب می‌شود.مثلاً دنباله مربوطه برای formula_75 برابر با formula_76 خواهد بود.ابتدا نشان می‌دهیم که برای جایگشت‌های متفاوت دنباله formula_71 نیز متفاوت خواهد بود.نشان می‌دهیم دنباله formula_78 جایگشتی یکتا تولید می‌کند.formula_79 را در نظر بگیرید، به سادگی می‌توان دریافت که در جایگشت جایگاه عدد formula_2، برابر با formula_81 است. اکنون عدد formula_2 را حذف کنید و به شکلی بازگشتی بقیه اعداد را به شکل یکتا در جایگاه‌هایشان قرار دهید، تا همه اعداد در جایگشت قرار گیرند، در تمامی مراحل فرایند یکتاست، پس تنها یک جایگشت خاص، دنباله متناظرش formula_71 است.می‌توان نشان داد ترتیبی که الگوریتم جانسون-تروتر تولید می‌کند دنباله‌های formula_71 می‌سازد که خاصیت کد گری را دارند، یعنی هر دو دنباله متوالی دقیقاً در یک رقم تفاوت دارند. (برای اثبات می‌توانید نشان دهید که اگر دو عضو متوالی از یک جایگشت را جابجا کنیم دقیقاً یکی از formula_72 تغییر می‌کند)برای formula_30 ،جایگشت‌هاformula_87 هستند که دنباله‌های متناظر با آن‌ها برابر باformula_88 استو همان‌طور که مشاهده می‌شود، دنباله تولید شده خاصیت کد گری را دارد.