جایگشت های n تایی n شیء

با سلامی دوباره خدمت همه دوستان

این بار برنامه چاپ جایگشت های n شی رو بصورت یک تابع بازگشتی براتون نوشتم. همونطور که خیلی از شما دوستان می دونید ، جایگشت های n تایی n شی یعنی حالات مختلف قرار گیری n شی در کنار هم در یک صف . به عنوان مثال جایگشت های سه تایی اشیاء a و b و c را به شکل زیر می توان نشان داد:

abc , acb , bac , bca , cab , cba

من برنامه ای نوشتم که عدد  n رو از ورودی خوانده و تمامی حالات قرار گیری اعداد 1 تا n رو چاپ کنه. برای نوشتن این برنامه بصورت یک تابع بازگشتی ، باید دقت کرد حالات قرار گیری n شی برابر مجموع حالات قرار گیری یک شی خاص در کنار حالات قرار گیری n-1 شی دیگر است. به عنوان مثال می خواهیم حالات قرار گیری اعداد 1 و 2 و 3 که به ترتیب در یک آرایه قرار دارند را چاپ کنیم ، برای اینکار ، ابتدا 1 را که اولین عنصر آرایه است ، عدد خاص در نظر گرفته و تمامی حالات قرارگیری 2 و 3 در کنار هم را می نویسیم ، سپس 1 را در کنار آنها قرار می دهیم:

23 => 123

32 => 132

سپس جای عدد 2 را با عدد یک عوض کرده و اینبار عدد 2 را که اولین عنصر آرایه است ، به عنوان عدد خاص در نظر می گیریم. حال تمامی حالات قرار گیری اعداد 1 و 3 که سایر عناصر آرایه هستند را نوشته و عدد 2 را در کنار آنها قرار می دهیم:

13 => 213

31 => 231

سپس آرایه را به شکل اول در می آوریم ( یعنی عدد 1 را در اولین عنصر قرار می دهیم ) و سپس عدد 3 را به اول آرایه منتقل کرده و عدد خاص در نظر می گیریم و پس از نوشتن تمامی حالات قرار گیری اعداد 1 و 2 در کنار هم ، عدد 3 را در ابتدای آنها می نویسیم:

12 => 312

21 => 321

برنامه ای که برای چاپ کردن حالات مختلف قرار گیری اعداد 1 تا n نوشتم ، از الگوریتم بالا پیروی می کند. این برنامه از 3 تابع Jaygasht ، Set2 و SetAndPrint تشکیل شده است. لازم به ذکر است این برنامه در یک سیستم با امکاناتی در حد متوسط ، تمامی حالات کنار هم قرار گرفتن اعداد 1 تا 8 که برابر 40320 حالت مختلف است را در زمانی بین 35 تا 40 ثانیه و حالات مختلف قرارگیری اعداد 1 تا 9 در کنار هم ( 362880 حالت ) را در حدود 380 ثانبه چاپ می کند ، ولی اگر این کار بدون استفاده از توابع Set2 و SetAndPrint انجام شود ، این زمان بیش از 600 برابر می شود!

 دانلود برنامه نمایش جایگشت های n شی به همراه فایل اجرایی

یک نمونه از کاربرد های این برنامه را در پست هشتاد و یکم ملاحظه کنید.