combinations listing

[Michael Linfield]

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!

 

[Shuaib Zahda]

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

 

[Daniel Sheppard]

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.
=20

puts "Word: "
word =3D gets.chomp
res =3D 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=20
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]

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]

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]

Others have already shown you how you can generate all permutations of a
sequence without having to type all possible ones.

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. You only need @@
if you want some value to be shared by all instances of a given class.

Sorry if that was actually your intent.

mortee

 

[Brian Adkins]

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]

RnJvbTogbW9ydGVlIFttYWlsdG86bW9ydGVlLmxpc3RzQGthdmVtYWxuYS5odV0gDQojIEhvd2V2
ZXIsIEknZCBhc2sgd2h5IGFyZSB5b3UgdXNpbmcgY2xhc3MgdmFyaWFibGVzDQojIChvbmVzIHN0
YXJ0aW5nIHdpdGggQEApPyBBdCBsZWFzdCBpbiBpdHMgY3VycmVudCBmb3JtLCANCiMgeW91ciBz
b2x1dGlvbiBzZWVtcyBxdWl0ZSBwcm9jZWR1cmFsLCBzbyBpdCBzZWVtcyBsaWtlDQojIHNpbXBs
ZSBsb2NhbCB2YXJpYWJsZXMgd291bGQgc3VmZmljZS4NCg0Kbm9wZS4gb3V0c2lkZSBsb2NhbHMg
d29udCBiZSB2aXNpYmxlIGluc2lkZSBtZXRob2RzLg0KDQo+IHg9MQ0KPT4gMQ0KPiBkZWYgdGVz
dA0KPiAgIHAgeA0KPiBlbmQNCj0+IG5pbA0KPiB0ZXN0DQpOYW1lRXJyb3I6IHVuZGVmaW5lZCBs
b2NhbCB2YXJpYWJsZSBvciBtZXRob2QgYHgnIGZvciBtYWluOk9iamVjdA0KDQo+IEBAeD0xDQo9
PiAxDQo+IGRlZiB0ZXN0DQo+ICAgcCBAQHgNCj4gZW5kDQo9PiBuaWwNCj4gdGVzdA0KMQ0KPT4g
bmlsDQoNCg0KIyBZb3Ugb25seSBuZWVkIEBAIGlmIHlvdSB3YW50IHNvbWUgdmFsdWUgdG8gYmUg
c2hhcmVkIGJ5IGFsbA0KIyBpbnN0YW5jZXMgb2YgYSBnaXZlbiBjbGFzcy4NCg0Kc29tZXRpbWVz
IGkgdXNlIGl0IGluIHBsYWNlIG9mIGNvbnN0YW50cyBvciBnbG9iYWxzIChzaW5jZSBjb25zdGFu
dHMgZ2l2ZSB3YXJuaW5ncyBhbmQgZ2xvYmFscyBhcmUuLi4gZ2xvYWJsZXMgOikNCg0Ka2luZCBy
ZWdhcmRzIC1ib3RwDQoNCg==

 

[Michael Linfield]

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

 

[Brian Adkins]

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]

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

 

[Brian Adkins]

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

There are probably better ways to do this, but the first thing that
popped into my head was the following:

Create a hash with the key being a string containing the letters of a
dictionary word in sorted order and the value being an array of words
sharing that key.

Then simply take the anagram, sort the letters and do a hash lookup to
get all the words that share the same letters.

Alternatively, create an array of pairs with the first element being
the string of sorted letters and the second element being the word and
do a binary search with the sorted anagram.

So, the "alphabetically" clue was this sorting technique.

HTH

Brian Adkins

 

[Brian Adkins]

Program 1: create the hash and dump to disk for future use

words = Hash.new([])

File.open("dictionary.txt", "r") do |file|
while line = file.gets
word = line.chomp
words[word.split('').sort!.join('')] += [word]
end
end

File.open("word_hash", "w") do |file|
Marshal.dump(words, file)
end

Program 2: load the hash from disk to solve anagrams

words = nil

File.open("word_hash", "r") do |file|
words = Marshal.load(file)
end

