Hey everyone,
I have an array called bunny. I want to check every single combination
of the strings inside bunny against a string called cow and see if it
matches, starting from the smallest combination to the largest, and I
really can't figure out how to do that, I'm completely stuck. Any
pointers, please?
--
Posted via http://www.ruby-forum.com/.
What is a combination?
On Sun, May 4, 2008 at 2:39 PM, Nadim Kobeissi <kaepora@mac.com> wrote:
Hey everyone,
I have an array called bunny. I want to check every single combination
of the strings inside bunny against a string called cow and see if it
matches, starting from the smallest combination to the largest, and I
really can't figure out how to do that, I'm completely stuck. Any
pointers, please?
Nadim Kobeissi wrote:
Hey everyone,
I have an array called bunny. I want to check every single combination
of the strings inside bunny against a string called cow and see if it
matches, starting from the smallest combination to the largest, and I
really can't figure out how to do that, I'm completely stuck. Any
pointers, please?
Hi Nadim,
First, think exactly what "match" means. If it means that cow can be built entirly from some unique
sequence of strings from bunny, selected without replacement then you might do the following.
procedure match(cow, bunny)
sort bunny into decending order by length. (longest first).
loop while length of cow > 0
search for the first string in bunny that begins cow.
if none is found, return (failure to match)
else
record the string that you have matched as part of the answer.
Remove the matched string from start of cow
and remove it from bunny, closing up the gap (so sort order is maintained).
end loop
return (success at matching).
If strings in bunny can be used twice, don't remove them when they match.
If the "match" can skip bits of cow, then you need to define exactly what match means in your
application - how big a gap, how many of bunny's strings may be used, etc.
You may have to search though the whole of the string space generated by bunny, but that could take a very long time.
Regards
Ian
p.s Why the rather unusual names of "cow" and "bunny"?
Xavier Noria wrote:
What is a combination?
Please allow me to make myself more clear:
bunny=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
cow="hello"
I want to test all possible combinations of the items inside bunny (the
alphabet) starting from the smallest to the biggest (a, then b, then c..
then aa, then ab, then ac, etc.) until I arrive to a case in which the
combination == cow, which means the combination would be "hello".
--
Posted via http://www.ruby-forum.com/\.
Hi --
Xavier Noria wrote:
What is a combination?
Please allow me to make myself more clear:
bunny=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
cow="hello"I want to test all possible combinations of the items inside bunny (the
alphabet) starting from the smallest to the biggest (a, then b, then c..
then aa, then ab, then ac, etc.) until I arrive to a case in which the
combination == cow, which means the combination would be "hello".
str = 'a'
=> "a"
cow = "hello"
=> "hello"
str.succ! until str == cow
=> nil
str
=> "hello"
David
On Sun, 4 May 2008, Nadim Kobeissi wrote:
--
Rails training from David A. Black and Ruby Power and Light:
INTRO TO RAILS June 9-12 Berlin
ADVANCING WITH RAILS June 16-19 Berlin
INTRO TO RAILS June 24-27 London (Skills Matter)
See http://www.rubypal.com for details and updates!
You could try a brute-force algorithm, which uses loops to do exactly
what you said: try "a" then "b" then "c", then try "aa", "ab",
"ac"..., then "ba", "bb", etc. String has a succ method which would
be useful for this.
The problem is that the brute-force algorithm will be slow. For the
example given, I think it will take around 26^5 (about 11 million)
iterations before it matches on a string of size 5. If you want a
faster algorithm, I would work backwards from the starting string
"hello".
Wyatt
On May 4, 8:50 am, Nadim Kobeissi <kaep...@mac.com> wrote:
Xavier Noria wrote:
> What is a combination?Please allow me to make myself more clear:
bunny=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
cow="hello"I want to test all possible combinations of the items inside bunny (the
alphabet) starting from the smallest to the biggest (a, then b, then c..
then aa, then ab, then ac, etc.) until I arrive to a case in which the
combination == cow, which means the combination would be "hello".
--
Posted viahttp://www.ruby-forum.com/.
Nadim Kobeissi wrote:
Xavier Noria wrote:
What is a combination?
Please allow me to make myself more clear:
bunny=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
cow="hello"I want to test all possible combinations of the items inside bunny (the alphabet) starting from the smallest to the biggest (a, then b, then c.. then aa, then ab, then ac, etc.) until I arrive to a case in which the combination == cow, which means the combination would be "hello".
I gather that the letter l matchs twice! You only discover that every letter in cow is in bunny.
This yu can go for directly, with a quick algorithm.
Foreach letter in cow
if letter not in bunny
fails match
success!
Ian
I am sorry, but this seems a rather silly approach. All you get as output is the information whether /cow/ can be built using characters in /bunny/. Your approach has at least O(n*n) while it seems there is a much simpler and faster (with O(n)) algorithm available:
irb(main):001:0> require 'set'
=> true
irb(main):002:0> bunny=("a".."z").to_set
=> #<Set: {"v", "k", "w", "l", "a", "x", "m", "b", "y", "n", "c", "z", "o", "d", "p", "e", "q", "f", "r", "g", "s", "h", "t", "i",
u", "j"}>
irb(main):003:0> cow="hello"
=> "hello"
irb(main):004:0> def t(s,chars)
irb(main):005:1> s.scan(/./) {|m| return false unless chars.include? m}
irb(main):006:1> true
irb(main):007:1> end
=> nil
irb(main):008:0> t cow, bunny
=> true
irb(main):009:0> t "___", bunny
=> false
irb(main):010:0>
Kind regards
robert
On 04.05.2008 14:50, Nadim Kobeissi wrote:
Xavier Noria wrote:
What is a combination?
Please allow me to make myself more clear:
bunny=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
cow="hello"I want to test all possible combinations of the items inside bunny (the alphabet) starting from the smallest to the biggest (a, then b, then c.. then aa, then ab, then ac, etc.) until I arrive to a case in which the combination == cow, which means the combination would be "hello".
David A. Black wrote:
Hi --
combination == cow, which means the combination would be "hello".
str = 'a'
=> "a"
cow = "hello"
=> "hello"
str.succ! until str == cow
=> nil
str
=> "hello"
David
That unfortunately does not suit my puropose. What if the bunny array
included numbers and symbols as well as uppercase letters?