Ideas for writing a "Combinator"

[Virchanza]

One way of counting to 999 is to use loops within loops as follows:

for (unsigned i = 0; i != 10; ++i)
for (unsigned j = 0; j != 10; ++j)
for (unsigned k = 0; k != 10; ++k)
cout << i << j << k << '\n';

I started off with the general idea of how the above code works, and
wanted to make it so that it would:

1) Work with any specified "alphabet" (for example, the decimal
alphabet is "0123456789", whereas the hexadecimal alphabet is
"0123456789abcdef")
2) Work for any length of output string (e.g. if you're counting to
999 then the length is 3).

I started off with the following recursive function:

void Combinate(char const *const pstart,

size_t const len,

char const *const alphabet,
char *p)

{

char const *const plast = (pstart + len) - 1;


for ( char const *p_alpha = alphabet; *p_alpha; ++p_alpha )

{

*p = *p_alpha;



if ( plast == p )

{

puts(pstart);

}

else

{
Combinate(pstart,len,alphabet,p+1);

}

}

}

To make it count to 999, you would call it as so:

char str[4];
Combinate(str,3,"0123456789",str);

So after I got that working, I wanted to remove the recursive-ness of
it (stack overflow and all that jazz). I removed the recursive-ness by
manually implementing a stack. Here's the code I have now:

void Combinate(char *const pstart,

size_t const len,

char const *const alphabet)

{


struct Frame {



/* Function Parameters */
char *p;



/* Local variables */
char const *p_alpha;

};



static Frame frames[16384]; /* This could be allocated
dynamically if you like */


Frame *frame_pointer = frames; /* Points to current frame! */



char const *const plast = (pstart + len) - 1;


/* >>>>>>>>>> Set up the very first frame <<<<<<<<<< */


frame_pointer->p = pstart;


/* Begin psuedo-recursive function body */

Begin_Func:

{

for ( frame_pointer->p_alpha = alphabet; *frame_pointer-

p_alpha; ++frame_pointer->p_alpha )

{

*frame_pointer->p = *frame_pointer->p_alpha;



if ( plast == frame_pointer->p )

{

puts(pstart);

}

else

{
/* >>>>>>>>>> Set up the next frame <<<<<<<<<< */


frame_pointer[1].p = frame_pointer->p + 1;

++frame_pointer;



goto Begin_Func;
/* Equivalent of a recursive call */


Return_Location_For_Recursive_Call: ;

}

}



if ( frames == frame_pointer )
/* OK, we're done */
return;



--frame_pointer;


goto Return_Location_For_Recursive_Call;

}

}

This function can be used to create any sort of "combinator" or
"counter", for example if you want to run through all the possible
values for a 6-letter password.

Anyway I'd just like to ask if anyone else has any other ideas on how
to write a combinator or counter like this? Is the code I have right
now optimal (I'm talking about the code that implements its own
stack) ?

 

[Virchanza]

char str[4];
Combinate(str,3,"0123456789",str);

Opps, you need to set the null terminator yourself, the Combinate
function doesn't do it for you. (Yes, that's by design).

str[3] = '\0';

 

[robertwessel2]

One way of counting to 999 is to use loops within loops as follows:

    for (unsigned i = 0; i != 10; ++i)
        for (unsigned j = 0; j != 10; ++j)
            for (unsigned k = 0; k != 10; ++k)
                cout << i << j << k << '\n';

I started off with the general idea of how the above code works, and
wanted to make it so that it would:

1) Work with any specified "alphabet" (for example, the decimal
alphabet is "0123456789", whereas the hexadecimal alphabet is
"0123456789abcdef")
2) Work for any length of output string (e.g. if you're counting to
999 then the length is 3).

I started off with the following recursive function:

void Combinate(char const *const pstart,

               size_t const len,

               char const *const alphabet,
               char *p)

{

    char const *const plast = (pstart + len) - 1;

    for ( char const *p_alpha = alphabet; *p_alpha; ++p_alpha )

    {

        *p = *p_alpha;

        if ( plast == p )

        {

            puts(pstart);

        }

        else

        {
            Combinate(pstart,len,alphabet,p+1);

        }

    }

}

To make it count to 999, you would call it as so:

char str[4];
Combinate(str,3,"0123456789",str);

So after I got that working, I wanted to remove the recursive-ness of
it (stack overflow and all that jazz). I removed the recursive-ness by
manually implementing a stack. Here's the code I have now:

void Combinate(char *const pstart,

               size_t const len,

               char const *const alphabet)

