All contiguous subsets

Ruby
1

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

2

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,

3

On Thu, Mar 25, 2010 at 4:33 PM, joe chesak [email protected] 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/
Twitter: http://twitter.com/RickDeNatale
WWR: http://www.workingwithrails.com/person/9021-rick-denatale
LinkedIn: http://www.linkedin.com/in/rickdenatale

4

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.

5

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