COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Ideas for writing a "Combinator"

• Email
• Follow

```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

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) ?
```
 0
Reply virtual (44) 4/19/2011 10:12:26 PM

See related articles to this posting

```On Apr 19, 11:12=A0pm, Virchanza <virt...@lavabit.com> 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] =3D '\0';
```
 0
Reply virtual (44) 4/19/2011 10:24:09 PM

```On Apr 19, 5:12=A0pm, Virchanza <virt...@lavabit.com> wrote:
> One way of counting to 999 is to use loops within loops as follows:
>
> =A0 =A0 for (unsigned i =3D 0; i !=3D 10; ++i)
> =A0 =A0 =A0 =A0 for (unsigned j =3D 0; j !=3D 10; ++j)
> =A0 =A0 =A0 =A0 =A0 =A0 for (unsigned k =3D 0; k !=3D 10; ++k)
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 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,
>
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0size_t const len,
>
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0char const *const alphabet,
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0char *p)
>
> {
>
> =A0 =A0 char const *const plast =3D (pstart + len) - 1;
>
> =A0 =A0 for ( char const *p_alpha =3D alphabet; *p_alpha; ++p_alpha )
>
> =A0 =A0 {
>
> =A0 =A0 =A0 =A0 *p =3D *p_alpha;
>
> =A0 =A0 =A0 =A0 if ( plast =3D=3D p )
>
> =A0 =A0 =A0 =A0 {
>
> =A0 =A0 =A0 =A0 =A0 =A0 puts(pstart);
>
> =A0 =A0 =A0 =A0 }
>
> =A0 =A0 =A0 =A0 else
>
> =A0 =A0 =A0 =A0 {
> =A0 =A0 =A0 =A0 =A0 =A0 Combinate(pstart,len,alphabet,p+1);
>
> =A0 =A0 =A0 =A0 }
>
> =A0 =A0 }
>
> }
>
> 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,
>
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0size_t const len,
>
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0char const *const alphabet)
>
> {
>
> =A0 =A0 struct Frame {
>
> =A0 =A0 =A0 =A0 /* Function Parameters */
> =A0 =A0 =A0 =A0 =A0 =A0 char *p;
>
> =A0 =A0 =A0 =A0 /* Local variables */
> =A0 =A0 =A0 =A0 =A0 =A0 char const *p_alpha;
>
> =A0 =A0 };
>
> =A0 =A0 static Frame frames[16384]; =A0/* This could be allocated
> dynamically if you like */
>
> =A0 =A0 Frame *frame_pointer =3D frames; =A0/* Points to current frame! *=
/
>
> =A0 =A0 char const *const plast =3D (pstart + len) - 1;
>
> =A0 =A0 /* >>>>>>>>>> Set up the very first frame <<<<<<<<<< */
>
> =A0 =A0 frame_pointer->p =3D pstart;
>
> =A0 =A0 /* Begin psuedo-recursive function body */
>
> =A0 =A0 Begin_Func:
>
> =A0 =A0 {
>
> =A0 =A0 =A0 =A0 for ( frame_pointer->p_alpha =3D alphabet; *frame_pointer=
-
>
> >p_alpha; ++frame_pointer->p_alpha )
>
> =A0 =A0 =A0 =A0 {
>
> =A0 =A0 =A0 =A0 =A0 =A0 *frame_pointer->p =3D *frame_pointer->p_alpha;
>
> =A0 =A0 =A0 =A0 =A0 =A0 if ( plast =3D=3D frame_pointer->p )
>
> =A0 =A0 =A0 =A0 =A0 =A0 {
>
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 puts(pstart);
>
> =A0 =A0 =A0 =A0 =A0 =A0 }
>
> =A0 =A0 =A0 =A0 =A0 =A0 else
>
> =A0 =A0 =A0 =A0 =A0 =A0 {
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 /* >>>>>>>>>> Set up the next frame <<<<<=
<<<<< */
>
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 frame_pointer[1].p =3D frame_pointer->p +=
1;
>
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 ++frame_pointer;
>
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 goto Begin_Func;
> /* Equivalent of a recursive call */
>
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 Return_Location_For_Recursive_Call: ;
>
> =A0 =A0 =A0 =A0 =A0 =A0 }
>
> =A0 =A0 =A0 =A0 }
>
> =A0 =A0 =A0 =A0 if ( frames =3D=3D frame_pointer )
> =A0 /* OK, we're done */
> =A0 =A0 =A0 =A0 =A0 =A0 return;
>
> =A0 =A0 =A0 =A0 --frame_pointer;
>
> =A0 =A0 =A0 =A0 goto Return_Location_For_Recursive_Call;
>
> =A0 =A0 }
>
> }
>
> 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.
```
 0
Reply robertwessel2 (1674) 4/20/2011 12:42:16 AM

```"robertwessel2@yahoo.com" <robertwessel2@yahoo.com> writes:
>On Apr 19, 5:12�pm, Virchanza <virt...@lavabit.com> 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.

```
 0
Reply ram (2987) 4/20/2011 2:08:07 AM

3 Replies
34 Views

Similar Articles

12/6/2013 12:05:34 PM
[PageSpeed]

Similar Artilces:

The writing on the wall
> can't really compete with WoS Forums (it's content which matters, not > technicalities of the platform), any future I can see for CSS is either as > a ghost ship or as something to complement WoS, doing something that the > WoS Forums doesn't do. I hope you guys remember me, but a few years back I was quite an active poster and set up the ZX Golden Years website. Back in about 2000, I started writing a book about the 8-bit computer movement. It's still sitting on my computer, half-written and full of promise. One day I hope to go back to it and finish it off

