OpenEuphoria

Re: Permutation function

• Posted by mistertrik at hotmail.com Nov 12, 2002
• 408 views

Actually, it's pretty simple.

The problem you have, and that I had at first, was that I'd generate a 
sequence of letters, and then see if it was the same as a word in the 
dictionary. That requires you to do as many compares as there are 
permutations, which is unfeasible.

What is a better idea...

Is look at each word, and see if it can be made from your text string.
My dictionary had 25000 words in it, which is much more palatable than a few 
million, and it can be also simply deduced that a 12 letter word can not be 
made from a 9 letter string, so you can easily split your dictionary up into 
lengths, and only compare sets of words with equal or lesser length. ie for 
a 7 letter string, compare the 7's the 6's the 5's etc....

My main loopset looks similar to this:

dictionary sequence of sequences of sequences (wordlengths, words, letters)
input sequence
blank sequence of sequences for putting valid words into (words, letters)

For each set of words in the dictionary that are <= input word length.
    For each word in the dictionary...
       For each letter in the word...
           Check if the letter is in the input string. 
--find(l[a][b][c],input)
               example: inputstring:weysahj, testword: yes
               if it is not in the inputstring then it can't be made.
               there is no way you can make 'ball' from weysahj, so go to 
the next word.
               if it is, then move to the next letter
       next letter
       if all the letters were valid (did not exit), then that word
       is valid, so add it to the list of words.
   next word
next set

return the sequence of valid words.

There was also checking that the dictionary word didn't contain more 
instances of a letter than the input sequence did. ie... having 'luetrnd' 
and wanting to make 'letter'.

This may make it easier to understand the source code... once I get my hands 
on it and post it.

The best thing about this approach was that it only took a second or two to 
do, even on my p233.

=====================================================
.______<-------------------\__
/ _____<--------------------__|===
||_    <-------------------/
\__| Mr Trick





>From: favreje at yahoo.com
>Reply-To: EUforum at topica.com
>To: EUforum <EUforum at topica.com>
>Subject: Re: Permutation function
>Date: Tue, 12 Nov 2002 19:23:22 -0800 (PST)
>
>
>Thanks Trick... I'd love to see the code you have.  I found a website on 
>permutation theory.  So I'm learning all about cycles, orbits,  and 
>products of transpositions.  It always helps to understand why the code 
>works, eh?
>Seems like the time/space constraints come into play more when I check a 
>given permuation against the dictionary.  But there should be a way to 
>reject entire series, or cycles of permuations outright (maybe based on a 
>hash function) by determining that no english words begin a particular 3 
>letter sequence?  I'm still thinking it through.
>
>
>Well, if they're real words, then I'm guessing you want to know what words
>you can make given the available tiles.
>
>That's exactly what my code does, and a lot more efficiently too. I don't
>care how fast your code is, it takes a while to generate 3.6 million
>permutations, and it uses a lot of space.
>
>If you can wait a few hours, I'll send it to you once I get home.
>=====================================================
>.______<-------------------\__
>/ _____<--------------------__|===
>||_ <-------------------/
>\__| Mr Trick
>
>
> >From: favreje at yahoo.com
> >Reply-To: EUforum at topica.com
> >To: EUforum
> >Subject: Re: Permutation function
> >Date: Tue, 12 Nov 2002 17:53:53 -0800 (PST)
> >
> >
> >Actually, I am generating permutations for the fun of it! (kinda sick,
> >eh?). I'm writing a scrabble-like word-play game (primarily to 
>familiarize
> >myself with Euphoria) that makes matrices of words no longer than 10
> >characters in length. The permutation algorithm supports the computer
> >player's generation of words. (With only 10 characters per word, and a
> >good hash function, I should be able to handle the 3.6 million possible
> >results, right?)
> >
> >
> >I have a funky bit of code at home (at work now) that can find words that
> >can be made from a given sequence of letters.
> >That uses a permutation function of sorts. What is this function wanted
> >for?
> >
> >I remember the first way I went about doing things was to generate a
> >permutation, then try and match it to the dictionary. This is *NOT* a 
>good
> >way of doing things. The number of permutations to word length ramps up
> >VERY
> >quickly. if you have a 15 length sequence, there are roughly 100 billion
> >permutations. Not good.
> >
> >I'm assuming you're not generating permutations for the fun of it. 
>Perhaps
> >you can tell us what this permutation function is for?
> >=====================================================
> >.______<-------------------\__
> >/ _____<--------------------__|===
> >||_ <-------------------/
> >\__| Mr Trick
> >
> >
> > >From: thomas at columbus.rr.com
> > >Reply-To: EUforum at topica.com
> > >To: EUforum
> > >Subject: Permutation function
> > >Date: Tue, 12 Nov 2002 20:12:39 -0500
> > >
> > >
> > >I read an e-mail about somebody looking for permutations.. Sorry, I'm a
> > >bit short on time so I won't have a chance to look for that e-mail or
> > >test out the code thoroughly (though my quick test shows that it 
>works).
> > >Here is a little function that I have been using to find permutations.
> > >You call it with the set of characters you want to be used (ex: {'A',
> > >'B', 'C'} or {'1', '2', '3'}) and the length of each permutation (ex: 
>3,
> > >6, 9).
> > >
> > >It's not the most optimized function in the world, but so far I haven't
> > >had any problems. I was recently working with the code, so it may not
> > >work exactly right (sorry!). I thought if I sent it to the list I could
> > >get some c&c on it. Tell me what you think!
> > >
> > >~Tom
> > >
<snip>

>
>