سلب مسئولیت: روشی که در زیر توضیح داده شده است جهانی نیست، اما اغلب می تواند یک مشکل را حل کند یا به شما کمک کند تا راه حل مناسب را پیدا کنید.
اگر باید وجود جایگشت را در یک مشکل بررسی کنید، یا تعداد جایگشتهای منطبق یا چیزی مشابه را بیابید، باید از برنامهنویسی زیرمجموعه پویا استفاده کنید.
پارامتر اصلی یک بیت ماسک خواهد بود که نشان میدهد کدام عناصر قبلاً در جایگشت گنجانده شدهاند و کدامها نیستند. همچنین اغلب مورد نیاز یک پارامتر دوم است که نشان می دهد کدام عنصر در آخرین بار گنجانده شده است.
اغلب جایگشت ها را می توان در زمینه مسیرها در نمودارها مشاهده کرد. بر این اساس، اجازه دهید یک مثال کلاسیک را در نظر بگیریم - مسئله مسیر همیلتونی.
مسیر همیلتونی یک مسیر ساده است که دقیقاً یک بار از هر رأس نمودار می گذرد. می توان آن را به سادگی به عنوان یک جایگشت طول n نشان داد، که در آن n تعداد رئوس است. ترتیب درون این جایگشت نشان دهنده ترتیب پیمودن رئوس در این مسیر است.
برای بررسی وجود یک مسیر همیلتونی در نمودار، اجازه دهید دینامیک dp[mask][last] را شروع کنیم - آیا مسیر ساده ای وجود دارد که رئوس علامت گذاری شده در بیت ماسک را دور زده و به آخرین راس ختم شود.
مقادیر اولیه dp[2i][i] = true و بقیه false خواهد بود، به این معنی که همیشه یک مسیر خالی وجود دارد که از هر یک از رئوس شروع می شود.
با داشتن مقدار true در dp[mask][last]، به معنای "توسعه مسیر" به جلو حرکت خواهیم کرد. یعنی به دنبال اعداد رئوس هایی می گردیم که در ماسک با صفر مشخص شده اند (هنوز در راه از آنها بازدید نکرده ایم) و در عین حال به گونه ای هستند که یک یال از آخرین تا این راس وجود داشته باشد (مسیر باید توسط یک لبه موجود گسترش یابد). یعنی dp[mask | را انجام می دهیم 2k][k] = درست اگر dp[mask][last] = true AND mask & 2k = 0 (راس k هنوز بازدید نشده است) و آخرین لبه وجود دارد -> k.
در نهایت، اگر یک مقدار واقعی در dp برای پارامترهای بیت ماسک همه یکها و هر رأس آخر وجود داشته باشد، یک مسیر همیلتونی وجود دارد.