From: Rick DeNatale <rick.denatale@...>
Date: 2010-03-26T06:58:34+09:00
Subject: Re: All contiguous subsets

On Thu, Mar 25, 2010 at 4:33 PM, joe chesak <rubytalk@chesak.com> wrote:
> 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?

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