1. RE: Permutation function
- Posted by thomas at columbus.rr.com Nov 12, 2002
- 370 views
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
- 377 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>
3. RE: Permutation function
- Posted by rforno at tutopia.com Nov 12, 2002
- 369 views
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
- 361 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> > > > >
5. RE: Permutation function
- Posted by mistertrik at hotmail.com Nov 13, 2002
- 368 views
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> > >