الگوریتم استینهوس-جانسون-تروتر
الگوریتم استینهوس-جانسون-تروتر الگوریتمی برای یافتن یک شیوه از قرار دادن 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_31 formula_32 formula_33 formula_34 formula_35 formula_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 است و همان‌طور که مشاهده می‌شود، دنباله تولید شده خاصیت کد گری را دارد.