Generating strings based on pattern

Discussion in 'C Programming' started by dhinakar_ve@yahoo.com, Aug 20, 2007.

  1. Guest

    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
    , Aug 20, 2007
    #1
    1. Advertising

  2. In article <>,
    <> 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
    Walter Roberson, Aug 20, 2007
    #2
    1. Advertising

  3. Chris Torek Guest

    In article <fab6nc$ni2$>
    Walter Roberson <-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 <= 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.
    --
    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.
    Chris Torek, Aug 20, 2007
    #3
  4. In article <>,
    Chris Torek <> wrote:
    >In article <fab6nc$ni2$>
    >Walter Roberson <-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
    Walter Roberson, Aug 20, 2007
    #4
  5. On Mon, 20 Aug 2007 18:05:04 +0000 (UTC),
    -cnrc.gc.ca (Walter Roberson) wrote:

    >In article <>,
    >Chris Torek <> wrote:
    >>In article <fab6nc$ni2$>
    >>Walter Roberson <-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.


    >
    >http://www.sugarforge.org/users/gracie/
    >--
    > Okay, buzzwords only. Two syllables, tops. -- Laurie Anderson
    Richard Harter, Aug 20, 2007
    #5
    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. Replies:
    17
    Views:
    1,832
    Chris Uppal
    Nov 16, 2005
  2. Ben

    Strings, Strings and Damned Strings

    Ben, Jun 22, 2006, in forum: C Programming
    Replies:
    14
    Views:
    732
    Malcolm
    Jun 24, 2006
  3. sunny
    Replies:
    1
    Views:
    446
    Salt_Peter
    Dec 7, 2006
  4. anonym
    Replies:
    1
    Views:
    998
    Knute Johnson
    Jan 15, 2009
  5. Pallav singh
    Replies:
    0
    Views:
    341
    Pallav singh
    Jan 22, 2012
Loading...

Share This Page