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?
On Sun, May 4, 2008 at 2:39 PM, Nadim K. [email protected] 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?
What is a combination?
Hi –
On Sun, 4 May 2008, Nadim K. wrote:
combination == cow, which means the combination would be “hello”.
str = ‘a’
=> “a”cow = “hello”
=> “hello”str.succ! until str == cow
=> nilstr
=> “hello”
David
David A. Black wrote:
Hi –
On Sun, 4 May 2008, Nadim K. wrote:
combination == cow, which means the combination would be “hello”.
str = ‘a’
=> “a”cow = “hello”
=> “hello”str.succ! until str == cow
=> nilstr
=> “hello”David
That unfortunately does not suit my puropose. What if the bunny array
included numbers and symbols as well as uppercase letters?
Xavier N. 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”.
On May 4, 8:50 am, Nadim K. [email protected] wrote:
combination == cow, which means the combination would be “hello”.
Posted viahttp://www.ruby-forum.com/.
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
Nadim K. 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”?
On 04.05.2008 14:50, Nadim K. wrote:
combination == cow, which means the combination would be “hello”.
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
Nadim K. wrote:
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