پیاده سازی ساده جایشگت در C++

پیاده سازی جایشگت در زبان های برنامه نویسی در نگاه اول می‌تواند بسیار سخت به نظر برسد(مخصوصاً اگه مثل من تازه کار باشید) ولی زمانی که کمی بیشتر راجع‌به این موضوع تحقیق کنید(به خصوص در منابع خارجی) به این نتیجه می‌رسید که پیاده‌سازی جایشگت بسیار ساده‌تر از آن چیزی است که فکر می‌کنید! در این مطلب قصد دارم که روش پیاده سازی جایشگت به صورت بازگشتی در زبان C++ را برایتان شرح بدهم. لازم به ذکر است این روش با پیاده سازی رایجی که از backtracking در سطح اینترنت مشاهده می‌کنید متفاوت است.

در حقیقت این روش را با مشاهده یک عکس پیاده سازی کردم و این‌که آیا این روش 100% درست است مطمئن نیستم.

احتمالاً در آینده الگوریتم "محاسبه جایشگت بعدی" را مورد بررسی قرار بدهم که هم ساده تر و هسریع تر است.

لطفاً اگر چیزی رو اشتباه نوشتم بگید بم تا منم یاد بگیریم، ممنون
این‌که این روش ناکارآمده درسته ولی من سعی کردم فقط درست کار کنه(حد اقل تا اونجایی که من تست کردم)

جایشگت چیست؟

قبل از اینکه سراغ پیاده سازی جایشگت در زبان C++ برویم، ابتدا اجازه بدهید که به صورت مختصر جایشگت را شرح بدهم. جایشگت در حقیقت یک روش برای تغییر موقعیت اعضای یک لیست است. این چیدمان می‌تواند خطی یا غیر خطی باشد. هنگام جایشگت یک لیست بهتر است که عنصر تکراری در لیست وجود نداشته باشد در غیر اینصورت لیست خروجی که شامل جایشگت‌ها است، شامل اعضای اضافی می‌باشد و فقط وقت بیشتری تلف شده است.

در تصویر زیر نمونه‌ای از جایگشت را مشاهده می‌کنید:

همانطور که در تصویر بالا مشاهده می‌کنید، در هر خط جای دو عنصر با هم عوض شده است. بنابراین جایشگت چیزی جز جا به جا کردن عنصر‌های یک لیست نیست. اگر دقت کرده باشید، اگر در حالت آخر جای هر عنصر را با عنصر دیگری عوض کنیم یک نتیجه تکراری به دست می‌آید که قبلاً در لیست وجود داشته است.

محاسبه تعداد جایگشت ها

برای اینکه بتوانیم حد اکثر تعدادی که یک لیست n عضوی می‌تواند جایگشت بشود را به دست بیاوریم باید از !n (بخوانید n فاکتوریل) استفاده کنیم. اگر بیشتر دقت کنید به این نتیجه می‌رسید که این فرمول کاملاً عاقلانه است!

تصور کنید که یک لیست داریم با اعضای (1,2,3,4,5) و قصد داریم که جایشگت‌های این لیست را به دست بیاوریم. اولاً، 1,2,3,4,5 خود یکی از جایشگت‌ها محسوب می‌شود. در مرحله بعد در ذهن خود پنج خانه خالی تصور کنید. در خانه اول می‌توانیم یکی از این 5 عضو را قرار دهیم و در نتیجه 4 عضو برای سایر خانه باقی می‌ماند. بعد از این کار باید یکی از آن 4 عضو را برای خانه بعدی انتخاب کنیم و بعد 3 عضو باقی می‌ماند و به همین ترتیب ادامه می‌دهیم تا یکی از جایگشت‌ها را محاسبه کنیم. از این حرف‌‌ها می‌توان به این نتیجه رسید که:

5 حالت برای خانه اول داریم که برای تغییر نیازمند 4 تغییر در خانه بعدی است. چرا گفتیم نیازمند؟ چون به ازای هر 4 بار تکرار در خانه دوم خانه اول یک بار تغییر می‌کند؛ و به ازای هر 3 بار تغییر خانه سوم خانه دوم یک بار تغییر می‌کند و به همین ترتیب.

انتخاب r از n

گاهی نیاز داریم که r خانه خالی را در نظر بگیریم و از یک لیست n عضوی(بدون اعضای تکراری)، اعضایی را انتخاب کنیم و در خانه‌های خالی جاگذاری کنیم و تمام جایگشت‌های آن‌ها را محاسبه کنیم. با این کار در حقیقت ما در حال انتخاب r عضو از n عضو برای محاسبه همه جایگشت هستیم. برای این‌که بتوانیم تعداد جایشگت های قابل ایجاد را در این حالت محاسبه کنیم ابتدا باید تعداد زیر مجموعه‌های r عضوی از n را به دست آورده و سپس باید به تعداد زیر مجموعه‌های به دست آمده !r را محاسبه کنیم؛ نتیجه هر محاسبه(!r) باید با قبلی جمع شود.

