[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

combinations listing

Michael Linfield

10/18/2007 3:48:00 AM

Making an form of an anagram solver. My approach would be the code
listed below but there has to be a cleaner way to do it.

################


puts "Word: "
@@word = gets.chomp
@@res = @@word.split('')

def letters5
letters5 = @letters5
puts "Displaying All Possible Solutions..."
puts "####################################"
@@res = @@word.split('')

puts "#{@@res[0]}#{@@res[1]}#{@@res[2]}#{@@res[3]}#{@@res[4]}"
puts "#{@@res[1]}#{@@res[0]}#{@@res[2]}#{@@res[3]}#{@@res[4]}"
puts "#{@@res[2]}#{@@res[1]}#{@@res[0]}#{@@res[3]}#{@@res[4]}"
puts "#{@@res[3]}#{@@res[1]}#{@@res[2]}#{@@res[0]}#{@@res[4]}"
puts "#{@@res[1]}#{@@res[4]}#{@@res[2]}#{@@res[3]}#{@@res[0]}"
puts "#{@@res[1]}#{@@res[2]}#{@@res[0]}#{@@res[3]}#{@@res[4]}"
puts "#{@@res[1]}#{@@res[3]}#{@@res[2]}#{@@res[0]}#{@@res[4]}"

#THE LIST GOES ON :(
end




if @@res.length == 5
letters5
end


##################

As you can imagine this would take me a ridiculous amount of time for
words that are 7 characters or longer...

Any ideas?

Thanks!
--
Posted via http://www.ruby-....
19 Answers

Shuaib Zahda

10/18/2007 4:03:00 AM

0

Michael Linfield wrote:

use nested loops and counters, you need to do some control to the value
of the counter so as to get the proper output.
I wish this comment will help

--
Posted via http://www.ruby-....

Daniel Sheppard

10/18/2007 4:52:00 AM

0

> Making an form of an anagram solver. My approach would be the code
> listed below but there has to be a cleaner way to do it.
>

> puts "Word: "
> word = gets.chomp
> res = word.split('')

require 'facet/enumerable/permutation'

res.each_permutation do |perm|
puts perm.join
end

(You'll need to install facets first - gem install facets)

> As you can imagine this would take me a ridiculous amount of time for
> words that are 7 characters or longer...

And you're going to get just as much output. You're probably best
iterating
over a dictionary word list rather than iterating over the possible word
list.
A 12 letter word is going to have 1/2 a billion possible permutations,
but
you'll struggle to find a dictionary with much more than 1/2 million
actual
words.

Dan.

Phrogz

10/18/2007 5:18:00 AM

0

On Oct 17, 9:48 pm, Michael Linfield <globyy3...@hotmail.com> wrote:
> Making an form of an anagram solver. My approach would be the code
> listed below but there has to be a cleaner way to do it.
>
> ################
>
> puts "Word: "
> @@word = gets.chomp
> @@res = @@word.split('')
>
> def letters5
> letters5 = @letters5
> puts "Displaying All Possible Solutions..."
> puts "####################################"
> @@res = @@word.split('')
>
> puts "#{@@res[0]}#{@@res[1]}#{@@res[2]}#{@@res[3]}#{@@res[4]}"
> puts "#{@@res[1]}#{@@res[0]}#{@@res[2]}#{@@res[3]}#{@@res[4]}"
> puts "#{@@res[2]}#{@@res[1]}#{@@res[0]}#{@@res[3]}#{@@res[4]}"
> puts "#{@@res[3]}#{@@res[1]}#{@@res[2]}#{@@res[0]}#{@@res[4]}"
> puts "#{@@res[1]}#{@@res[4]}#{@@res[2]}#{@@res[3]}#{@@res[0]}"
> puts "#{@@res[1]}#{@@res[2]}#{@@res[0]}#{@@res[3]}#{@@res[4]}"
> puts "#{@@res[1]}#{@@res[3]}#{@@res[2]}#{@@res[0]}#{@@res[4]}"

Slim2:~/Code phrogz$ sudo gem install facets
Successfully installed facets-2.0.2

Slim2:~/Code phrogz$ irb
irb(main):001:0> require 'rubygems'
=> true
irb(main):002:0> require 'facets/enumerable'
=> true
irb(main):005:0> letters = 'neato'.split('')
=> ["n", "e", "a", "t", "o"]
irb(main):007:0> letters.each_permutation{ |word| p word.join }
"otaen"
"otane"
"otean"
"otnae"
"otena"
"otnea"
"oaten"
"oatne"
"oetan"
"ontae"
"oetna"
"ontea"
"oaetn"
"oante"
"oeatn"
"onate"
"oenta"
"oneta"
"oaent"
"oanet"
"oeant"
"onaet"
"oenat"
"oneat"
"toaen"
"toane"
"toean"
"tonae"
"toena"
"tonea"
"aoten"
"aotne"
"eotan"
"notae"
"eotna"
"notea"
"aoetn"
"aonte"
"eoatn"
"noate"
"eonta"
"noeta"
"aoent"
"aonet"
"eoant"
"noaet"
"eonat"
"noeat"
"taoen"
"taone"
"teoan"
"tnoae"
"teona"
"tnoea"
"atoen"
"atone"
"etoan"
"ntoae"
"etona"
"ntoea"
"aeotn"
"anote"
"eaotn"
"naote"
"enota"
"neota"
"aeont"
"anoet"
"eaont"
"naoet"
"enoat"
"neoat"
"taeon"
"tanoe"
"teaon"
"tnaoe"
"tenoa"
"tneoa"
"ateon"
"atnoe"
"etaon"
"ntaoe"
"etnoa"
"nteoa"
"aeton"
"antoe"
"eaton"
"natoe"
"entoa"
"netoa"
"aenot"
"aneot"
"eanot"
"naeot"
"enaot"
"neaot"
"taeno"
"taneo"
"teano"
"tnaeo"
"tenao"
"tneao"
"ateno"
"atneo"
"etano"
"ntaeo"
"etnao"
"nteao"
"aetno"
"anteo"
"eatno"
"nateo"
"entao"
"netao"
"aento"
"aneto"
"eanto"
"naeto"
"enato"
"neato"
=> 0

Brian Adkins

10/18/2007 6:09:00 AM

0

On Oct 17, 11:48 pm, Michael Linfield <globyy3...@hotmail.com> wrote:
> Making an form of an anagram solver. My approach would be the code
> listed below but there has to be a cleaner way to do it.

As others have mentioned, simply generating all permutations may not
be the best way to solve an anagram, but here's a recursive
permutation generator:

def words chars, result='', &b
if chars.empty?
yield result
else
chars.length.times do |i|
c = (x = chars.clone).slice!(i)
words(x, result + c, &b)
end
end
end

word = 'dog';
words(word.split('')) {|s| puts s }

mortee

10/18/2007 3:44:00 PM

0

Brian Adkins

10/18/2007 4:52:00 PM

0

On Oct 18, 2:08 am, Brian Adkins <lojicdot...@gmail.com> wrote:
> On Oct 17, 11:48 pm, Michael Linfield <globyy3...@hotmail.com> wrote:
>
> > Making an form of an anagram solver. My approach would be the code
> > listed below but there has to be a cleaner way to do it.
>
> As others have mentioned, simply generating all permutations may not
> be the best way to solve an anagram, but here's a recursive
> permutation generator:
>
> def words chars, result='', &b
> if chars.empty?
> yield result
> else
> chars.length.times do |i|
> c = (x = chars.clone).slice!(i)
> words(x, result + c, &b)
> end
> end
> end
>
> word = 'dog';
> words(word.split('')) {|s| puts s }

I was curious about the code using the facets gem, so I ran a few
benchmarks. The above naive recursive code is over 3 times faster on
an 8 character word. I'm sure this is due in part to the above code
being quite specific and the facets code needing to be more general,
but that still seems like a large factor.

Peña, Botp

10/19/2007 4:59:00 AM

0

From: mortee [mailto:mortee.lists@kavemalna.hu]
# However, I'd ask why are you using class variables
# (ones starting with @@)? At least in its current form,
# your solution seems quite procedural, so it seems like
# simple local variables would suffice.

nope. outside locals wont be visible inside methods.

> x=1
=> 1
> def test
> p x
> end
=> nil
> test
NameError: undefined local variable or method `x' for main:Object

> @@x=1
=> 1
> def test
> p @@x
> end
=> nil
> test
1
=> nil


# You only need @@ if you want some value to be shared by all
# instances of a given class.

sometimes i use it in place of constants or globals (since constants give warnings and globals are... gloables :)

kind regards -botp

Michael Linfield

10/19/2007 6:01:00 AM

0

Thanks all ----

Final Result:

##############################

require 'rubygems'
require 'facets/enumerable'

puts "###################################"
puts "### Anagram Solver ###"
puts "###################################"

print "Enter Word: "
letters = gets.chomp
modletters = letters.split('')
res = []

modletters.each_permutation {|word| res << word.join}
puts "Finding All Possible Combinations..."


file = open('dict1.txt') {|p| p.readlines}
dict = []
file.each {|p| dict << p}

res.collect! {|c| c + "\n"}

puts "Finished."
puts "Solution: #{res&dict}"

######################################

How accurate it is depends on the dictionary, i used an 8mb password
dictionary so the common issue is that it comes up with garble words in
the list of solutions sometimes, and sometimes spells the word
backwards, but none-the-less the word im looking for is always there.

Feel free to improve it if you see a flaw or a better way of doing it

--
Posted via http://www.ruby-....

Brian Adkins

10/19/2007 4:13:00 PM

0

On Oct 19, 2:01 am, Michael Linfield <globyy3...@hotmail.com> wrote:
> Thanks all ----
>
> Final Result:
>
> ##############################
>
> require 'rubygems'
> require 'facets/enumerable'
>
> puts "###################################"
> puts "### Anagram Solver ###"
> puts "###################################"
>
> print "Enter Word: "
> letters = gets.chomp
> modletters = letters.split('')
> res = []
>
> modletters.each_permutation {|word| res << word.join}
> puts "Finding All Possible Combinations..."
>
> file = open('dict1.txt') {|p| p.readlines}
> dict = []
> file.each {|p| dict << p}
>
> res.collect! {|c| c + "\n"}
>
> puts "Finished."
> puts "Solution: #{res&dict}"
>
> ######################################
>
> How accurate it is depends on the dictionary, i used an 8mb password
> dictionary so the common issue is that it comes up with garble words in
> the list of solutions sometimes, and sometimes spells the word
> backwards, but none-the-less the word im looking for is always there.
>
> Feel free to improve it if you see a flaw or a better way of doing it

Can your program solve this anagram (a very common word)?
"aaabcehilllpty"

It might take a while. The word provides a hint (in two separate ways)
for an improvement.

Using my code from another post will speed up the permutation
generation by a factor of 3, but that is no match for an O(n!)
algorithm. I think you'll need a new technique for longer words.

Also, since the anagram and the actual word must be the same length to
match, you can partition the dictionary by word size. That and the
hint above should get you a long way down the road.

Brian Adkins

Michael Linfield

10/19/2007 7:38:00 PM

0

Brian Adkins wrote:

>> Feel free to improve it if you see a flaw or a better way of doing it
>
> Can your program solve this anagram (a very common word)?
> "aaabcehilllpty"
>
> It might take a while. The word provides a hint (in two separate ways)
> for an improvement.
>
> Using my code from another post will speed up the permutation
> generation by a factor of 3, but that is no match for an O(n!)
> algorithm. I think you'll need a new technique for longer words.
>
> Also, since the anagram and the actual word must be the same length to
> match, you can partition the dictionary by word size. That and the
> hint above should get you a long way down the road.
>
> Brian Adkins

Alright i see your point lol, so are you suggesting that the actual
dictionaries be split up? in a sense of...

word = "foobar"
res = word.split('')

if res.size > 3
#use dictionary 1
end

if res.size > 6
#use dictionary 2
end

ect...

one way or another, the only speed issue here is generating the
permutations, searching the dictionary is pretty quick from what ive
seen.
The clue was alphabetically, sadly i didnt want to wait for my program
to finish that lol. I'm kind of hazy as to what that clue might suggest,
my interpretation is to possibly grep out all the words that are of the
same length as the word entered.

word = gets.chomp
res = word.split('')
size = res.length
# so now size would equal 14 if you used the word 'alphabetically'

file = open('dict1.txt') {|p| p.readlines}
dict = []
#when statement that shoves all words = to 14 into the dict array
end
--
Posted via http://www.ruby-....