ধরুন আমাদের একটি অ্যারেতে কয়েকটি স্ট্রিং আছে। আমাদের আলাদা আলাদা লাইনে তাদের সব পারমুটেশন খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুটটি স্ট্রিং এর মত হয় =["abc", "def", "ghi"], তাহলে আউটপুট হবে
abc def ghi abc ghi def def abc ghi def ghi abc ghi abc def ghi def abc
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন সংজ্ঞায়িত করুন next_permutation(), এতে n, স্ট্রিং অ্যারে s লাগবে,
- আরম্ভ করার জন্য i :=n - 1, যখন i> 0, আপডেট করুন (i 1 দ্বারা কম করুন), করুন:
- যদি s[i]> s[i - 1]), তারপর:
- j :=i + 1
j - যদি s[j] <=s[i - 1]), তারপর:
- লুপ থেকে বেরিয়ে আসুন
- t :=s[i - 1]
, আপডেট করুন (j 1 দ্বারা বাড়ান), করুন: - যদি s[i]> s[i - 1]), তারপর:
- s[i - 1] =s[j - 1]
- s[j - 1] =t
- i
- t :=s[i]
- s[i] :=s[n - 1]
- s[n - 1] =t
- না হওয়া পর্যন্ত
- নিম্নলিখিত অসীমভাবে করুন
- আরম্ভ করার জন্য i :=0, যখন i
- প্রদর্শন স্ট্রিং[i] তারপর (যদি আমি n - 1 এর মতো হয়, তাহলে পরবর্তী লাইনে যান, অন্যথায় ফাঁকা জায়গা প্রিন্ট করুন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <stdio.h>
#include <string.h>
int next_permutation(int n, char **s){
for (int i = n - 1; i > 0; i--)
if (strcmp(s[i], s[i - 1]) > 0){
int j = i + 1;
for (; j < n; j++)
if (strcmp(s[j], s[i - 1]) <= 0)
break;
char *t = s[i - 1];
s[i - 1] = s[j - 1];
s[j - 1] = t;
for (; i < n - 1; i++, n--){
t = s[i];
s[i] = s[n - 1];
s[n - 1] = t;
}
return 1;
}
for (int i = 0; i < n - 1; i++, n--){
char *t = s[i];
s[i] = s[n - 1];
s[n - 1] = t;
}
return 0;
}
int main(){
char *strings[] = {"abc", "def", "ghi"};
int n = 3;
do{
for (int i = 0; i < n; i++)
printf("%s%c", strings[i], i == n - 1 ? '\n' : ' ');
} while (next_permutation(n, strings));
}
ইনপুট
{"abc", "def", "ghi"} আউটপুট
abc def ghi abc ghi def def abc ghi def ghi abc ghi abc def ghi def abc