البته این را می‌توان به راحتی با فرمول زیر محاسبه کرد:

پیاده سازی به روش بازگشتی

یکی از روش‌هایی که می‌توانید جایشگت یا ترکیب یک لیست را محاسبه کنید استفاده از الگوریتم‌های بازگشتی است. این روش چند ضرر دارد که عبارتند از:

• ناکارمد بودن توابع بازگشتی(به دلیل سربار‌های اضافی ناشی از فراخوانی فراوان تابع)
• پیچیدگی بالا
• استفاده از ارسال با کپی در C++
• در این روش خود لیست وارد خروجی نمی‌شود
• در این روش یک عنصر با خودش تعویض می‌شود(هرچند با استفاده از شرط می‌توان جلوی این کار را گرفت)

اما به هر حال فهمیدن روش پیاده سازی بازگشتی می‌‌تواند به شما برای یادگیری بیشتر برنامه نویسی کمک کند. به طور کلی بنده سعی می‌کنم تا آنجا که می‌توانم انواع الگوریتم‌ها را امتحان کنم؛ این حقیقت که برنامه نویسی حرفه‌ای نیازمند تمرین مداوم و تبحر در طراحی الگوریتم ها است غیر قابل انکار است.(مخصوصاً تبحر در طراحی الگوریتم‌ها)

بهتر است که ابتدا تصویر زیر را مشاهده کنید و سپس با کد زیرش مقایسه کنید:

#include <iostream>
void PerCompu(std::string str, const size_t start) {
	if (start >= str.length()) return;
	std::string temp{ str };
	for (size_t i{ start }; i < str.length(); i++) {
		    str = temp;
			std::swap(str[start], str[i]);
			if(i!=start) std::cout << str << std::endl;
			PerCompu(str, start + 1);
	}
}

int main() {
	PerCompu(&quotABC&quot, 0);
	return 0; 
}

اگر در کد ایرادی پیدا کردید توی کامت‌ها بنویسید

توضیح کد های بالا

یک دید کلی

تابع PerCompu(گیر به اسمش ندید) برای محاسبه جایگشت‌های یک رشته(str) از موقعیت start است.

در مرحله اول ابتدا باید حالت توقف را بررسی کنیم تا با خطای Stack Overflow رو به رو نشویم(هر چند باید اندازه رشته هم محدود می‌کردیم ولی نکردیم!)

بسیار خب اجازه بدهید که از تصویر بالا یک دید جالب را ارائه بدهم. هر خط در تصویر بالا را یک حلقه تکرار در نظر بگیرید و هر مستطیل سه عضوی را یک فراخوانی تابع در نظر بگیرید.

شرح کد

در کد، قبل از اینکه وارد حلقه for بشویم ابتدا یک کپی از رشته دریافتی را ذخیره می‌کنیم تا بعد از جا به جا کردن اعضای رشته، رشته اصلی دریافتی را به حالت اولیه برگردانیم. دلیل این کار این است که اگر قرار باشد تغییر ها روی رشته اصلی اعمال شود، در اولین فراخوانی تابع و در آخرین شمارش حلقه تکرار به جای اینکه رشته CBA را تحویل بگیریم، رشته CAB را تحویل می‌گیریم. دلیل این اتفاق نیز این است که در حالت قبلی(قبل از این‌که رشته CAB را تحویل بگیریم) رشته BAC را داشتیم و i برابر با 2 بود و در این حالت که start برابر 0 است(زیرا حلقه تکرار در اولین فراخوانی تابع را در نظر گرفتیم)، C را با B تعویض می‌کنیم!

ما با استفاده از حلقه for شروع کردیم و سپس و تا انتهای لیست شروع به شمارش کردیم. در هر شمارش ابتدا temp را در str قرار دادیم(می‌توانست در آخر هم باشد) سپس خانه شماره i را با خانه‌ای با اندیس start عوض کردیم.

در مرحله بعد برسی می‌کنیم که اگر i مخالف start بود، رشته را در خروجی چاپ کن. دلیل این شرط این است که اگر i و start با هم برابر باشند در حقیقت فقط یک عنصر را با خودش تعویض کردیم!

در مرحله بعد برای این‌که خانه ها از 0 تا start ثابت باشند تابع را با یک کپی از رشته تغییر یافته و با start+1 مجدداً فراخوانی می‌کنیم. این یعنی از فراخوانی بعدی به جای شروع از 0 از start+1 شروع می‌کنیم و در نتیجه از 0 تا start+1 ثابت است.

منبع 1: geeksforgeeks

منبع 2: جایگشت - ویکی‌پدیا، دانشنامهٔ آزاد (wikipedia.org)