# Array combination check

**URL:** <https://www.ruby-forum.com/t/array-combination-check/136612>\
**Category:** Ruby\
**Created:** [May 4, 2008, 2:39pm UTC](https://www.ruby-forum.com/t/array-combination-check/136612 "2008-05-04T14:39:56Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![kaepora](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/d78d45/32.png) [@kaepora](https://www.ruby-forum.com/u/kaepora)\
**Post date:** [May 4, 2008, 2:39pm UTC](https://www.ruby-forum.com/t/array-combination-check/136612/1 "2008-05-04T14:39:56Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![kaepora](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/d78d45/32.png) [@kaepora](https://www.ruby-forum.com/u/kaepora)\
**Post date:** [May 4, 2008, 2:46pm UTC](https://www.ruby-forum.com/t/array-combination-check/136612/2 "2008-05-04T14:46:52Z")

</div>

On Sun, May 4, 2008 at 2:39 PM, Nadim K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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?

---

<div class="post-metadata">

**Author:** ![kaepora](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/d78d45/32.png) [@kaepora](https://www.ruby-forum.com/u/kaepora)\
**Post date:** [May 4, 2008, 2:59pm UTC](https://www.ruby-forum.com/t/array-combination-check/136612/3 "2008-05-04T14:59:50Z")

</div>

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  
> > =\> nil
> 
> > str  
> > =\> “hello”

David

---

<div class="post-metadata">

**Author:** ![kaepora](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/d78d45/32.png) [@kaepora](https://www.ruby-forum.com/u/kaepora)\
**Post date:** [May 4, 2008, 3:02pm UTC](https://www.ruby-forum.com/t/array-combination-check/136612/4 "2008-05-04T15:02:49Z")

</div>

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  
> > > =\> 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?

---

<div class="post-metadata">

**Author:** ![kaepora](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/d78d45/32.png) [@kaepora](https://www.ruby-forum.com/u/kaepora)\
**Post date:** [May 4, 2008, 2:50pm UTC](https://www.ruby-forum.com/t/array-combination-check/136612/5 "2008-05-04T14:50:32Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![kaepora](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/d78d45/32.png) [@kaepora](https://www.ruby-forum.com/u/kaepora)\
**Post date:** [May 4, 2008, 3:05pm UTC](https://www.ruby-forum.com/t/array-combination-check/136612/6 "2008-05-04T15:05:46Z")

</div>

On May 4, 8:50 am, Nadim K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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

---

<div class="post-metadata">

**Author:** ![kaepora](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/d78d45/32.png) [@kaepora](https://www.ruby-forum.com/u/kaepora)\
**Post date:** [May 4, 2008, 3:17pm UTC](https://www.ruby-forum.com/t/array-combination-check/136612/7 "2008-05-04T15:17:35Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![kaepora](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/d78d45/32.png) [@kaepora](https://www.ruby-forum.com/u/kaepora)\
**Post date:** [May 5, 2008, 8:25am UTC](https://www.ruby-forum.com/t/array-combination-check/136612/8 "2008-05-05T08:25:54Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![kaepora](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/k/d78d45/32.png) [@kaepora](https://www.ruby-forum.com/u/kaepora)\
**Post date:** [May 4, 2008, 3:28pm UTC](https://www.ruby-forum.com/t/array-combination-check/136612/9 "2008-05-04T15:28:42Z")

</div>

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