সি++ প্রোগ্রাম: পারমুটেশন লিস্ট থেকে অনুপস্থিত পারমুটেশন খুঁজে বের করা

সমস্যা বিবরণ

কোনো শব্দের পারমুটেশন (क्रमবিন্যাস)ের একটি লিস্ট দেওয়া আছে। সেই লিস্ট থেকে অনুপস্থিত পারমুটেশন খুঁজে বের করতে হবে।

উদাহরণ

যদি পারমুটেশন = { "ABC", "ACB", "BAC", "BCA" } হয়,
তবে অনুপস্থিত পারমুটেশনগুলো হবে { "CBA" এবং "CAB" }

অ্যালগরিদম

• দেয়া সব স্ট্রিংয়ের একটি সেট তৈরি করুন।
• সাম্ভব সব পারমুটেশনের একটি সেট তৈরি করুন।
• দুটি সেটের পার্থক্য (difference) রিটার্ন করুন।

সি++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

void findMissingPermutation(string givenPermutation[], size_t permutationSize) {
    vector permutations;
    string input = givenPermutation[0];
    permutations.push_back(input);
    while (true) {
        string p = permutations.back();
        next_permutation(p.begin(), p.end());
        if (p == permutations.front())
            break;
        permutations.push_back(p);
    }
    vector missing;
    set givenPermutations(givenPermutation, givenPermutation + permutationSize);
    set_difference(permutations.begin(), permutations.end(),
                   givenPermutations.begin(), givenPermutations.end(),
                   back_inserter(missing));
    cout << "Missing permutations are" << endl;
    for (auto i = missing.begin(); i != missing.end(); ++i)
        cout << *i << endl;
}

int main() {
    string givenPermutation[] = {"ABC", "ACB", "BAC", "BCA"};
    size_t permutationSize = sizeof(givenPermutation) / sizeof(*givenPermutation);
    findMissingPermutation(givenPermutation, permutationSize);
    return 0;
}

আউটপুট

Missing permutations are
CAB
CBA