برنامه چاپ جایگشت های رشته – به زبان ساده

«جایگشت» (Permutation) در ریاضیات، کار سازمان‌دهی اعضای یک مجموعه در توالی یا ترتیب‌ها است. اگر مجموعه خود مرتب باشد، باز سازمان‌دهی (مرتب‌سازی مجدد) عناصر آن با اهداف گوناگون انجام می‌شود که به این فرایند، جایگشت می‌گویند. جایگشت با «ترکیب» (Combinations) که انتخاب از میان اعضای مجموعه، صرف نظر از ترتیب آن‌ها است، به طور کامل تفاوت دارد. یک رشته با طول n، دارای !n جایگشت است. در این مطلب، روش نوشتن برنامه چاپ جایگشت های رشته تشریح شده است. در ادامه، جایگشت‌های گوناگون رشته ABC را می‌توان مشاهده کرد.

ABC ACB BAC BCA CBA CAB

در تصویر زیر، راهکار مورد استفاده برای به دست آوردن جایگشت‌های مختلف رشته ABC با استفاده از روش «پَس‌گرد» (Backtracking) قابل مشاهده است. در ادامه، پیاده‌سازی روش مذکور با استفاده از زبان‌های برنامه‌نویسی گوناگون، شامل «سی‌پلاس‌پلاس» (++C ،(C، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و «پی‌اچ‌پی» (PHP) انجام شده است.

برنامه چاپ جایگشت های رشته در ++C

برنامه چاپ جایگشت های رشته در C

برنامه چاپ جایگشت های رشته در جاوا

برنامه چاپ جایگشت های رشته در پایتون

برنامه چاپ جایگشت های رشته در #C

برنامه چاپ جایگشت های رشته در PHP

خروجی

خروجی قطعه کدهای بالا، برای رشته ABC، در ادامه ارائه شده است.

ABC
ACB
BAC
BCA
CBA
CAB

پیچیدگی زمانی الگوریتم پس‌گرد مورد استفاده برای حل این مساله، از درجه (!O(n*n است. توجه به این نکته لازم است که !n جایگشت وجود دارد و نیازمند زمان (O(n برای چاپ کردن جایگشت است.

راهکار بالا، در صورت وجود کاراکتر تکراری در رشته ورودی، جایگشت‌های تکراری را در خروجی چاپ می‌کند. می‌توان الگوریتم را به نوعی بهبود بخشید که تنها جایگشت‌های متمایز را چاپ کند؛ حتی در صورتی که تکرار در رشته ورودی وجود داشته باشد.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش برنامه‌نویسی C++‎
• مجموعه آموزش‌های ریاضیات
• کد جمع کردن چند جمله‌ای ها — راهنمای کاربردی
• برنامه ضرب چند جمله‌ای‌ها — راهنمای کاربردی

^^