get Elements of Recursion step-wise

Hello all,

i cant figute out how to make my code work the way i want it to.
make() gets me all the combination with a string of length k using a specific dataset. each char in dataset is meant to occurr 0 to k times in any relative position to the other elements in dataset.
So, its like a password-list generator.
The problem is that if i let it create f.ex. a 10 digit password vector with dataset "01234567879" there are 10^10 combinations * 10Bytes/Password means
a 100GB of random access memory usage and thus is not suitable in this case and, surely throws bad_alloc().

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
struct combinations
{
        string DATASET;
        size_t IND{};

        combinations(string _Dataset): DATASET(_Dataset) {}



        string next(string prefix, int k)
        {
            if (k == 0)
            {
                IND++;
                return prefix;
            }


            for (int i = 0; i < DATASET.size(); i++)
            {
                string new_Prefix = "";

                new_Prefix = prefix + DATASET.at(i);

                return next(new_Prefix, k - 1);
            }
        }


        bool has_next(int k)
        { return IND < pow(DATASET.size(), k); }
};


I wanna next() to return just the next item in the row, Element-wise.
Can someone help me out please?

Thank you very much.

greetings,

Luke
Last edited on
Convert to a 10-digit number. Add 1 to it (modulo 10^10). Then convert back.

If your password has a different number of chars, then use a different number base.

Doesn’t need recursion.
Last edited on
This uses a counter for every character position.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <string>
int main ( ) {
    std::string foo = "123";
    int used[3] = { 0, 0, 0 };
    int carry = 0;
    while ( carry == 0 ) {
        std::cout << foo[used[0]] << foo[used[1]] << foo[used[2]] << std::endl;
        carry = 1;
        for ( int i = 2 ; i >= 0 ; i-- ) {
            used[i] += carry;
            if ( used[i] == 3 ) {
                used[i] = 0;
                carry = 1;
            } else {
                carry = 0;
            }
        }
    }
}



$ ./a.out 
111
112
113
......
331
332
333
Thank you.
The problem is that
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <string>
int main ( ) {
    std::string foo = "123";
    int used[3] = { 0, 0, 0 };
    int carry = 0;
    while ( carry == 0 ) {
        std::cout << foo[used[0]] << foo[used[1]] << foo[used[2]] << std::endl;
        carry = 1;
        for ( int i = 2 ; i >= 0 ; i-- ) {
            used[i] += carry;
            if ( used[i] == 3 ) {
                used[i] = 0;
                carry = 1;
            } else {
                carry = 0;
            }
        }
    }
}

gives me the combinations from 1, 2 or 3. but i need to get a combination like that:
1
2
3
4
5
6
7
8
9
10
11
12
13
14

foo = "01234"
used = length 3 (not the same length than foo is.
                 i need it to take every item of foo and create a permutation with that)
out:
000
001
002
003
004
010
...
443
444

currently, the output is:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
000
001
002
010
011
012
020
021
022
100
101
102
110
111
112
120
121
122
200
201
202
210
211
212
220
221
222

and it skipps using 3 and 4 as elements.

where there is foo of a greater/smaller length than the individual results.
This is why i cant figure out how to solve this
Last edited on
The magic is on line 12. Perhaps if ( used[i] == foo.size() ) { would be more obivous?
> This is why i cant figure out how to solve this
You've got to replace all the 2's and 3's and anything else which specifically assumes a string length of 3 with something more appropriate.

It's a hack code to show you the concept.

Not something you can copy/paste without having to do any more thinking.
Thank you anyways.
I worked out a even faster way to achieve so, and post this here just for the sake of completeness times:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
struct combinations
    {
            string DATASET;
            const size_t K, OUTSIZE;
            size_t curr_pos{};

            string next(void)
            {
                size_t val, j;
                string result;
                if ((val = curr_pos++) < OUTSIZE)
                {
                    for (j = 0; j < K; j++)
                    {
                        result = DATASET[val % DATASET.size()] + result;
                        val /= DATASET.size();
                    }
                    return std::move(result);
                }
                return {};



            }
            bool has_next(void)
            { return curr_pos < OUTSIZE; }


            combinations(string _Dataset, int _K): DATASET(_Dataset), K(_K), OUTSIZE(pow(_Dataset.length(), _K)) {}
    };

Topic archived. No new replies allowed.