Проверить, есть ли в векторе все возможные комбинации символов

Я нашел много других вопросов, в которых спрашивалось, как создать все возможные комбинации 'A' 'B' 'C' в векторе, но Я пытаюсь найти более простой способ проверить, содержит ли мой вектор, который содержит много разных и одинаковых комбинаций 'A' 'B' 'C' (с повторением, например, AAA и CAA) все возможные комбинации этих трех символы.

Я собирался сделать каждую комбинацию символов равной разному числу и иметь оператор switch, как показано ниже, который меняет каждый регистр на true при совпадении, а в конце имеет оператор if, проверяющий, все ли случаи истинны.

Но мне кажется, что есть более простой способ сделать это ...

Я все еще новичок в C++, поэтому приветствую любую помощь или предложения

vector<string> myVector = {"ABC", "CBA"};
bool case1 = false;
for(int i = 0; i < myVector.size(); i++){
    switch(myVector[i]){
        case 11:
            case1 = true;
            break;
        ...
    }        
}

Я думаю, что next_permutation - это то, что вы ищете.

Nyque 26.10.2018 06:50

Примечание: myVector[i] - это string. Вы не можете switch на string на C++.

user4581301 26.10.2018 07:00
3
2
113
3

Ответы 3

  • Сохраните все перестановки строки в vector
  • Сравните это с входным вектором

Минимальный пример будет выглядеть так:

#include <algorithm>
#include <string>
#include <iostream>

int main()
{
    std::string s = "ABC";

    std::vector<string> perString;
    std::vector<string> inputVector = {"ABC", "ACB", "BAC", "BCA", "CAB", "CBA"}; 
    do {
        perString.push_back(s);
    } while(std::next_permutation(s.begin(), s.end()));
    if(perString == inputVector)
        std::cout<< "YES, the vector has all possible combinations of characters" << '\n';
    else
        std::cout<< "NO, It doesn't" << '\n';       

    return 0;
}

Не все эти комбинации являются перестановками, хотя {"AAA", "AAB", "AAC", "ABA", "ABB", "ABC", "ACA", "ACB", "ACC", "BAA" ‌ , «BAB», «BAC», «BBA», «‌ BBB», «BBC», «BCA», «BC‌ B», «BCC», «CAA», «CAB» ‌, «CAC» , «CBA», «CBB», «‌ CBC», «CCA», «CCB», «CC‌ C»}

DiamondEdge 26.10.2018 08:28

Я не знала, было ли это с повторами

P.W 26.10.2018 08:29

Какие-нибудь решения для повторения?

DiamondEdge 26.10.2018 08:31

Функция std для этого недоступна. Но примеры доступны в Интернете. Проверьте эту ссылку: geeksforgeeks.org/combinations-with-repetitions

P.W 26.10.2018 08:33

Найдя все комбинации с повторениями, можно сравнивать векторы

P.W 26.10.2018 14:08
  • Отфильтруйте свой вектор, чтобы иметь только действительную строку (поэтому отклоняйте "AZA", если вы хотите только буквы из 'A', 'B', 'C')
  • std::sort / std::unique его содержимое. (так что "AAA", "ABA", "AAA"} -> {"AAA", "ABA"}).
  • затем проверьте размер вектора с ожидаемым размером (3 ** 3 или 27 в вашем случае ($alphabetSize ** $stringSize)).

Один из способов решения этой проблемы - отсортировать вектор проверяемых комбинаций (если это еще не сделано), а затем сравнить элементы со всеми возможными (отсортированными) комбинациями. Временная сложность этого подхода из-за фазы сортировки составляет O (C * log C), где C - количество элементов введенного вектора.

C может быть довольно большим, учитывая ппg> как количество возможных элементов и k количество выбранных элементов, вся возможная комбинация с повторениями равна ппg>k (в примере OP это 3 ^ 3 = 27).

Другой подход, который не требует ни сортировки исходного вектора, ни фактического создания отсортированных комбинаций, аналогичен поиску значения в хеш-таблице.

Если все комбинации можно отсортировать, их тоже можно проиндексировать. Таким образом, вы можете вычислить «индекс» конкретной комбинации, представленной проверяемой строкой, и подсчитать количество найденных допустимых комбинаций.

Это возможная реализация:

#include <iostream>
#include <string>
#include <vector>

// Transforms a string representing a combination into the index of that
// combination in the set of all possible combinations
size_t index_of(std::string const &candidate, std::string const &source);

// Check if the the vector 'combs' contains all the possible combinations
// of 'k' elements of string 'base'
bool are_there_all_the_possible_combinations(std::string const &base,
                                             size_t k,
                                             std::vector<std::string> const &combs);

int main()
{
    std::string base {"ABC"};

    std::vector<std::string> combs {
        "AAA", "AAB", "AAC", "ABA", "ABB", "ABC", "ACA", "ACB", "ACC",
        "BAA", "BAB", "BAC", "BBA", "BBB", "BBC", "BCA", "BCB", "BCC",
        "CAA", "CAB", "CAC", "CBA", "CBB", "CBC", "CCA", "CCB", "CCC"
    };

    size_t k = 3;

    std::cout << ( are_there_all_the_possible_combinations(base, k, combs)
                 ? "Yes\n" : "No\n" );              // <-- it should output 'Yes'

    combs.erase( std::remove( combs.begin(), combs.end(), "BCA" ), combs.end() );

    std::cout << ( are_there_all_the_possible_combinations(base, k, combs)
                 ? "Yes\n" : "No\n" );              // <-- it should output 'No'

    combs.push_back("BCA");              // <-- Note that now the vector isn't sorted.

    std::cout << ( are_there_all_the_possible_combinations(base, k, combs)
                 ? "Yes\n" : "No\n" );              // <-- it should output 'Yes'
}

// Calculate base ^ exponent (using size_t, not floating point math)
constexpr size_t ull_pow(size_t base, size_t exponent)
{
    size_t result = 1;
    for (;;)
    {
        if (exponent & 1)
            result *= base;
        exponent >>= 1;
        if (exponent == 0)
            break;
        base *= base;
    }
    return result;
}


// Counts the number of valid combinations and check if it equals the total
bool are_there_all_the_possible_combinations(std::string const &base,
                                             size_t k,
                                             std::vector<std::string> const &combs)
{
    size_t total_combinations = ull_pow(base.size(), k);
    std::vector<bool> combinations(total_combinations);

    size_t count = 0;
    for (auto const & str : combs)
    {
        if (str.size() != k)
        {
            // You can either ignore those mismatches or break
            continue;
        }
        size_t pos = index_of(str, base);
        if (pos == std::string::npos)
        {   
            // This string doesn't belong to the possible combinations. It's
            // unclear if OP want to ignore this case or consider it a mismatch
            continue;
        }
        if ( combinations[pos] )
        {
            // This is a duplicate. Again, it can be ignored or not.
            continue;
        }
        combinations[pos] = true;
        ++count;
    }

    return count == total_combinations;    
}

// Evaluate the index as a number in base n (number of elements in the base string)
size_t index_of(std::string const &candidate, std::string const &source)
{
    size_t result = 0, base = 1;
    for (auto c = candidate.crbegin(); c != candidate.crend(); ++c)
    {
        size_t pos = source.find(*c);
        if (pos == std::string::npos)
            return std::string::npos;
        result += pos * base;
        base *= source.size();
    }
    return result;
}

Другие вопросы по теме