Generating strings based on pattern

[dhinakar_ve]

Hi All,
I am writing a function to generate the strings based on a
pattern. For example A[1-3] will generate A1, A2 and A3. If the
pattern is A[1-3][1-2] then it will generate the strings A11, A12,
A21, A22, A31, A32. What is the best algorithm to accomplish this?

Thanks for your time.

ananihdv

 

[Walter Roberson]

I am writing a function to generate the strings based on a
pattern. For example A[1-3] will generate A1, A2 and A3. If the
pattern is A[1-3][1-2] then it will generate the strings A11, A12,
A21, A22, A31, A32. What is the best algorithm to accomplish this?

That's an algorithm question, not a C question.

*One* algorithm is:

For each position, construct a string which lists each of the
allowed characters at that position. Create an array of these
strings, say char *PosChars[NumPositions].
Allocate an integral array, PosIdx, which is as long as the number of
positions. The integral type needs to be as wide enough to
count the maximum number of different characters allowed at any
given position. If you aren't using multibyte characters,
unsigned char PosIdx[NumPositions] should do. Initialize each
element of the PosIdx array to 0.

Outer Loop

For J over all the position indices: output PosChars[PosIdx[J]]
Output the string seperator (e.g., newline)

Let J be the last position index

Inner Loop:

Increment PosIdx[J]
If PosChars[PosIdx[J]] is the nul character (0)
Reset PosIdx[J] to the first index
Decrement J
If J is less than 0, the program is finished
Otherwise, allow the next iteration of the inner loop
Otherwise, if the character was not nul, terminate the inner loop

End of Inner Loop

Allow the next iteration of the outer loop

End of Outer Loop


I don't know who first invented this single-index algorithm
(a typical algorithm for working with N different positions involves
N nested FOR loops.) As far as I *remember*, I didn't read it anywhere
before I (re-?) invented it in late 2005 or early 2006. But it's
too useful of a technique for me to believe that I got there first.
Perhaps one of the other readers will have a reference for the
technique. (As the technique is not immediately obvious, you should
be crediting -someone- for the algorithm if you use it.)

 

[Chris Torek]

*One* algorithm is: [snipped]
(As the technique is not immediately obvious, you should
be crediting -someone- for the algorithm if you use it.)

I like to think of it as an odometer.

An ordinary odometer of N decimal digits increments thus:

/*
* Increment an "ndigits"-digit decimal odometer whose values
* are in odo[0] through odo[ndigits-1]. Return 0 on
* success, nonzero if the odometer has rolled over to
* all-zeros again.
*/
int odo_increment(int *odo, size_t ndigits) {
size_t i;

for (i = ndigits - 1;; i--) {
if (++odo <= 9)
break;
odo = 0;
if (i == 0)
return -1; /* overflow -- odometer is all 0s again */
}
return 0; /* success */
}

It is not too difficult to adapt this to "odometers" using something
other than "decimal digits". The key observation, of course, is
that we simply increment the least-significant "digit" until it
overflows, then reset it to zero and increment next-most significant
digit, and so on -- exactly like an old-style mechanical odometer.

 

[Walter Roberson]

It is not too difficult to adapt this to "odometers" using something
other than "decimal digits". The key observation, of course, is
that we simply increment the least-significant "digit" until it
overflows, then reset it to zero and increment next-most significant
digit, and so on -- exactly like an old-style mechanical odometer.

Yes, exactly, that's a very nice way of thinking about the
algorithm!

Any idea where it originated? Or is it old enough that we could
start a new urban legend that it Admiral Grace Hooper, coiner
of the term "bug" ?

http://www.sugarforge.org/users/gracie/

 

[Richard Harter]

On Mon, 20 Aug 2007 18:05:04 +0000 (UTC),

Yes, exactly, that's a very nice way of thinking about the
algorithm!

Any idea where it originated? Or is it old enough that we could
start a new urban legend that it Admiral Grace Hooper, coiner
of the term "bug" ?

She probably did it, but I rather imagine that it predates
computers - it's the obvious way to map cartesian products into
one dimension. I recall using it in Fortran II which was quite
some time ago.