آموزش ++c, زبان c++

جایگشت حروف در سی پلاس پلاس (Combinations in Cpp)

جایگشت حروف در سی پلاس پلاس

در این جلسه تیم کدگیت را با آموزش جایگشت حروف در سی پلاس پلاس همراهی کنید. پیش نیاز این آموزش شامل موارد زیر است:

  1. آشنایی با توابع
  2. آشنایی با For
  3. آشنایی با روش بازگشتی
  4. آشنایی با if

ترکیب یا جایگشت

ترکیب در حوزه ریاضیات مفهوم نزدیکی با جایگشت دارد. یک جایگشت (تبدیل) تعداد حالات چیده شدن تعدادی معین از اعضای یک مجموعه در مکان هایی معین است، در حالی که یک ترکیب تعداد حالات انتخاب تعدادی معین از اعضای یک مجموعه است. ترکیب را با نماد C(n,r) نمایش میدهند. تصویر زیر نماد دیگر جایگشت است

جایگشت حروف در جاوا

می خواهیم از مجموعه {a1,a2, …… an} که تمامی اعضایش متمایزند یک زیر مجموعه r عضوی انتخاب کنیم. برای این کار ابتدا سعی می کنیم تا r عضو از این مجموعه را در یک ردیف به دنبال هم قرار دهیم که این همان جایگشت r تایی از بین n عضو است که بنابر محاسبه جایگشت ها تعداد حالات انجام این کار برابر با p(n,r)  با کمی دقت می‌توان دریافت که در حین این عملیات ما هم r عضو از بین n عضو مجموعه اصلی انتخاب کردیم و هم آنها را در یک ردیف چیدیم، در حالی که برای به دست آوردن تعداد ترکیب r تایی از بین n عضو تنها باید r عضو انتخاب کرده و بخش دوم یعنی چیدن آنها در یک ردیف را انجام ندهیم. برای رسیدن به این مطلوب باید در نظر داشت که هر r عضو {a1,a2, …… an} به تعداد !r جایگشت ایجاد می‌کنند که در ترکیب این جایگشت‌ها حالات تکراری محسوب می‌شوند در نتیجه باید پاسخ بر !r تقسیم شود(ویکیپدیا):

جایگشت حروف در جاوا
جایگشت حروف در جاوا

جایگشت حروف در سی پلاس پلاس

برای محاسبه جایگشت حروف در جاوا ابتدا یک توضیح کوتاهی درباره جایگشت حروف می‌دهیم. منظور از جایگشت حروف این است که فرضا ما حرف aوbوc را داشته باشیم جایگشت این سه حرف برابر است با :

a

ab

abc

ac

b

bc

c

کدی که ما خواهیم نوشت خروجی آن به صورت بالا است.

کد جایگشت حروف در سی پلاس پلاس

با آشنا شدن جایگشت و جایگشت حروف نوبت به کد رسیده است. برای کد جایگشت حروف در سی پلاس پلاس از یک روش با دو نوع پیاده سازی مختلف استفاده کردیم. کد جایگشت در سی پلاس پلاس به صورت زیر است:

void comb1(string prefix, string s) {

    if (s.size() > 0) {

         cout << prefix + s.substr(0, 1) << endl;

         string temp = prefix + s.substr(0, 1);

         string temp2 = s.substr(1, s.size());

         comb1(temp, temp2);

         comb1(prefix, temp2);

    }

}

void comb1(string s) {

    comb1("", s);

}

void comb2(string prefix, string s) {

    cout << prefix << endl;

    for (int i = 0; i < s.length(); i++) {

         comb2(prefix + s.at(i), s.substr(i + 1, s.size()));

    }

}

void comb2(string s) {

    comb2("", s);

}

کد بالا شامل متد های زیر است:

  1. Comb1: این تابع دو بار overload شده است. یکی برای استفاده و دومی برای پیاده سازی جایگشت حروف در سی پلاس پلاس.
  2. Comb2: این متد دو بار overload شده است. یکی برای استفاده و دومی برای پیاده سازی جایگشت حروف در سی پلاس پلاس.

همانطور که میبینید دو تابع comb1 و comb2 یک کار را میکنند. به طور کلی کاری که هر یک انجام میدهند این است که یکی یکی حروف را کنار میچینند و به صورت بازگشتی یک حرف را در هر مرحله حذف میکنند(پیشنهاد میشود یک بار برنامه را دیباگ کنید تا به طور کامل روند را متوجه شوید).

تست جایگشت حروف در جاوا

برای تست کدهای بالا، کد main زیر را بزنید:

int main() {

    int n = 5;

    string alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

    string elements = alphabet.substr(0, n);

    comb1(elements);

    cout << endl;

    comb2(elements);

    cout << endl;

    return 0;

}

در کد بالا ما کل حروف را در یک متغیر به نام alphabet ریخته ایم و متغیر دیگری به نام n  تعداد حروفی را مشخص میکند که ما میخواهیم جایگشت آنها را محاسبه کنیم. مثلا اگر n برابر با 3 بود یعنی حروف abc و یا 4 بود یعنی حروف abcd.

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *