Re: Permutation function
- Posted by favreje at yahoo.com
Nov 12, 2002
--0-598390506-1037157802=:58352
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
> >
> >-- 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 --
> >
> >---
> >
> >
>
>
<P>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?
<P>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.
<P> <B><I>mistertrik at hotmail.com</I></B> wrote:
if you have a 15 length sequence, there are roughly 100
billion<BR>>permutations. Not good.<BR>><BR>>I'm assuming you're not
generating permutations for the fun of it. Perhaps<BR>>you can tell us what
this permutation function is
for?<BR>>=====================================================<BR>>.______<-------------------\__<BR>>/
_____<--------------------__|===<BR>>||_
<-------------------/<BR>>\__| Mr Trick<BR>><BR>><BR>> >From:
thomas at columbus.rr.com<BR>> >Reply-To: EUforum at topica.com<BR>>
>To: EUforum<BR>> >Subject: Permutation function<BR>> >Date: Tue,
12 Nov 2002 20:12:39 -0500<BR>> ><BR>> ><BR>> >I read an e-mail
about somebody looking for permutations.. Sorry, I'm a<BR>> >bit short on
time so I won't have a chance to look for that e-mail or<BR>> >test out the
code thoroughly (though my quick test shows that it works).<BR>> >Here is a
little function that I h!
ave been using to find permutations.<BR>> >You call it with the set of
characters you want to be used (ex: {'A',<BR>> >'B', 'C'} or {'1', '2',
'3'}) and the length of each permutation (ex: 3,<BR>> >6, 9).<BR>>
><BR>> >It's not the most optimized function in the world, but so far I
haven't<BR>> >had any problems. I was recently working with the code, so it
may not<BR>> >work exactly right (sorry!). I thought if I sent it to the
list I could<BR>> >get some c&c on it. Tell me what you think!<BR>>
><BR>> >~Tom<BR>> ><BR>> >-- code --<BR>> >function
GetPermutations( sequence characters, atom len )<BR>> > sequence final,
combo<BR>> > integer chars<BR>> > atom doit doit = 1<BR>> >
final = {}<BR>> > combo = repeat(1, len)<BR>> > chars =
length(characters)<BR>> > while doit do<BR>> > final = append(final,
combo)<BR>> > combo[1] += 1<BR>> > for !
|
Not Categorized, Please Help
|
|
