# All contiguous subsets

Discussion in 'Ruby' started by joe chesak, Mar 25, 2010.

1. ### joe chesakGuest

[Note: parts of this message were removed to make it a legal post.]

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

joe chesak, Mar 25, 2010

2. ### Jean-Julien FleckGuest

Hello,

> Isn't there a cleaner way?

Perhaps you could use each_cons (from 1.8.7):

str =3D "1 2 3 4"
arr =3D str.split
arr.size.downto(1) do |i|
arr.each_cons(i) {|a| puts a.join(' ')}
end

Cheers,

--=20
JJ Fleck
PCSI1 Lyc=E9e Kl=E9ber

Jean-Julien Fleck, Mar 25, 2010

3. ### Rick DeNataleGuest

On Thu, Mar 25, 2010 at 4:33 PM, joe chesak <> wrote:
> Hello list,
>
> I know the ruby community is filled with algorithmic folks. =A0I have a f=

airly
> simple algorithm that I have solved, but I know it can be done cleaner th=

an
> I have.
>
> Given a short string of words separated by spaces, I wish to print out ev=

ery
> contiguous subset of words from that string.
>
> Given this string:
> =A0 =A0 "first second third fourth fifth"
> Output this list of substrings:
> =A0 =A0 first second third fourth
> =A0 =A0 first second third
> =A0 =A0 second third fourth
> =A0 =A0 first second
> =A0 =A0 second third
> =A0 =A0 third fourth
> =A0 =A0 first
> =A0 =A0 second
> =A0 =A0 third
> =A0 =A0 fourth
>
> I feel like this should all be possible within a REGEX, but I couldn't
> manage that. =A0So I turned it into an array plowed through it in a very
> manual manner. =A0You can run this in irb:
>
> phrase =3D "first second third fourth".split(' ')
> (phrase.size.downto(1)).each do |subphrase_size|
> =A0(0..phrase.size-subphrase_size).each do |cursor|
> =A0 =A0[cursor..cursor+subphrase_size-1].each do |subrange|
> =A0 =A0 =A0puts subrange.inject('') {|subphrase,letter| subphrase +
> phrase[letter] + ' '}
> =A0 =A0end
> =A0end
> end
>
> Isn't there a cleaner way?

Here's a recursive solution:

module Enumerable
def contiguous_subsequences(result=3D[])
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"]

--=20
Rick DeNatale

WWR: http://www.workingwithrails.com/person/9021-rick-denatale

Rick DeNatale, Mar 25, 2010
4. ### gfGuest

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.

gf, Mar 25, 2010
5. ### joe chesakGuest

[Note: parts of this message were removed to make it a legal post.]

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

On Thu, Mar 25, 2010 at 11:07 PM, gf <> wrote:

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

joe chesak, Mar 26, 2010