জাভাতে ArrayList ব্যবহার করে স্ট্রিংয়ের সকল পারমিউটেশন প্রিন্ট করা

সমস্যা বিবরণ

এই প্রোগ্রামে আমরা একটি স্ট্রিং গ্রহণ করব এবং তার সকল সম্ভাব্য পারমিউটেশন (permutation) বা বিন্যাস গণনা করে প্রিন্ট করব। এইবার আমরা ArrayList ব্যবহার করে সমাধান করব।

উদাহরণ

ইনপুট: "XYZ"

আউটপুট: XYZ, XZY, YXZ, YZX, ZXY, ZYX

অ্যালগরিদম ও লজিক

আমরা একটি রিকার্সিভ (recursive) ফাংশন লিখব যা স্ট্রিংয়ের প্রতিটি ক্যারেক্টারের জন্য সব সম্ভাব্য পজিশনে বসিয়ে নতুন কম্বিনেশন তৈরি করবে। বেস কেস হবে খালি স্ট্রিং, যেখান থেকে একটি খালি স্ট্রিংসহ ArrayList রিটার্ন করবে।

জাভা কোড উদাহরণ

import java.util.ArrayList;

public class StringPermutationArrayList {
    
    // ArrayList-এর কন্টেন্ট প্রিন্ট করার হেল্পার মেথড
    static void printArrayList(ArrayList<String> combo) {
        combo.remove(""); // খালি স্ট্রিং বাদ দিন
        for (int i = 0; i < combo.size(); i++) {
            System.out.print(combo.get(i) + "\t");
        }
    }
    
    // রিকার্সিভ ফাংশন: স্ট্রিংয়ের সকল পারমিউটেশন জেনারেট করে
    public static ArrayList<String> generatePermutation(String str) {
        // বেস কেস: খালি স্ট্রিং
        if (str.length() == 0) {
            ArrayList<String> empty = new ArrayList<>();
            empty.add("");
            return empty;
        }
        
        // প্রথম ক্যারেক্টার এবং বাকি সাবস্ট্রিং
        char ch = str.charAt(0);
        String subStr = str.substring(1);
        
        // রিকার্সিভ কল: বাকি স্ট্রিংয়ের পারমিউটেশন পাওয়া
        ArrayList<String> lastCombination = generatePermutation(subStr);
        
        // নতুন কম্বিনেশন তৈরি
        ArrayList<String> newCombination = new ArrayList<>();
        for (String val : lastCombination) {
            for (int i = 0; i <= val.length(); i++) {
                // প্রতিটি পজিশনে চরেক্টার ইনসার্ট করুন
                newCombination.add(val.substring(0, i) + ch + val.substring(i));
            }
        }
        return newCombination;
    }
    
    public static void main(String[] args) {
        String str = "NOPQ";
        System.out.println("স্ট্রিংয়ের পারমিউটেশনগুলো:");
        printArrayList(generatePermutation(str));
    }
}

আউটপুট

স্ট্রিংয়ের পারমিউটেশনগুলো:
NOPQ    ONPQ    OPNQ    OPQN    NPOQ    PNOQ    PONQ    POQN    
NPQO    PNQO    PQNO    PQON    NOQP    ONQP    OQNP    OQPN    
NQOP    QNOP    QONP    QOPN    NQPO    QNPO    QPNO    QPON

কোড ব্যাখ্যা

1. বেস কেস: যখন স্ট্রিং খালি হয়, একটি খালি স্ট্রিংসহ ArrayList রিটার্ন করা হয়।
2. রিকার্সিভ স্টেপ: প্রথম ক্যারেক্টার (`ch`) আলাদা করে, বাকি স্ট্রিংয়ের (`subStr`) পারমিউটেশন রিকার্সিভলি পাওয়া হয়।
3. কম্বিনেশন বিল্ডিং: প্রতিটি পূর্ববর্তী পারমিউটেশনের (`val`) সব পজিশনে (০ থেকে length পর্যন্ত) নতুন ক্যারেক্টার ইনসার্ট করে নতুন পারমিউটেশন তৈরি করা হয়।
4. সময় জটিলতা: O(n × n!) — n দৈর্ঘ্যের স্ট্রিংয়ের n! পারমিউটেশন হয়, এবং প্রতিটি তৈরি করতে O(n) সময় লাগে।

অ্য্যারেলিস্ট ব্যবহারের সুবিধা

• ডাইনামিক সাইজ: এড করতেই সাইজ বেড়ায়।
• সহজ ইটেরেশন এবং ম্যানিপুলেশন।
• জেনেরিক টাইপ সেফটি (এখানে String)।

সারসংক্ষেপ

এই প্রোগ্রাম দেখিয়েছে কিভাবে রিকারশন এবং ArrayList একসাথে ব্যবহার করে স্ট্রিং পারমিউটেশন জেনারেট করা যায়। এটি কম্পিটিটিভ প্রোগ্রামিং এবং ইন্টারভিউতে একটি phổপ্রিয় সমস্যা। বড় স্ট্রিংয়ের জন্য এটি মেমরি ও টাইম লিমিট ছাড়াতে পারে, তখন ইটেরেটিভ বা হিপস অ্যালগরিদম ব্যবহার করা ভালো।