Permutaciones faltantes en una lista

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *