الگوریتم استینهوس-جانسون-تروتر

الگوریتم استینهوس-جانسون-تروتر (به انگلیسی: Steinhaus–Johnson–Trotter algorithm) الگوریتمی برای یافتن یک شیوه از قرار دادن $n!$ جایگشت به طول $n$ پشت سر یکدیگر است به طوری که هر جایگشت در این ترتیب با جابجا کردن دو عنصر مجاور در جایگشت قبلی‌اش به دست می‌آید.
نام این الگوریتم بر اساس نام سه دانشمند هوگو استینهوس، سلمر مارتین جانسون و هیل‌فریمن تروتر بوده‌است که تقریباً در زمانی نزدیک و به صورت مجزا از هم به این الگوریتم رسیده بودند.

این الگوریتم برای ساختن ترتیبی از جایگشت‌ها در قرن ۱۷ام شناخته شد و رابرت سجدویک^[۱] نیز به سرعت و سادگی این الگوریتم اشاره کرده‌است.

دیدگاه از منظر گراف‌ها[ویرایش]

ابن مسئله معادل یافتن یک مسیر هامیلتونی در یک گراف است.
گراف را به این شکل می‌سازیم که برای هر یک از $n!$ جایگشت موجود یک راس قرار دهیم و سپس بین دو راس یال می‌گذاریم اگر با یک‌بار جابجا کردن دو عنصر مجاور بتوانیم یکی را به دیگری تبدیل کنیم، به این گراف، گراف جایگشت‌ها می‌گویند.
مثلاً برای $n=4$ ، جایگشت $<1,2,3,4>$ به $<1,3,2,4>$ یال دارد ولی به $<3,2,1,4>$ یال ندارد.
اکنون اگر بتوانیم مسیری هامیلتونی در این گراف بیابیم، در این صورت ترتیب پیمایش گراف، همان تعریف مطلوب است. الگوریتم مورد بحث نیز یک مسیر معتبر ارائه می‌دهد.

شیوه استقرایی در یافتن دنباله جایگشت‌ها[ویرایش]

برای $n=1$ که مسئله واضح است و تک جایگشت $<1>$ ترتیب مطلوب است.
اکنون فرض می‌کنیم می‌توانیم ترتیبی از $n!$ جایگشت بیابیم و ترتیبی برای جایگشت‌های به طول $n+1$ پیدا می‌کنیم.

فرض کنید ترتیب در فرض استقرا $P_{1},P_{2},...,P_{n!}$ باشد. اکنون $Q_{i,j}$ را به این شکل تعریف می‌کنیم.

چنان‌چه $i$ زوج باشد، $Q_{i,j}$ جایگشتی است که از اضافه کردن $n+1$ به جایگاه $j$ ام $P_{i}$ به دست می‌آید.
چنانچه $i$ فرد باشد، $Q_{i,j}$ جایگشتی است که از اضافه کردن $n+1$ به جایگاه $n+2-j$ جایگشت $P_{i}$ به دست می‌آید.

اکنون ترتیب مطلوب برای جایگشت‌های به طول $n+1$ را به این شکل می‌سازیم. $Q_{1,1},Q_{1,2},...,Q_{1,n+1},...,Q_{i,1},Q_{i,2},...,Q_{i,n+1},...,Q_{n!,1},Q_{n!,2},...,Q_{n!,n+1}$

برای مثال اگر برای $n=2$ ترتیبی که فرض استقرا به ما می‌دهد، $<1,2>,<2,1>$ باشد، در این‌صورت $P_{1}=<1,2>,P_{2}=<2,1>$ و با ساختن $Q_{i,j}$ ها، ترتیب مطلوب برای $n=3$ به شکل
$<1,2,3>$
$<1,3,2>$
$<3,1,2>$
$<3,2,1>$
$<2,3,1>$
$<2,1,3>$
خواهد بود.

اثبات[ویرایش]

اکنون درستی این دنباله را نشان می‌دهیم. دو عنصر متوالی از دنباله را در نظر می‌گیریم و نشان می‌دهیم که با یک عملیات جابجایی دو عنصر مجاور به یکدیگر تبدیل می‌شوند. فرض کنید دو جایگشت $k$ و $k+1$ را در نظر بگیریم دو حالت متصور است.

اگر این دو جایگشت به شکل $Q_{i,j},Q_{i,j+1}$ باشند، در این‌صورت اگر $n+1$ را از دو جایگشت حذف کنیم جایگشت یکسان $P_{i}$ به دست می‌آید؛ و دو جایگشتی که ما بررسی می‌کنیم از اضافه کردن $n+1$ به دو جایگاه متوالی از $P_{i}$ به دست می‌آید. پس با جابجا کردن $n+1$ با عنصر کنارش از جایگشت $k$ به جایگشت $k+1$ می‌رسیم.
اگر اگر این دو جایگشت به شکل $Q_{i,n+1},Q_{i+1,1}$ باشد، در این صورت در تعریف ما، در هر دو این جایگشت‌ها $n+1$ در یک سمت جایگشت است و بقیه جایگشت (بدون در نظر گرفتن $n+1$ ) جایگشت‌های $P_{i},P_{i+1}$ هستند که طبق فرض استقرا با یک عملیات به یکدیگر تبدیل می‌شوند.

برای اینکه اثبات کامل شود، لازم است نشان دهیم که جایگشت‌هایی که تولید می‌کنیم متمایزند. برای مثال $Q_{i_{1},j_{1}},Q_{i_{2},j_{2}}$ را در نظر بگیرید.

اگر $i_{1}=i_{2}$ در این‌صورت چون $j_{1}\neq j_{2}$ مکان $n+1$ در این دو جایگشت تفاوت می‌کند لذا دو جایگشت متفاوتند.
اگر $i_{1}\neq i_{2}$ ، در این‌صورت جایگشت‌هایی که با حذف $n+1$ به دست می‌آید $P_{i_{1}},P_{i_{2}}$ هستند که طبق فرض استقرا با یکدیگر متفاوتند لذا دو جایگشت $Q_{i_{1},j_{1}},Q_{i_{2},j_{2}}$ نیز متفاوتند.

الگوریتم[ویرایش]

الگوریتمی که در سال ۱۹۶۳ منتشر شد، دقیقاً ترتیب بالا را تولید می‌کند ولی نیازی به حل مسئله برای مقادیر کمتر و تولید دنباله‌های کوچک‌تر ندارد و به شکلی مستقیم و با شروع از حالت اولیه همه جایگشت‌ها را تولید می‌کند.^[۲]^[۱]^[۳]
برای هر عدد در جایگشت یک جهت تعریف می‌شود که یا به‌راست است یا به‌چپ. در ابتدا جایگشت $<1,2,...,n>$ است و همه جهت‌ها به چپ هستند.
سپس در هر گام یک mobile تعریف می‌کنیم که به این صورت محاسبه می‌شود.

بزرگترین عددی است که از عدد سمت جهتش، بزرگتر است (یعنی برای اعدادی که جهتشان به‌چپ است آن را با عدد سمت چپش و برای اعدادی که جهت‌شان به‌راست است آن را با عدد سمت راستش مقایسه می‌کنیم) در میان اعدادی که از عدد مربوطه‌شان بزرگترند، بزرگ‌ترین را در نظر می‌گیریم و این عدد را mobile می‌نامیم.
سپس این عدد را با عددی که جهتش اشاره می‌کند (یعنی همان عددی که با آن مقایسه شده‌است) جابجا می‌کنیم.
در گام آخر، جهت همه اعدادی که از mobile بزرگترند را برعکس می‌کنیم. یعنی از به‌چپ به به‌راست و بالعکس.

هنگامی که دیگر mobile در جایگشت پیدا نشد، الگوریتم پایان می‌یابد و جایگشت‌های تولید شده در این میان، ترتیب مطلوب ما هستند.

فرایند را برای $n=3$ ببینید.
$<1,<2,<3$
mobile = ۳

$<1,<3,<2$
mobile = ۳

$<3,<1,<2$
mobile = ۲

$>3,<2,<1$
mobile = ۳

$<2,>3,<1$
mobile = ۳

$<2,<1,>3$
دیگری mobile وجود ندارد. الگوریتم پایان می‌یابد.
مجدداً درستی الگوریتم با استقرا ثابت می‌شود.

پیچیدگی زمانی الگوریتم[ویرایش]

در این الگوریتم $\theta (n!)$ جایگشت تولید می‌شود که برای هر کدام $\theta (n)$ هزینه برای یافتن mobile و جابجایی‌ها و برعکس‌کردن جهت‌ها لازم است؛ لذا هزینه الگوریتم $\theta (n.n!)$ خواهد بود.

ارتباط با کد گِرِی[ویرایش]

کدگری در حالت کلی، ترتیبی از اعداد $n$ رقمی در مبنایی دلخواه است، طوری که هر دو عدد مجاور در دقیقاً یک رقم تفاوت داشته باشند.
اکنون به هر جایگشت یک دنباله متناظر می‌کنیم و ادعا می‌کنیم که دنباله‌های تولید شده توسط الگوریتمِ (که در مبنای فاکتوریل هستند)، خاصیت کدگری را دارند.
برای هر جایگشت یک دنباله $C$ ، تعریف می‌کنیم که به این شکل حساب می‌شود.

$c_{i}$ را برابر تعداد اعداد کوچکتر از $i$ ، در سمت راست $i$ در جایگشت تعریف می‌کنیم.

مثلاً دنباله مربوطه برای $<3,1,2,5,4>$ برابر با $C=<0,0,2,0,1>$ خواهد بود.
ابتدا نشان می‌دهیم که برای جایگشت‌های متفاوت دنباله $C$ نیز متفاوت خواهد بود.
نشان می‌دهیم دنباله $<c_{1},c_{2},...,c_{n}>$ جایگشتی یکتا تولید می‌کند.
$c_{n}$ را در نظر بگیرید، به سادگی می‌توان دریافت که در جایگشت جایگاه عدد $n$ ، برابر با $n-c_{n}$ است. اکنون عدد $n$ را حذف کنید و به شکلی بازگشتی بقیه اعداد را به شکل یکتا در جایگاه‌هایشان قرار دهید، تا همه اعداد در جایگشت قرار گیرند، در تمامی مراحل فرایند یکتاست، پس تنها یک جایگشت خاص، دنباله متناظرش $C$ است.

می‌توان نشان داد ترتیبی که الگوریتم جانسون-تروتر تولید می‌کند دنباله‌های $C$ می‌سازد که خاصیت کد گری را دارند، یعنی هر دو دنباله متوالی دقیقاً در یک رقم تفاوت دارند. (برای اثبات می‌توانید نشان دهید که اگر دو عضو متوالی از یک جایگشت را جابجا کنیم دقیقاً یکی از $c_{i}$ تغییر می‌کند)^[۴]^[۵]
برای $n=3$ ، جایگشت‌ها
$<1,2,3>,<1,3,2>,<3,1,2>,<3,2,1>,<2,3,1>,<2,1,3>$ هستند که دنباله‌های متناظر با آن‌ها برابر با
$<0,0,0>,<0,0,1>,<0,0,2>,<0,1,2>,<0,1,1>,<0,1,0>$ است و همان‌طور که مشاهده می‌شود، دنباله تولید شده خاصیت کد گری را دارد.