OpenEuphoria

RE: Permutation function

• Posted by favreje at yahoo.com Nov 12, 2002
• 376 views

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. 


mistertrik at hotmail.com wrote:
> 
> 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)
<snip>