Рубрики

Отсутствующие перестановки в списке

Дан список перестановок любого слова. Найдите недостающую перестановку из списка перестановок.

Примеры:

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) Создаем набор всех заданных строк.
2) И еще один набор всех перестановок.
3) Наконец, верните разницу между двумя наборами.

#include <bits/stdc++.h>

using namespace std;

  

void find_missing_strings(string Permutation_given[], size_t Size_Permutation_given)

{

    // вектор "перестановка", содержащий все

    // перестановка входной строки

    vector<string> permutations;

  

    // Здесь мы можем взять любую строку

    // из заданного списка и делаем

    // необходимая перестановка

    string input = Permutation_given[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> given_permutations(Permutation_given, 

         Permutation_given + Size_Permutation_given);

  

    // Через разность множеств получим

    // пропущенные слова в векторе отсутствуют

    set_difference(permutations.begin(), permutations.end(),

                                 given_permutations.begin(),

                                 given_permutations.end(), 

                                  back_inserter(missing));

  

    // печатаем всю отсутствующую строку

    for (auto i = missing.begin(); i != missing.end(); ++i)

        cout << *i << endl;

}

  
// Код драйвера

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_t Size_Permutation_given = 

                 sizeof(Permutation_given) / 

                 sizeof(*Permutation_given);

  

    find_missing_strings(Permutation_given, 

                    Size_Permutation_given);

  

    return 0;

}

Выход:

DBAC
DBCA

Рекомендуемые посты:

Отсутствующие перестановки в списке

0.00 (0%) 0 votes