OpenEuphoria

Re: Permutation function

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

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 <EUforum at topica.com>
>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
> >
> >-- code --
> >function GetPermutations( sequence characters, atom len )
> > sequence final, combo
> > integer chars
> > atom doit doit = 1
> > final = {}
> > combo = repeat(1, len)
> > chars = length(characters)
> > while doit do
> > final = append(final, combo)
> > combo[1] += 1
> > for i = 1 to len do
> > if combo[i] > chars then
> > if i = len then
> > combo[i] = chars
> > final = append(final, combo)
> > doit = 0
> > exit
> > else
> > combo[i..i+1] = {1, combo[i+1]+1}
> > end if
> > end if
> > end for
> > end while
> > for i = 1 to length(final) do
> > for p = 1 to length(final[i]) do
> > final[i][p] = characters[final[i][p]]
> > end for
> > end for
> > return final
> >end function
> >-- code --
> >
> >---
> >
> >
<snip>

>
>