# All contiguous subsets

**URL:** <https://www.ruby-forum.com/t/all-contiguous-subsets/185772>\
**Category:** Ruby\
**Created:** [March 25, 2010, 9:34pm UTC](https://www.ruby-forum.com/t/all-contiguous-subsets/185772 "2010-03-25T21:34:17Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![joe\_chesak](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/439d5e/32.png) [@joe\_chesak](https://www.ruby-forum.com/u/joe_chesak)\
**Post date:** [March 25, 2010, 9:34pm UTC](https://www.ruby-forum.com/t/all-contiguous-subsets/185772/1 "2010-03-25T21:34:17Z")

</div>

Hello list,

I know the ruby community is filled with algorithmic folks. I have a  
fairly  
simple algorithm that I have solved, but I know it can be done cleaner  
than  
I have.

Given a short string of words separated by spaces, I wish to print out  
every  
contiguous subset of words from that string.

Given this string:  
“first second third fourth fifth”  
Output this list of substrings:  
first second third fourth  
first second third  
second third fourth  
first second  
second third  
third fourth  
first  
second  
third  
fourth

I feel like this should all be possible within a REGEX, but I couldn’t  
manage that. So I turned it into an array plowed through it in a very  
manual manner. You can run this in irb:

phrase = “first second third fourth”.split(’ ‘)  
(phrase.size.downto(1)).each do |subphrase\_size|  
(0…phrase.size-subphrase\_size).each do |cursor|  
[cursor…cursor+subphrase\_size-1].each do |subrange|  
puts subrange.inject(’’) {|subphrase,letter| subphrase +  
phrase[letter] + ’ '}  
end  
end  
end

Isn’t there a cleaner way?

Joe

---

<div class="post-metadata">

**Author:** ![joe\_chesak](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/439d5e/32.png) [@joe\_chesak](https://www.ruby-forum.com/u/joe_chesak)\
**Post date:** [March 25, 2010, 9:51pm UTC](https://www.ruby-forum.com/t/all-contiguous-subsets/185772/2 "2010-03-25T21:51:15Z")

</div>

Hello,

> Isn’t there a cleaner way?

Perhaps you could use each\_cons (from 1.8.7):

str = “1 2 3 4”  
arr = str.split  
arr.size.downto(1) do |i|  
arr.each\_cons(i) {|a| puts a.join(’ ')}  
end

Cheers,

---

<div class="post-metadata">

**Author:** ![joe\_chesak](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/439d5e/32.png) [@joe\_chesak](https://www.ruby-forum.com/u/joe_chesak)\
**Post date:** [March 25, 2010, 10:59pm UTC](https://www.ruby-forum.com/t/all-contiguous-subsets/185772/3 "2010-03-25T22:59:09Z")

</div>

On Thu, Mar 25, 2010 at 4:33 PM, joe chesak [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> ```
> "first second third fourth fifth"
> fourth
> 
> ```
> 
> phrase[letter] + ’ '}  
> end  
> end  
> end
> 
> Isn’t there a cleaner way?

Here’s a recursive solution:

module Enumerable  
def contiguous\_subsequences(result=[])  
unless empty?  
result \<\< self  
(size - 1).downto(1) do |len|  
result \<\< self[0,len]  
end  
self[1…-1].contiguous\_subsequences(result)  
end  
result  
end  
end

%w{first second third fourth fifth}.contiguous\_subsequences.each  
{|subsequence| p subsequence}

[“first”, “second”, “third”, “fourth”, “fifth”]  
[“first”, “second”, “third”, “fourth”]  
[“first”, “second”, “third”]  
[“first”, “second”]  
[“first”]  
[“second”, “third”, “fourth”, “fifth”]  
[“second”, “third”, “fourth”]  
[“second”, “third”]  
[“second”]  
[“third”, “fourth”, “fifth”]  
[“third”, “fourth”]  
[“third”]  
[“fourth”, “fifth”]  
[“fourth”]  
[“fifth”]

–  
Rick DeNatale

Blog: [http://talklikeaduck.denhaven2.com/](http://talklikeaduck.denhaven2.com/)  
Twitter: [http://twitter.com/RickDeNatale](http://twitter.com/RickDeNatale)  
WWR: [http://www.workingwithrails.com/person/9021-rick-denatale](http://www.workingwithrails.com/person/9021-rick-denatale)  
LinkedIn: [http://www.linkedin.com/in/rickdenatale](http://www.linkedin.com/in/rickdenatale)

---

<div class="post-metadata">

**Author:** ![joe\_chesak](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/439d5e/32.png) [@joe\_chesak](https://www.ruby-forum.com/u/joe_chesak)\
**Post date:** [March 25, 2010, 11:10pm UTC](https://www.ruby-forum.com/t/all-contiguous-subsets/185772/4 "2010-03-25T23:10:51Z")

</div>

Don’t be seduced by the idea that everything can be fixed by hitting  
it with the regex hammer. Sometimes regex will lead you down a very  
dark path when some simple constructs would get you running quickly.

Jean’s sample code is hard to beat for being simple and concise.

---

<div class="post-metadata">

**Author:** ![joe\_chesak](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/439d5e/32.png) [@joe\_chesak](https://www.ruby-forum.com/u/joe_chesak)\
**Post date:** [March 26, 2010, 1:17pm UTC](https://www.ruby-forum.com/t/all-contiguous-subsets/185772/5 "2010-03-26T13:17:41Z")

</div>

Thanks guys!

Jean-Julien, I’m floored how tailor-made the .each\_cons method is for  
this  
particular problem. Perfect! Thanks for introducing that to me.

Rick, I like your approach. If there are any changes to the  
requirements, I  
think your solution would be easy to modifiy for just about any new  
twist.

GF. I mostly agree. I’ve been long seduced by REGEX and find it a  
comfort  
zone. But in this case, there’s no contest with the .each\_cons.

Joe