All contiguous subsets

[joe chesak]

[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

 

[Jean-Julien Fleck]

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

 

[Rick DeNatale]

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

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

 

[gf]

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]

[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