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> > >