string combination algorithm for a "word descrambler"

Discussion in 'C++' started by gdogg1587, Jan 19, 2005.

  1. gdogg1587

    gdogg1587 Guest

    Greetings.

    I'm working on a program that will "descramble" words. Think of a word
    scramble game where there is a list of characters, and several blank
    spaces to denote the word(s) that you are to come up with from the list.
    i.e.(* denotes a space): _ _ _ _ _ * _ _ _ _ _ _

    characters: .hwodlelrlo

    answer: hello world.

    So, implemented as a c/c++ program, you would have something like:
    <begin pseudo-c code>
    char letters[11] = {'.','h','w','o','d','l','e','l','r','l','o'};

    char PossibleWordOne[100][5];
    char PossibleWordTwo[100][6];
    //WordOneLength = 5;
    //WordTwoLength = 6;
    /* Ultimately, the goal is to not know the number of words or their
    lengths or even the scrambled characters before execution, but this will
    work for the example. I got the 100 because there should be no way of
    getting more than 100 possible 'real' words*/


    /* In order to make sure the combination of characters is a real word,
    verify() will check it against a word list and return True or False Swap
    will be a simple function (I hope it'll be simple anyways) that will swap
    the characters into the next combination.*/

    Permu()
    {
    static int counter = 1;
    static int possibles = 0;
    while (counter != 11!) /* Since there are 11! possible combinations */
    if (!(Verify(Swap(letters*))
    { counter++;
    Permu();
    }
    else
    {
    PossibleWordOne[possibles][] = letters*;
    possibles++;
    counter++;
    Permu();
    }

    <end pseudo-c code>

    Well, what do guys think? Any suggestions or sample code would be greatly
    appreciated. In order to optimize performance, I would like to load the
    word list directly into memory, and preferably have the words categorized
    by length. This way, I can find the possible words for the longest word
    first, and then go to the next longest. For example, let's say that I find
    two possible combinations for the five-letter word. Then, I can seperate
    them into two cases to find the four-letter word. Each case would have a
    char array with 5 less chars than the original, which should make it a lot
    faster to find the second word. Then let's say that only case two turns up
    a possible combination for the four letter word. case one could then be
    disguarded and you could move on to the next word... and on and on.
    Anyways, that's what I've got so far... Like I said any suggestions would
    be greatly appreciated.

    Thanks,
    Gaines
    gdogg1587, Jan 19, 2005
    #1
    1. Advertising

  2. gdogg1587

    David Hilsee Guest

    "gdogg1587" <> wrote in message
    news:...
    > Greetings.
    >
    > I'm working on a program that will "descramble" words. Think of a word
    > scramble game where there is a list of characters, and several blank
    > spaces to denote the word(s) that you are to come up with from the list.
    > i.e.(* denotes a space): _ _ _ _ _ * _ _ _ _ _ _
    >
    > characters: .hwodlelrlo
    >
    > answer: hello world.
    >
    > So, implemented as a c/c++ program, you would have something like:
    > <begin pseudo-c code>
    > char letters[11] = {'.','h','w','o','d','l','e','l','r','l','o'};
    >
    > char PossibleWordOne[100][5];
    > char PossibleWordTwo[100][6];
    > //WordOneLength = 5;
    > //WordTwoLength = 6;
    > /* Ultimately, the goal is to not know the number of words or their
    > lengths or even the scrambled characters before execution, but this will
    > work for the example. I got the 100 because there should be no way of
    > getting more than 100 possible 'real' words*/
    >
    >
    > /* In order to make sure the combination of characters is a real word,
    > verify() will check it against a word list and return True or False Swap
    > will be a simple function (I hope it'll be simple anyways) that will swap
    > the characters into the next combination.*/
    >
    > Permu()
    > {
    > static int counter = 1;
    > static int possibles = 0;
    > while (counter != 11!) /* Since there are 11! possible combinations */
    > if (!(Verify(Swap(letters*))
    > { counter++;
    > Permu();
    > }
    > else
    > {
    > PossibleWordOne[possibles][] = letters*;
    > possibles++;
    > counter++;
    > Permu();
    > }
    >
    > <end pseudo-c code>
    >
    > Well, what do guys think? Any suggestions or sample code would be greatly
    > appreciated. In order to optimize performance, I would like to load the
    > word list directly into memory, and preferably have the words categorized
    > by length. This way, I can find the possible words for the longest word
    > first, and then go to the next longest. For example, let's say that I find
    > two possible combinations for the five-letter word. Then, I can seperate
    > them into two cases to find the four-letter word. Each case would have a
    > char array with 5 less chars than the original, which should make it a lot
    > faster to find the second word. Then let's say that only case two turns up
    > a possible combination for the four letter word. case one could then be
    > disguarded and you could move on to the next word... and on and on.
    > Anyways, that's what I've got so far... Like I said any suggestions would
    > be greatly appreciated.


    I've written a similar program before, just for a laugh. To determine the
    "legal" words that one can make, there's a simple, efficient approach that
    doesn't take too much time to implement. Simply scan the entire list of
    "legal" words, testing if it is a subset of the scrambled letters. This
    tends to be pretty quick (virtually instantaneous on my machine), as there
    are only around 180,000 words in the English language. Then, for each word
    you can make that is of an appropriate length, examine each pair (or
    whatever size tuple) to see if, together, they "use up" all of the scrambled
    letters. Of course, you may have multiple correct answers. For other
    programs, it may pay to try to do something "smarter", but, in my
    experience, nothing fancy is required for a program like this. However, it
    might get out of hand if you had a lot of letters that could make many
    words, and there are many words in the sentence.

    --
    David Hilsee
    David Hilsee, Jan 19, 2005
    #2
    1. Advertising

  3. gdogg1587

    gdogg1587 Guest

    Re: string combination algorithm for a

    Hmm... That's a pretty good idea. 18,000 is a lot less than 11! And a whole
    lot less than 100!. And, I could categorize the word list by length of word
    to make it even faster! That's great! Thanks.
    gdogg1587, Jan 19, 2005
    #3
  4. gdogg1587

    gdogg1587 Guest

    Re: string combination algorithm for a

    Hmm... That's a pretty good idea. 18,000 is a lot less than 11! And a whole
    lot less than 100!. And, I could categorize the word list by length of word
    to make it even faster! That's great! Thanks.
    gdogg1587, Jan 19, 2005
    #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. Ross

    combination algorithm/source code

    Ross, Dec 9, 2004, in forum: C Programming
    Replies:
    2
    Views:
    601
    Richard Bos
    Dec 9, 2004
  2. aka_eu

    Combination problem - fast algorithm

    aka_eu, Apr 28, 2006, in forum: C Programming
    Replies:
    6
    Views:
    449
    Rod Pemberton
    Apr 30, 2006
  3. Replies:
    8
    Views:
    400
    James Kanze
    Jul 29, 2007
  4. sophia

    string combination

    sophia, Apr 15, 2008, in forum: C Programming
    Replies:
    14
    Views:
    601
    santosh
    Apr 19, 2008
  5. Tagore

    combination of a string and queries

    Tagore, Dec 23, 2008, in forum: C Programming
    Replies:
    2
    Views:
    301
    user923005
    Dec 23, 2008
Loading...

Share This Page