คำชี้แจงปัญหา
ให้รายการการเรียงสับเปลี่ยนของคำใด ๆ ค้นหาการเรียงสับเปลี่ยนที่หายไปจากรายการเรียงสับเปลี่ยน
ตัวอย่าง
If permutation is = { “ABC”, “ACB”, “BAC”, “BCA”} then missing permutations are {“CBA” and “CAB”}
อัลกอริทึม
- สร้างชุดของสตริงที่กำหนดทั้งหมด
- และอีกหนึ่งชุดของการเรียงสับเปลี่ยนทั้งหมด
- คืนค่าส่วนต่างระหว่างสองชุด
ตัวอย่าง
#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; }
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
ผลลัพธ์
Missing permutations are CAB CBA