ข้อความโจทย์
กำหนดรายการของการเรียงสับเปลี่ยนของคำใดคำหนด หาการเรียงสับเปลี่ยนที่หายไปจากรายการ
ตัวอย่าง
If permutation is = { "ABC", "ACB", "BAC", "BCA"} then missing permutations are {"CBA" and "CAB"}
อัลกอริทึม
- สร้างเซตของสตริงทั้งหมดที่กำหนด
- และอีกเซตหนึ่งของการเรียงสับเปลี่ยนทั้งหมด
- คืนค่าความแตกต่างระหว่างสองเซต
ตัวอย่างโค้ด C++
#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
