Bruteforce string generator in C++ with resume option

Question

I want to write string generator in C++ which allow me to resume generation of the strings from one string that I give to the function on the input. For example when I give string length=20 to the function, I'll wait some time and I'll stop my program I don't want to start over with string "aaaaaaaaaaaaaaaaaaaa", but I would rather to start next execution with some previously generated string (logged somewhere when program stops).

Here is my code how I do it right now:

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);
}

Also, in this revcursive function strings are generated "from the end" (for example last "a" is changed, then second last "a" etc.), do you have any suggestions how to change it to generate strings "from the beginning"?

You may use [signals](https://www.geeksforgeeks.org/signals-c-language/) of C, C++. When u close program, by Ctrl+C then some function would be invoked, this would save the current generated string in the log — Nimit Bhardwaj, Jun 07 '19 at 06:59
Does this include that your application should start in resume with a certain level of recursion? I don't believe thats impossible but harder to solve. (In this case, I would switch from simple recursion (as it is now) to iteration with stacks of data. Hence, the stack data would be something which could be serialized and safed and reloaded on resume to continue processing.) — Scheff's Cat, Jun 07 '19 at 07:03
@Scheff Yes, I would like to resume with a certain level of recursion. Or even better, get rid of recursive function and replace it with some good iterative method. — westman379, Jun 07 '19 at 07:25
@NimitBhardwaj Thanks for the tip, but logging is minor issue here, resuming execution on certain point is what I'm looking for. — westman379, Jun 07 '19 at 07:25
Yep, simple it is, just when u closed the program, state of the program is saved, when u start the program, check the logs, if logs are found then the state would be found, now u may have the problem of re-establishing the stack, for this, I would say try to create an iterative method as @Scheff said, use the stack of STL and assume its the stack of recursion push when needed pop when needed — Nimit Bhardwaj, Jun 07 '19 at 07:28
I found another question concerning how to convert recursive to iterative: [SO: Convert this recursive function to iterative](https://stackoverflow.com/q/21572631/7478597) (and there are probably more). The general idea is IMHO: All the local variables and parameters, you have to put into a structure (say: Context) which is stored in a stack. When ever you would do a recursive call you have to push a new context. When ever you would return from a recursive call you have to pop a context (and apply the results) to the new top of stack. If stack becomes empty you are done and return. — Scheff's Cat, Jun 07 '19 at 07:32
On interrupt of execution, the current stack can be saved. Then, on resume, a saved stack can be loaded. (Please, don't take stack too literally. It could be e.g. a `std::vector` used as stack to simplify serialization.) — Scheff's Cat, Jun 07 '19 at 07:35

fjardon · Accepted Answer · 2019-06-07T09:55:24.830

Remove recusion alltogether. Basically what you are doing is generating all strings in lexicographical order with a specific character order defined by your set2 array.

Consider your strings as a number written in a certain base whose digits are the characters from your set2 array. Then your algorithm boils down to:

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

The first run, you should pass the value "aaaaa" as initial value. If you interrupt, pass the last printed value as initial value to resume the output.

See it live there: https://coliru.stacked-crooked.com/a/642b53dd914dd94e

Note on transforming recursion to iteration

Basically when converting from recursion to iteration you want to save the stack variables for all depths of the stack. In your case your only relevant variables at each depth are: the current character, the current depth. All this information is contained in the last output string. That's why you don't need more than that to resume your computation.

C++ code copied here for reference:

#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));
}

Bruteforce string generator in C++ with resume option

1 Answers1