Как искать все возможные комбинации добавления буквы к слову?

Question

Я застрял на этой проблеме навсегда. То, что я пытаюсь сделать, это посмотреть, сколько возможных способов добавить букву к слову, используя какую-то методологию бинарного поиска.

Например, предположим, что у меня есть слово длиной 4 буквы, затем слово: ----

Теперь предположим, что я хочу увидеть все возможные способы, которыми я мог бы добавить "Y"к этому слову. Тогда все возможные комбинации будут 2 ^ 4 и будут выглядеть так:

----    
---Y
--Y-
--YY
-Y--
-Y-Y
-YY-
-YYY
Y---
Y--Y
Y-Y-
Y-YY
YY--
YY-Y
YYY-
YYYY

Как я могу получить все эти комбинации? Затем я планирую добавить все эти комбинации в список строк, которые затем буду использовать для сравнения с набором слов.

Answer 1

вы можете увидеть это как двоичную проблему. Это все числа от 0000 до 1111 в двоичной базе. И тогда вы отображаете 1 на Y

Answer 2

Вы можете использовать алгоритм next_permutation

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

int main()
{
    std::string s = "____";
    std::string per;
    int count = 1;
    // first combi 
    std::cout << s << '\n';
    for (auto i=0;i<s.size();i++)
    {
    //character for replacement 
    s[i] = 'y';
    per = s;
    std::sort(per.begin(), per.end());
    do {
        std::cout << per << '\n';
        count++;
    } while(std::next_permutation(per.begin(), per.end()));
    }
     std::cout << "Number of Combination is "  << count<<'\n';
}

Выход

____
___y
__y_
_y__
y___
__yy
_y_y
_yy_
y__y
y_y_
yy__
_yyy
y_yy
yy_y
yyy_
yyyy
Number of Combination is 16

Answer 3

Почему бы не полный рекурсивный поиск? Должно работать что-то вроде следующего: Это работает так: Если вы хотите сгенерировать всю возможную строку длиной n, вы можете вставить либо 'Y', либо '-' в первую позицию. После того как вы приняли решение, вы можете добавить свой выбор ко всем возможным комбинациям длины n-1.

. Вот возможная реализация, которую вы можете попробовать онлайн :

vector<string>  generate_p(const int n){
    vector<string> ans;
    if(n==0)
    {
        ans.push_back("");   
    }
    else
    {
        auto v = generate_p(n-1);    
        for(size_t i = 0 ; i < v.size() ; i++){
            ans.push_back("Y"+v[i]);
            ans.push_back("-"+v[i]);
        }
    }
    return ans;   
}

---

Другой подход состоит в том, чтобы заметить, что для каждой позиции у вас есть два выбора: «Y» или «-», как у вас есть для двоичного числа, где вы можете выбрать между «1» или «0». Итак, если вы перечислите все числа от '0000' до '1111' в базе '2', вы получите все свои комбо. Я оставляю это как упражнение для вас.