while true
print "Enter word: "
anagram = gets.chomp
sorted_anagram = anagram.split('').sort!.join('')
p words[sorted_anagram]
end
---

This is pretty darn fast, so unless your dictionary is huge, I'd
probably skip the step of partitioning the dictionary by word size. I
used a 70K word dictionary and the dumped hash was 1.5MB.

Since strings are mutable in Ruby, I tried sorting the string using a
quicksort algorithm instead of "split, sort, join", but since the
former was in Ruby and the latter mostly in C, the latter is *much*
faster. This speed disparity encourages taking an indirect route at
times.

Maybe some C extension guru can supply an example of extending the
String class with a sort! method

Brian Adkins

 

[Michael Linfield]

Thanks Brian, after testing out one of the 2 methods i get better
results...I was going to use your permutation method but i get a
localjumperror, I'll have to look into it more because i generally just
glanced at the define:

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

################ None-the-less here is what i came up with by creating a
faster matching method for larger words.

require 'rubygems'
require 'facets/enumerable'

print "Enter Word: "

input = gets.chomp
modinput = input.split('')
modlength = modinput.size

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

file.delete_if {|x| x.size - 1 > modlength}

res = []
puts "Finding All Possible Combinations..."
modinput.each_permutation {|word| res << word.join}

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

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

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

You'll have to explain your method a little more in-depth to me, haha,
got confused a bit from that last post.

Thanks a ton btw.

Oh, one other question, if i wanted to benchmark this entire program in
1 clean sweep how would i do it, id like to compare the before and after
methods to see if they are in fact actually making a dent. With words
such as alphabetically i still have the issue of the overhaul on ram
creating billions of permutation possibilities lol.

 

[Michael Linfield]

I know this post is getting long so ill try to wrap things up with a
last question haha, ur post above kind of inspired me to change my
version to write the permutations to a file rather than memory.

require 'rubygems'
require 'facets/enumerable'

print "Enter Word: "

input = gets.chomp
modinput = input.split('')
modlength = modinput.size

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

file.delete_if {|x| x.size - 1 > modlength}
stuff = File.new("wordhash.txt","w+")

puts "Finding All Possible Combinations..."

modinput.each_permutation {|word| stuff.puts word.join}

store = File.open("wordhash.txt","r")
res = []
store.each {|c| res << c}

res.inspect

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

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

Works fine expect the results are screwd because the output is as
follows for a res.inspect

