Генератор строк грубой силы в C ++ с возможностью возобновления - PullRequest
Новая
       25

Генератор строк грубой силы в C ++ с возможностью возобновления

0 голосов
/ 07 июня 2019

Я хочу написать генератор строк в C ++, который позволил бы мне возобновить генерацию строк из одной строки, которую я передаю функции на входе. Например, когда я даю функции длину строки = 20, я подожду некоторое время и остановлю свою программу. Я не хочу начинать заново со строки "aaaaaaaaaaaaaaaaaaaa", но я бы предпочел начать следующее выполнение с некоторыми ранее созданная строка (записывается где-то, когда программа останавливается).

Вот мой код, как я делаю это прямо сейчас: 

void printAllKLengthRec(char set[], string prefix, int n, int k)
{
    if (k == 0)
    {
        cout << (prefix) << endl;
        return;
    }

    for (int i = 0; i < n; i++)
    {
        string newPrefix;
        newPrefix = prefix + set[i];

        printAllKLengthRec(set, newPrefix, n, k - 1);
    }

}

void printAllKLength(char set[], int k, int n)
{
    printAllKLengthRec(set, "", n, k);
}


int main()
{
    cout << "Test\n";
    char set2[] = { 'a', 'b', 'c', 'd', '.', '\\', '_', 'f' };
    int k = 20;
    printAllKLength(set2, k, 8);
}

Кроме того, в этой рекурсивной функции строки генерируются «с конца» (например, изменяется последняя «а», затем вторая последняя «а» и т. Д.), Есть ли у вас какие-либо предложения, как изменить его, чтобы генерировать строки "с самого начала"?

1 Ответ

1 голос
/ 07 июня 2019

Устранить отторжение полностью. По сути, вы генерируете все строки в лексикографическом порядке с определенным порядком символов, определенным вашим массивом set2.

Рассматривайте ваши строки как число, записанное в определенной базе, цифрами которой являются символы из вашего массива set2. Тогда ваш алгоритм сводится к: 

str = <initial value>
do
   last = str
   str = last+1
   print str
while str > last

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

Посмотри, как там живут: https://coliru.stacked -crooked.com / a / 642b53dd914dd94e

Примечание по преобразованию рекурсии в итерацию

В основном при преобразовании из рекурсии в итерацию вы хотите сохранить переменные стека для всех глубин стека. В вашем случае ваши единственные релевантные переменные на каждой глубине: текущий символ, текущая глубина. Вся эта информация содержится в последней выходной строке. Вот почему вам не нужно больше, чтобы возобновить вычисления.

C ++ код, скопированный сюда для справки: 

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

using namespace std;
static string const digits = "abcd.\\_f";

string increment(string value) {
    string result;
    bool carry = true;
    for(int i=value.size()-1; i>=0; --i) {
        int v = digits.find(value.at(i));
        v += carry;
        carry = v >= digits.size();
        v = carry ? 0 : v;
        result.push_back(digits.at(v));
    }
    reverse(begin(result), end(result));
    return result;
}

bool compare_digits(char a, char b) {
    int va = digits.find(a);
    int vb = digits.find(b);
    return va < vb;
}

bool compare(string const& a, string const& b) {
    return lexicographical_compare(begin(a), end(a), begin(b), end(b), compare_digits);
}

int main(int argc, char* argv[]) {
    string initial = "aaa";

    // read new initial string from first argument if any
    if(argc > 1) initial = argv[1];

    string str = initial;
    string last;
    do {
        last = str;
        str = increment(last);
        cout << str << '\n';
    } while(compare(last, str));
}
...