Generating strings based on pattern
dhina...@yahoo.com
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
<dhina...@yahoo.com> wrote:
> 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.)
--
All is vanity. -- Ecclesiastes
Chris Torek
Walter Roberson <robe...@ibd.nrc-cnrc.gc.ca> wrote:
>*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[i] <= 9)
break;
odo[i] = 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.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.
Walter Roberson
Chris Torek <nos...@torek.net> wrote:
>In article <fab6nc$ni2$1...@canopus.cc.umanitoba.ca>
>Walter Roberson <robe...@ibd.nrc-cnrc.gc.ca> wrote:
>>*One* algorithm is:
>>(As the technique is not immediately obvious, you should
>>be crediting -someone- for the algorithm if you use it.)
>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/
--
Okay, buzzwords only. Two syllables, tops. -- Laurie Anderson
Richard Harter
robe...@ibd.nrc-cnrc.gc.ca (Walter Roberson) wrote:
>In article <fabed...@news4.newsguy.com>,
>Chris Torek <nos...@torek.net> wrote:
>>In article <fab6nc$ni2$1...@canopus.cc.umanitoba.ca>
>>Walter Roberson <robe...@ibd.nrc-cnrc.gc.ca> wrote:
>>>*One* algorithm is:
>
>>>(As the technique is not immediately obvious, you should
>>>be crediting -someone- for the algorithm if you use it.)
>
>>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" ?
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.