এই সমস্যায়, দুটি পূর্ণসংখ্যা k এবং n দেওয়া থাকে। এবং ১ থেকে n পর্যন্ত সংখ্যা ব্যবহার করে দৈর্ঘ্য k-এর সব সিকোয়েন্স সর্টেড অর্ডারে প্রিন্ট করতে হবে।
উদাহরণ দিয়ে বুঝি:
ইনপুট: k = 2 ; n = 3 আউটপুট: 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
এই সমস্যায়, আমাদের উপরে বর্ণিত সিকোয়েন্সটি প্রিন্ট করতে হবে।
এটি সমাধান করার একটি সহজ পদ্ধতি হলো সিকোয়েন্সের ইন্টিজারগুলো ইনক্রিমেন্ট করা যতক্ষণ না সেগুলো मैক্স ভ্যালু n-এ পৌঁছায়। নিচে সমাধানের বিস্তারিত বর্ণনা দেওয়া হলো।
অ্যালগরিদম
১) k আকারের একটি অ্যারে তৈরি করুন যেখানে সব ভ্যালু = 1 অর্থাৎ {1, 1, ..k বার}। ২) ধাপ ৩ এবং ৪ পুনরাবৃত্তি করুন যতক্ষণ না অ্যারেটি {n, n, ..., n} হয়ে যায়। ৩) অ্যারেটি প্রিন্ট করুন। ৪) মান ইনক্রিমেন্ট করুন যাতে অ্যারের এলিমেন্টগুলো পরবর্তী ভ্যালুতে যায়। উদাহরণস্বরূপ, {1, 1, 1} ইনক্রিমেন্ট হয়ে {1, 1, 2} হবে এবং {1, 3, 3} ইনক্রিমেন্ট হয়ে {2, 1, 1} হবে। এর জন্য অ্যারের kth এলিমেন্ট চেক করতে হবে, যদি সেটি n-এর সমান হয় তবে আপডেট করুন, তারপর সিকোয়েন্সের k-1 এলিমেন্ট চেক করুন এবং একই শর্তের জন্য তা করুন।C++ উদাহরণ
নিচের প্রোগ্রামটি কনসেপ্টটি আরও স্পষ্ট করবে।
#include<iostream> using namespace std; void printSequence(int arr[], int size){ for(int i = 0; i < size; i++) cout<<arr[i]<<"\t"; cout<<endl; return; } int nextElement(int arr[], int k, int n){ int s = k - 1; while (arr[s] == n) s--; if (s < 0) return 0; arr[s] = arr[s] + 1; for(int i = s + 1; i < k; i++) arr[i] = 1; return 1; } void generateSequence(int n, int k){ int *arr = new int[k]; for(int i = 0; i < k; i++) arr[i] = 1; while(1){ printSequence(arr, k); if(nextElement(arr, k, n) == 0) break; } return; } int main(){ int n = 3; int k = 2; cout<<"The sequence is :\n"; generateSequence(n, k); return 0; }আউটপুট
সিকোয়েন্সটি হলো:
1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
এই পদ্ধতিটি বোঝা সহজ কিন্তু এটি আরও ভালো এবং দক্ষ করা যায়।
এই পদ্ধতিতে রিকার্শন এবং একটি এক্সট্রা ইন্ডেক্স ব্যবহার করা হয় সিকোয়েন্স অফসেট চেক করার জন্য (যে ভ্যালুর পর সিকোয়েন্স ফ্লিপ হবে)। ফাংশনটি রিকার্শিভলি কল হবে এবং ইন্ডেক্স পর্যন্ত টার্মগুলো আপডেট করবে না। এবং ইন্ডেক্সের পরের টার্মগুলো জন্য ফাংশনটি রিকার্শন করবে।
রিকার্শিভ উদাহরণ
#include<iostream> using namespace std; void printSequence (int arr[], int size){ for (int i = 0; i < size; i++) cout << arr[i] << "\t"; cout << endl; return; } void generateSequence (int arr[], int n, int k, int index){ int i; if (k == 0){ printSequence (arr, index); } if (k > 0){ for (i = 1; i <= n; ++i){ arr[index] = i; generateSequence (arr, n, k - 1, index + 1); } } } int main (){ int n = 3; int k = 2; int *arr = new int[k]; cout<<"The sequence is:\n"; generateSequence (arr, n, k, 0); return 0; }আউটপুট
সিকোয়েন্সটি হলো:
1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
