1. RE: Permutation function
Aha! I found the original message (from favreje at yahoo.com):
<snip>
Hello gang - I'm new to the list (and to Eu as well). I'm looking for
an efficient (couldn't be any less efficient than the one I came up
with) algorithm to produce all possible permutations of a given sequence
for a word-game library that I'm working on. I'm not a mathematician,
and only have limited coding experience, but I do enjoy writing "hobby"
projects in Euphoria.
Anyone?
__Jeff__
</snip>
---
2. RE: Permutation function
- Posted by favreje at yahoo.com
Nov 12, 2002
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>
3. RE: Permutation function
- Posted by rforno at tutopia.com
Nov 12, 2002
Hi!
You get a function that returns permutation number n of x objects taken from
z objects. It is found in the Euphoria archives in the package "General
Functions" I submitted to Rob.
Regards.
----- 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.
>
>
> 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>> > fo!
> r !
>
>
>
4. RE: Permutation function
- Posted by rforno at tutopia.com
Nov 12, 2002
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>
>
>
>
>
5. RE: Permutation function
I dissent... this code is more of an anagram solver.
Could the code from the comp do that?
=====================================================
.______<-------------------\__
/ _____<--------------------__|===
||_ <-------------------/
\__| Mr Trick
>From: rforno at tutopia.com
>Subject: RE: Permutation function
>
>
>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>
>To: EUforum <EUforum at topica.com>
>Sent: Wednesday, November 13, 2002 1:02 AM
>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
<snip>
>
>
