Ideas for writing a "Combinator"

Discussion in 'C++' started by Virchanza, Apr 19, 2011.

  1. Virchanza

    Virchanza Guest

    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, Apr 19, 2011
    #1
    1. Advertising

  2. Virchanza

    Virchanza Guest

    On Apr 19, 11:12 pm, Virchanza <> wrote:

    > 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';
    Virchanza, Apr 19, 2011
    #2
    1. Advertising

  3. Virchanza

    Guest

    On Apr 19, 5:12 pm, Virchanza <> wrote:
    > 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.
    , Apr 20, 2011
    #3
  4. Virchanza

    Stefan Ram Guest

    "" <> writes:
    >On Apr 19, 5:12 pm, Virchanza <> wrote:

    (...)
    >> void Combinate(char *const pstart,
    >>
    >>size_t const len,

    (...)
    >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.
    Stefan Ram, Apr 20, 2011
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. David
    Replies:
    2
    Views:
    999
    Anthony J Bybell
    Nov 2, 2004
  2. HNguyen
    Replies:
    4
    Views:
    2,401
    HNguyen
    Dec 21, 2004
  3. Scott Weeks

    Ruby Parser Combinator

    Scott Weeks, Jan 20, 2006, in forum: Ruby
    Replies:
    7
    Views:
    116
    Eric Mahurin
    Jan 22, 2006
  4. Lui Core
    Replies:
    0
    Views:
    101
    Lui Core
    Jun 10, 2009
  5. Brian Maddy
    Replies:
    1
    Views:
    381
    Robert Klemme
    Jun 3, 2011
Loading...

Share This Page