Dada una lista de permutaciones de cualquier palabra. Encuentra la permutación que falta en la lista de permutaciones.
Ejemplos:
Input : Permutation_given[] = {"ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DCAB"}; Output : DBAC DBCA
1) Creamos un conjunto de todas las strings dadas.
2) Y un conjunto más de todas las permutaciones.
3) Finalmente devuelva la diferencia entre dos conjuntos.
#include <bits/stdc++.h> using namespace std; void find_missing_strings(string Permutation_given[], size_t Size_Permutation_given) { // vector "permutation" containing all // the permutation of input string vector<string> permutations; // Here we can take any string // from the given list and do // the necessary permutation string input = Permutation_given[0]; permutations.push_back(input); // In the loop we will store // all the permutations of the string // in the vector "permutation". while (true) { string p = permutations.back(); // Getting next permutation of input string next_permutation(p.begin(), p.end()); if (p == permutations.front()) break; permutations.push_back(p); } // vector containing all the // missing strings in permutation vector<string> missing; // given_permutations contains the // permutation of the input string set<string> given_permutations(Permutation_given, Permutation_given + Size_Permutation_given); // Through the set difference we will get // the missing words in vector missing set_difference(permutations.begin(), permutations.end(), given_permutations.begin(), given_permutations.end(), back_inserter(missing)); // printing all the missing string for (auto i = missing.begin(); i != missing.end(); ++i) cout << *i << endl; } // Driver code int main() { string Permutation_given[] = { "ABCD", "CABD", "ACDB", "DACB", "BCDA", "ACBD", "ADCB", "CDAB", "DABC", "BCAD", "CADB", "CDBA", "CBAD", "ABDC", "ADBC", "BDCA", "DCBA", "BACD", "BADC", "BDAC", "CBDA", "DCAB" }; // size of permutation list size_t Size_Permutation_given = sizeof(Permutation_given) / sizeof(*Permutation_given); find_missing_strings(Permutation_given, Size_Permutation_given); return 0; }
Producción:
DBAC DBCA
Publicación traducida automáticamente
Artículo escrito por Surya Priy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA