Генерация строк

Question

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

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

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

aa
ab
ba
bb

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

Answer 1

Это вариант замыкания Клини (звезда Клини) , если это поможет вам найти решение.

Answer 2

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

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

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

Answer 3

Вы можете использовать std :: next_permutation. Это будет работать, даже если вы повторяете буквы (то есть letters = "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()));
}

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

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

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