جایگشت حروف در جاوا (Combinations)

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

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

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

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

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

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

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

a
ab
abc
ac
b
bc
c

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

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

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

public class Combinations {


    public static void comb1(String s) { comb1("", s); }


    private static void comb1(String prefix, String s) {
        if (s.length() > 0) {
            System.out.println(prefix + s.charAt(0));
            comb1(prefix + s.charAt(0), s.substring(1));
            comb1(prefix,               s.substring(1));
        }
    } 


    public static void comb2(String s) { comb2("", s); }
    private static void comb2(String prefix, String s) {
        System.out.println(prefix);
        for (int i = 0; i < s.length(); i++)
            comb2(prefix + s.charAt(i), s.substring(i + 1));
    } 


}

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

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

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

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

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

public static void main(String[] args) {
        int n = 3;
        String alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
        String elements = alphabet.substring(0, n);


        comb1(elements);
        System.out.println();


        comb2(elements);
        System.out.println();
    }

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