OpenEuphoria

RE: Permutation function

• Posted by rforno at tutopia.com Nov 12, 2002
• 362 views

The last contest in Euphoria was exactly on this subject (at least the
intermediate difficulty one): find all English words with a pattern (with
more options than the ones you wish).
----- Original Message -----
From: <favreje at yahoo.com>
Subject: RE: Permutation function


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