Combinations listing

ruby-talk
1

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 :frowning:
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-forum.com/.

2

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-forum.com/.

3

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.

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

···

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]}"

5

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 }

···

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.

6

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

Michael Linfield 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]}"

  #THE LIST GOES ON :frowning:
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!

7

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.

···

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 }

8

# 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 :slight_smile:

kind regards -botp

···

From: mortee [mailto:mortee.lists@kavemalna.hu]

9

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-forum.com/.

10

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

···

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

11

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-forum.com/\.

12

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

Brian Adkins

13

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

···

On Oct 19, 3:38 pm, Michael Linfield <globyy3...@hotmail.com> wrote:

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

14

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.
--
Posted via http://www.ruby-forum.com/.

15

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!
--
Posted via http://www.ruby-forum.com/.

16

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.

···

On Oct 19, 9:25 pm, Michael Linfield <globyy3...@hotmail.com> wrote:

17

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!
--
Posted via http://www.ruby-forum.com/.

18

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.

···

On 10/20/07, Michael Linfield <globyy3000@hotmail.com> wrote:

19

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

When using %w() (=array 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)- #=> ["(a", "bc", "de)"]
p %w_a(0) { [a(0) bc]}_ #=> ["a(0)", "{", "[a(0)", "bc]}"]

Dirk

···

Am 21 Oct 2007 um 7:20 hat Jesús Gabriel y Galán 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}

20

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.

···

On 10/21/07, Dirk Traulsen <dirk.traulsen@lypso.de> wrote:

Am 21 Oct 2007 um 7:20 hat Jesús Gabriel y Galán 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) #=> ["a,", "b,", "c"]
p %w(a b c) #=> ["a", "b", "c"]

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