{

    struct Frame {

        /* Function Parameters */
            char *p;

        /* Local variables */
            char const *p_alpha;

    };

    static Frame frames[16384];  /* This could be allocated
dynamically if you like */

    Frame *frame_pointer = frames;  /* Points to current frame! */

    char const *const plast = (pstart + len) - 1;

    /* >>>>>>>>>> Set up the very first frame <<<<<<<<<< */

    frame_pointer->p = pstart;

    /* Begin psuedo-recursive function body */

    Begin_Func:

    {

        for ( frame_pointer->p_alpha = alphabet; *frame_pointer-

p_alpha; ++frame_pointer->p_alpha )

        {

            *frame_pointer->p = *frame_pointer->p_alpha;

            if ( plast == frame_pointer->p )

            {

                puts(pstart);

            }

            else

            {
                /* >>>>>>>>>> Set up the next frame <<<<<<<<<< */

                frame_pointer[1].p = frame_pointer->p +1;

                ++frame_pointer;

                goto Begin_Func;
/* Equivalent of a recursive call */

                Return_Location_For_Recursive_Call: ;

            }

        }

        if ( frames == frame_pointer )
  /* OK, we're done */
            return;

        --frame_pointer;

        goto Return_Location_For_Recursive_Call;

    }

}

This function can be used to create any sort of "combinator" or
"counter", for example if you want to run through all the possible
values for a 6-letter password.

Anyway I'd just like to ask if anyone else has any other ideas on how
to write a combinator or counter like this? Is the code I have right
now optimal (I'm talking about the code that implements its own
stack) ?

Allocating 16384 entries for frames is a bit absurd. Just how long do
you expect your program to run? With a two character alphabet, and an
output string length of 64, and assuming your generator could produce
a new string each nanosecond, it's going to take nearly six hundred
years to complete. The universe will be well into its heat death by
the time you finish the combinations for a 2 symbol, 110 character
string.

 

[Stefan Ram]

(...)
Allocating 16384 entries for frames is a bit absurd.

Leaving every other line of the source code empty and then
full-quoting this is as absurd.

I just wrote this C code to count in any base with
user-defined digits. The digits can have any length, so we
are not limited to as many digits as there are characters of
the execution character set (but currently there can be at
most about INT_MAX digits), and everything is allocated at
run time, so we are not limited to 16384 entries per frame.
But there still is recursion, which limits the number of
frame entries to a value related to the stack size.

#include <stdio.h>
#include <stdlib.h>

#define STRING char *

int N = 12; /* how many lines to write. Just used in main,
so one could use any other means to terminate the main loop.
For example, one can replace "for( int i = 0; i < N; ++i )"
below by "while( 1 )" in order to count forever. */

STRING names[]={ "0", "1", "2" }; /* the digits to be used.
Can be arbitrary strings.
Three digits specify a ternary number system. */

/* the output for the above data is:
0
1
2
10
11
12
20
21
22
100
101
102
*/

/* array */

int * n; int length;
int has_next;
int base;
STRING * arg;
STRING * result;

static int inc( int const p )
{ int result;
if( p < length )
{ if( n[ p ] < base - 1 ){ ++n[ p ]; result = 1; }
else { n[ p ]= 0; result = inc( p + 1 ); }}
else result = 0;
return result; }

static int increment()
{ return inc( 0 ); }

static STRING * dress()
{ for( int i = 0; i < length; ++i )
result[ i ]= arg[ n[ i ]];
return result; }

void array( int const l, void * a, int al )
{ length = l;
arg = a;
n = malloc( length * sizeof( int )); if( !n )abort();
result = malloc( length * sizeof( char * )); if( !result )abort();
for( int i = 0; i < length - 1; ++i )n[ i ]= 0;
n[ length - 1 ]= length > 1;
base = al;
has_next = length > 0 && base > 0; }

int hasnext(){ return has_next; }

STRING * next()
{ void * result = dress();
has_next = increment();
return result; }

/* counter */

int len;

int s = sizeof( names )/sizeof( STRING );

void counter()
{ len = 1;
array( len, names, s ); }

STRING * count()
{ if( !hasnext() )
{ free( n ); free( result ); ++len; array( len, names, s ); }
return next(); }

/* main */

int main(int argc, char *argv[])
{ counter();
for( int i = 0; i < N; ++i )
{ STRING * value = count();
for( int j = len - 1; j >= 0; --j )
printf( "%s", value[ j ]);
printf( "\n" ); }
free( result );
free( n ); }

Exercise: Convert the code sections »array« and »counter«
into two C++ classes, so as to structure the code in a more
object-oriented manner, and rewrite everything into
idiomatic C++ style, using »new«, »::std::string« and so.