From: Ian Hobson <ian.hobson@...>
Date: 2008-05-04T22:16:30+09:00
Subject: Re: Array combination check

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