Thiếu hoán vị trong danh sách trong C ++

Tuyên bố vấn đề

Đưa ra một danh sách các hoán vị của bất kỳ từ nào. Tìm hoán vị còn thiếu từ danh sách các hoán vị.

Ví dụ

If permutation is = { “ABC”, “ACB”, “BAC”, “BCA”} then missing
permutations are {“CBA” and “CAB”}

Thuật toán

• Tạo một tập hợp tất cả các chuỗi đã cho
• Và một tập hợp tất cả các hoán vị
• Chênh lệch lợi nhuận giữa hai tập hợp

Ví dụ

#include <bits/stdc++.h>
using namespace std;
void findMissingPermutation(string givenPermutation[], size_t
permutationSize) {
   vector<string> 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<string> missing;
   set<string> 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;
}

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Đầu ra

Missing permutations are
CAB
CBA