All contiguous subsets

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

  1. joe chesak

    joe chesak Guest

    [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
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

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

    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
     
    Rick DeNatale, Mar 25, 2010
    #3
  4. joe chesak

    gf Guest

    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
    #4
  5. joe chesak

    joe chesak Guest

    [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
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Roger Varley
    Replies:
    20
    Views:
    932
    jan V
    Aug 14, 2005
  2. Paul
    Replies:
    1
    Views:
    540
    Jack Klein
    Nov 24, 2004
  3. Gaijinco

    Generate All Subsets

    Gaijinco, Sep 26, 2005, in forum: C Programming
    Replies:
    7
    Views:
    576
    Emmanuel Delahaye
    Sep 26, 2005
  4. Gaijinco

    Generate All Subsets

    Gaijinco, Sep 26, 2005, in forum: C++
    Replies:
    7
    Views:
    579
  5. Patrick

    search all subsets?

    Patrick, Dec 21, 2007, in forum: C++
    Replies:
    4
    Views:
    400
    Kira Yamato
    Dec 22, 2007
Loading...

Share This Page