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


 

Forums >

comp.lang.ruby

Array combination check

Nadim Kobeissi

5/4/2008 12:40:00 PM

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-....
8 Answers

Xavier Noria

5/4/2008 12:46:00 PM

0

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?

What is a combination?

Nadim Kobeissi

5/4/2008 12:51:00 PM

0

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

David A. Black

5/4/2008 12:59:00 PM

0

Hi --

On Sun, 4 May 2008, 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".

>> str = 'a'
=> "a"
>> cow = "hello"
=> "hello"
>> str.succ! until str == cow
=> nil
>> str
=> "hello"


David

--
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.r... for details and updates!

Wyatt Greene

5/4/2008 1:02:00 PM

0

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

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 Kobeissi

5/4/2008 1:03:00 PM

0

David A. Black wrote:
> Hi --
>
> On Sun, 4 May 2008, Nadim Kobeissi wrote:
>
>> 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?
--
Posted via http://www.ruby-....

Ian Hobson

5/4/2008 1:17:00 PM

0

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"?

Ian Hobson

5/4/2008 1:26:00 PM

0

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

Robert Klemme

5/5/2008 6:24:00 AM

0

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".

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