Writing to Files
Can I write to files, say for example, to an excel spreadsheet and have it written in a certain order or in certain cells? Thanks, VAL On Tue, 30 Sep 2003 05:55:16 -0400, "Nevo" <victorlopez@bellsouth.net> wrote: >Can I write to files, say for example, to an excel spreadsheet and have it >written in a certain order or in certain cells? Yes, it is possible. You need to create a reference to the Excel object in your program. In the Visual Basic editor, select menu Project | References and scroll down and tick Microsoft Excel, click OK. Here's a simple program th

writing to sockets
In non-blocking NIO, why do I need the OP_WRITE flag to be set in an interest set ever? I understand that OP_READ indicates that new data is ready to be read. But for writing, should I not only need to do Channel.write(buffer) whenever I feel for it? In nonblocking mode, if the write buffer of the socket is full, just "blasting away" with writes will cause a large number of zero-length writes. If inside a tight loop, you would effectively busy-wait for sending of data, which would clear some of the buffer (much like not looking at a selector, and just calling read.... On Sun, 22 Jan 2006 23:00:21 +0100, Andersen wrote: > In non-blocking NIO, why do I need the OP_WRITE flag to be set in an > interest set ever? I understand that OP_READ indicates that new data > is ready to be read. But for writing, should I not only need to do > Channel.write(buffer) whenever I feel for it? You can write without OP_WRITE as long as write() succeeds. When write() returns 0, wait until OP_WRITE is indicated before attempting to write again. /gordon -- [ do not email me copies of your followups ] g o r d o n + n e w s @ b a l d e r 1 3 . s e

writing a proxy ..
Hi ppl ... I am writing a simple proxy server ... I redirect my browser to the local server and re-route the HTTP request to the host. I get a reply back from the HOST but unfortunately this is not shown in my browser ( html appears in my console ) . I am putting the code here .. ( Its a thread ) pls run with the Server Class specified below it .. package com.webproxy.fthread; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.net.Socket; import...("localhost", 8080); Socket s2 = null; (new PrintWriter(new OutputStreamWriter(s.getOutputStream()))) .write("GET http://www.google.com/ig HTTP/1.0"); s2 = ss.accept(); fthread t = new fthread(s2); t.start(); t.join(); } catch (IOException e) { // TODO Auto-generated catch block e.printStackTrace(); } catch (InterruptedException e) { // TODO Auto-generated catch block e.printStackTrace(); } } } ebby83@gmail.com wrote: > Hi ppl ... > I am writing a simple proxy server ... > > I redirect my browser to the local server

Writing an NLP System in Python
My First time here, I am trying to write a program in python that can parse simple sentences like: ''I need a train from London to Brighton'' and get a query response from a database. Can anyone help me begin this task by suggesting what components I will need to look at. I am learning python, for the first time, and would be grateful for any help. Thanks A.T. _________________________________________________________________ Get Hotmail on your mobile phone http://www.msn.co.uk/msnmobile you can have a look at http://nltk.sourceforge.net it seems very nice but it ca

Writing Data to BIOS.
How do i write data to BIOS frm Windows.Any programs for that in C. Thanks in Adv. Shyam.

J2ME Open file for writing
Hi to all! At the moment I'm using the API that hasn't got FileConnection class, so I'm using OutputStream o = ((OutputConnection)Connector.open( "file:///root1/file" )).openOutputStream(); I don't know if I have some typos, but it doesn't matter. It works for files that already exist but there are several problems: 1. If the file doesn't exist, it won't create it. I saw thew way people do it by using FileConnection, but I don't have it. What's the way around? 2. If the file is bigger than the content I'm writing, only the part of it is overwritten. What I would like is the "truncate" behaviour, meaning the file should be truncated the moment it's open for writing. 3. How do I delete the file later, once I don't need it? Thank you in advance, I'm waiting by the computer for the answer :) [just kidding :] Darko Since noone has answered on my question, does anybody have an idea where else should I put the question? Sun forum? Other Usenet group? Somewhere else? Thanks, Darko Darko wrote > Hi to all! > > At the moment I'm using the API that hasn't got FileConnection class, > so I

Sockets, writing data and shutdownOutput
My client connects to an HTTP server by opening a socket, starting a separate thread to feed it with data and reading the response in the main thread. The feeder thread basically does this: OutputStream out = socket.getOutputStream(); out.write(...); out.flush(); socket.shutdownOutput(); Problem: roughly half of the time the server resets the connection before sending its response? I use the shutdownOutput to make sure the server understands that we are done and no more data can be expected, but it seems that it overinterpretes it as if my client is not interested in pending respons

Writing to depth buffer 147247
Hi! I'm writing an application which needs to write depth information to the depth buffer. AFAIK is there no linear mapping from depth to the value, I must write to the buffer. Therefore: How can I compute the depth buffer-value from the depth value? thx Markus Doerschmidt Markus D�rschmidt wrote: > Hi! > > I'm writing an application which needs to write depth information to the > depth buffer. AFAIK is there no linear mapping from depth to the value, I > must write to the buffer. Therefore: How can I compute the depth > buffer-value from the depth value? > It's not easy... You could use gluProject() to generate a table of depth values to use as a base for a table based lookup. -- <\___/> For email, remove my socks. / O O \ \_____/ FTB. The Cheat is not dead! On Mon, 8 Nov 2004 08:46:23 +0100, "Markus D�rschmidt" <markus.doerschmidt@gmx.de> wrote: >I'm writing an application which needs to write depth information to the >depth buffer. AFAIK is there no linear mapping from depth to the value, I >must write to the buffer. Therefore: How can I compute the depth >buffer-value