Струны Generation

Question

Я хотел бы знать, как я могу создать различные строки из некоторых заданных символов, например:

данные символы: a, b

Я хотел бы генерировать следующие строки:

aa 
ab 
ba 
bb 

То, о чем я думал, имеет (только для двух входов) два для однолинейных циклов, а затем цикл каждого из числа входов, которые в этом случае равны 2, а выходные строки будут 2 * 2 = 4 строки и при увеличении числа t он число выходных строк будет увеличиваться путем умножения п * п (п-кратное)

Answer 1

Я думаю, что это подстановка вопрос ..

http://www.bearcave.com/random_hacks/permute.html

Answer 2

Это изменение Kleene closure (Kleene star), если это поможет вам в поиске решения.

Answer 3

Вашего подхода (насколько я понял его) хорошо звучит как первую попытку, хотя доказательство пудинга ест его, так что писать код и протестировать его :-)

Обратите внимание, что он выиграл 't масштабируется очень хорошо, поэтому вопрос заключается в том, сколько символов и сколько строк вы ожидаете получить. Если ответ «не так много», а потребление производительности/памяти не является проблемой, вполне нормально придерживаться простейшего решения, которое работает. В противном случае вам нужен более сложный алгоритм.

У меня была смутно подобная задача некоторое время назад, где количество возможных перестановок было настолько велико, что было просто недостаточно памяти для хранения каждого в одно и то же время. Таким образом, мы попытались смоделировать перестановки с номерами: обратите внимание, что любая п долго перестановка м символов может быть определена с м базового числом п цифр. Таким образом, путем повторения всех целых значений от 0 до m ⁿ, вызывая довольно простой метод преобразования, вы получаете каждую возможную строку один за другим. Для значения индекса, конечно, вам может потребоваться использовать более крупный целочисленный тип, например long long, для больших m и n значения.

Answer 4

С рекурсии (только идея демонстрации):

void generate(std::string& s, size_t beg) { 
    for (char c = 'a'; c <= 'b'; ++c) { 
    s[beg] = c; 
    if (beg < s.length() - 1) { 
     generate (s, beg + 1); 
    } 
    else { 
     std::cout << s << std::endl; 
    } 
    } 
} 

int main() { 
    std::string s = "####"; 
    generate(s, 0); 
    return 0; 
} 

Answer 5

Вы можете использовать зЬй :: next_permutation. Это будет работать, даже если вы повторяете буквы (т. Е. Буквы = "ababcd").

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


int main(int argc, char** argv) { 
    std::string letters = "abcd"; 

    std::sort(letters.begin(), letters.end()); 
    do { 
     std::cout << letters << "\n"; 
    } 
    while (std::next_permutation(letters.begin(), letters.end())); 
}