Tìm hoán vị thiếu trong danh sách trong C++

Đề bài

Cho danh sách các hoán vị của một từ bất kỳ. Tìm hoán vị 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 tập hợp tất cả các chuỗi cho trước
• Và thêm một tập hợp tất cả các hoán vị
• Trả về hiệu giữa hai tập hợp

Ví dụ mã nguồn

#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 biên dịch và chạy chương trình trên. Nó tạo ra đầu ra sau:

Kết quả

Missing permutations are CAB CBA