[\"rdow\\n\"] #just using a brief example ... this would be 1 element
for the anagram of "word"...

Now theoretically i could do a res.collect! but thats getting sloppy
doing that too much so is there any way to strip off the \'s?

Thanks!

 

[Brian Adkins]

Thanks Brian, after testing out one of the 2 methods i get better
results...I was going to use your permutation method but i get a
localjumperror, I'll have to look into it more because i generally just
glanced at the define:

You need to pass in a block.

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

...
Oh, one other question, if i wanted to benchmark this entire program in
1 clean sweep how would i do it, id like to compare the before and after
methods to see if they are in fact actually making a dent. With words
such as alphabetically i still have the issue of the overhaul on ram
creating billions of permutation possibilities lol.

Creating all possible permutations is the wrong approach. See my other
post.

 

[Michael Linfield]

Alright I'd have to say im amazed at the speed....now my question
remains how does it all work lol?

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

words = Hash.new([])

File.open("dict1.txt", "r") do |file| #opens the dictionary file
while line = file.gets #sets line equal to all the data in
the file
word = line.chomp #knocks the \n's off the words
words[word.split('').sort!.join('')] += [word]

#this is the one im hazy about
#it splits every letter in the file, sorts it alphabetically, joins them
all #together to form one long continuous line of letters, and combines
that to the #words pulled from the dictionary?

end
end

File.open("word_hash", "w") do |file| #creates a new file named
word_hash
Marshal.dump(words, file) #writes the output from the words hash to
the file?
end

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

words = nil #makes the words hash equal to nothing

File.open("word_hash", "r") do |file| #loads the data
words = Marshal.load(file)
end

while true
print "Enter word: "
anagram = gets.chomp
sorted_anagram = anagram.split('').sort!.join('') #sorts it the same
way as #the words hash?

p words[sorted_anagram]
end

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

I think the part im confused about is how the sorting actually works in
terms of not so much 'how it works' but 'why it works'.

Sorry to keep this running lol but I'd rather walk away knowing the code
rather than saying 'screw it, it works, im happy' if u know what i mean.

Thanks a ton!

 

[Jesús Gabriel y Galán]

Alright I'd have to say im amazed at the speed....now my question
remains how does it all work lol?

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

words = Hash.new([])

File.open("dict1.txt", "r") do |file| #opens the dictionary file
while line = file.gets #sets line equal to all the data in
the file

Line is set to each line in the file, not to the whole file. The while
loops through all the lines in the file one at a time.

word = line.chomp #knocks the \n's off the words
words[word.split('').sort!.join('')] += [word]

#this is the one im hazy about
#it splits every letter in the file, sorts it alphabetically, joins them
all #together to form one long continuous line of letters, and combines
that to the #words pulled from the dictionary?

It splits every letter of one word, sorts the letters and joins them
again. Then appends to the array corresponding to the value of the
sorted letters the actual word. For example, if this were the
dictionary file:

abc
acb

for abc:
word.split('') --> %w{a, b, c}
sort --> %w{a, b, c}
join('') --> "abc"
words["abc"] += ["abc"] --> {"abc" --> ["abc"]}

now for acb:
word.split('') --> %w{a, c, b}
sort --> %w{a, b, c}
join('') --> "abc"
words["abc"] += ["acb"] --> {"abc" --> ["abc", "acb"]}

Hope you see how the hash is built. For each set of letters it creates
an array with the words that have those letters.

end
end

File.open("word_hash", "w") do |file| #creates a new file named
word_hash
Marshal.dump(words, file) #writes the output from the words hash to
the file?

Yes, serializes the hash to a file in binary form: fast to convert
back to a hash.

end

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

words = nil #makes the words hash equal to nothing

File.open("word_hash", "r") do |file| #loads the data
words = Marshal.load(file)
end

Here's where the serliazed hash is brought back to life.

while true
print "Enter word: "
anagram = gets.chomp
sorted_anagram = anagram.split('').sort!.join('') #sorts it the same
way as #the words hash?

Yes, to obtain the key to the hash --> "abc"

p words[sorted_anagram]
end

Hope this helps,

Jesus.

 

[Dirk Traulsen]

Am 21 Oct 2007 um 7:20 hat Jes=FAs Gabriel y Gal=E1n geschrieben:

It splits every letter of one word, sorts the letters and joins them
again. Then appends to the array corresponding to the value of the
sorted letters the actual word. For example, if this were the
dictionary file:

abc
acb

for abc:
word.split('') --> %w{a, b, c}

Be careful:
p %w(a, b, c) #=3D> ["a,", "b,", "c"]
p %w(a b c) #=3D> ["a", "b", "c"]

When using %w() (=3Darray of tokens) the tokens are separated by spaces.
If you additionally use commas, they will be part of the strings.

Oh, and the delimiter can be any character, so look at this:
p %w-(a bc de)- #=3D> ["(a", "bc", "de)"]
p %w_a(0) { [a(0) bc]}_ #=3D> ["a(0)", "{", "[a(0)", "bc]}"]

Dirk

 

[Jesús Gabriel y Galán]

Am 21 Oct 2007 um 7:20 hat Jes=FAs Gabriel y Gal=E1n geschrieben:

It splits every letter of one word, sorts the letters and joins them
again. Then appends to the array corresponding to the value of the
sorted letters the actual word. For example, if this were the
dictionary file:

abc
acb

for abc:
word.split('') --> %w{a, b, c}

Be careful:
p %w(a, b, c) #=3D> ["a,", "b,", "c"]
p %w(a b c) #=3D> ["a", "b", "c"]

When using %w() (=3Darray of tokens) the tokens are separated by spaces.
If you additionally use commas, they will be part of the strings.

Yeah, you are right. It was just lazy typing on my part to explain
what each part of the program was doing.

Thanks for correcting that,

Jesus.