How would you accomplish this?

Discussion in 'Ruby' started by George George, Nov 4, 2009.

  1. Given an array of arrays for example
    [["A", "B"], ["A", "B", "D", "C"], ["B", "D"], ["B", "C", "F", "E"],
    ["C", "F"], ["C", "E"], ["G"]]

    what would be a nice way of "merging" the items that seem to already be
    contained in another array. e.g.
    ["A","B"] and ["B", "D"] are subsets of ["A", "B", "D", "C"] I would
    like to drop the subsets and be left with ["A", "B", "D", "C"] only.

    My approach was to use the set module in Ruby, and look for set
    membership using a pairwise comparison.
    I also thought maybe i should look for the largest set. and then check
    whether the rest of the sets are subsets of this set. if they are, then
    delete them.

    However i thought a better solution, or strategy may already exist.
    How would you accomplish this?
    --
    Posted via http://www.ruby-forum.com/.
    George George, Nov 4, 2009
    #1
    1. Advertising

  2. 2009/11/4 George George <>:
    > Given an array of arrays for example
    > [["A", "B"], ["A", "B", "D", "C"], ["B", "D"], ["B", "C", "F", "E"],
    > ["C", "F"], ["C", "E"], ["G"]]
    >
    > what would be a nice way of "merging" the items that seem to already be
    > contained in another array. e.g.
    > ["A","B"] and ["B", "D"] are subsets of ["A", "B", "D", "C"] I would
    > like to drop the subsets =A0and be left with ["A", "B", "D", "C"] only.
    >
    > My approach was to use the set module in Ruby, and look for set
    > membership using a pairwise comparison.
    > I also thought maybe i should look for the largest set. and then check
    > whether the rest of the sets are subsets of this set. if they are, then
    > delete them.
    >
    > However i thought a better solution, or strategy may already exist.
    > How would you accomplish this?


    The approach using set size seems reasonable to reduce the number of
    set comparisons. You could do

    require 'set'

    arrs =3D [["A", "B"], ["A", "B", "D", "C"], ["B", "D"], ["B", "C", "F", "E"=
    ],
    ["C", "F"], ["C", "E"], ["G"]]

    result =3D []

    arrs.sort_by {|a| -a.size}.each do |a|
    s =3D a.to_set
    result << s unless result.any? {|rs| rs.superset? s}
    end

    p result

    -> [#<Set: {"B", "C", "F", "E"}>, #<Set: {"A", "B", "D", "C"}>, #<Set: {"G"=
    }>]

    Kind regards

    robert


    --=20
    remember.guy do |as, often| as.you_can - without end
    http://blog.rubybestpractices.com/
    Robert Klemme, Nov 4, 2009
    #2
    1. Advertising

  3. On Wed, Nov 4, 2009 at 11:49 AM, George George
    <> wrote:
    > Given an array of arrays for example
    > [["A", "B"], ["A", "B", "D", "C"], ["B", "D"], ["B", "C", "F", "E"],
    > ["C", "F"], ["C", "E"], ["G"]]
    >
    > what would be a nice way of "merging" the items that seem to already be
    > contained in another array. e.g.
    > ["A","B"] and ["B", "D"] are subsets of ["A", "B", "D", "C"] I would
    > like to drop the subsets =A0and be left with ["A", "B", "D", "C"] only.


    This is one way:

    irb(main):025:0> a =3D [["A", "B"], ["A", "B", "D", "C"], ["B", "D"],
    ["B", "C", "F", "E"],["C", "F"], ["C", "E"], ["G"]]
    =3D> [["A", "B"], ["A", "B", "D", "C"], ["B", "D"], ["B", "C", "F",
    "E"], ["C", "F"], ["C", "E"], ["G"]]
    irb(main):026:0> a.delete_if {|x| a.any? {|y| (x !=3D y) && ((x&y).size
    =3D=3D x.size)}}
    =3D> [["A", "B", "D", "C"], ["B", "C", "F", "E"], ["G"]]

    Maybe there would be a way to optimize this sorting by size and
    checking smaller ones against bigger ones only.
    Left as an excercise for the reader :)

    Jesus.
    Jesús Gabriel y Galán, Nov 4, 2009
    #3
  4. 2009/11/4 Jes=FAs Gabriel y Gal=E1n <>:
    > On Wed, Nov 4, 2009 at 11:49 AM, George George
    > <> wrote:
    >> Given an array of arrays for example
    >> [["A", "B"], ["A", "B", "D", "C"], ["B", "D"], ["B", "C", "F", "E"],
    >> ["C", "F"], ["C", "E"], ["G"]]
    >>
    >> what would be a nice way of "merging" the items that seem to already be
    >> contained in another array. e.g.
    >> ["A","B"] and ["B", "D"] are subsets of ["A", "B", "D", "C"] I would
    >> like to drop the subsets =A0and be left with ["A", "B", "D", "C"] only.

    >
    > This is one way:
    >
    > irb(main):025:0> a =3D [["A", "B"], ["A", "B", "D", "C"], ["B", "D"],
    > ["B", "C", "F", "E"],["C", "F"], ["C", "E"], ["G"]]
    > =3D> [["A", "B"], ["A", "B", "D", "C"], ["B", "D"], ["B", "C", "F",
    > "E"], ["C", "F"], ["C", "E"], ["G"]]
    > irb(main):026:0> a.delete_if {|x| a.any? {|y| (x !=3D y) && ((x&y).size
    > =3D=3D x.size)}}
    > =3D> [["A", "B", "D", "C"], ["B", "C", "F", "E"], ["G"]]
    >
    > Maybe there would be a way to optimize this sorting by size and
    > checking smaller ones against bigger ones only.
    > Left as an excercise for the reader :)


    Done. :)

    robert


    --=20
    remember.guy do |as, often| as.you_can - without end
    http://blog.rubybestpractices.com/
    Robert Klemme, Nov 4, 2009
    #4
  5. George George

    Greg Barozzi Guest

    George George wrote:
    > Given an array of arrays for example
    > [["A", "B"], ["A", "B", "D", "C"], ["B", "D"], ["B", "C", "F", "E"],
    > ["C", "F"], ["C", "E"], ["G"]]
    >
    > what would be a nice way of "merging" the items that seem to already be
    > contained in another array.


    Try this:

    arr = [["A", "B"], ["A", "B", "D", "C"], ["B", "D"], ["B", "C", "F",
    "E"],
    ["C", "F"], ["C", "E"], ["G"]]


    arr = arr.flatten.sort

    str = arr.to_s.squeeze

    arr = str.split(//)


    This takes the array of arrays, flattens it into a single array
    and sorts it. Then turns it into a string so we can use the
    squeeze method that eliminates duplicate characters. Then
    it changes it back into an array. =)
    --
    Posted via http://www.ruby-forum.com/.
    Greg Barozzi, Nov 5, 2009
    #5
  6. Greg Barozzi wrote:
    > George George wrote:
    >> Given an array of arrays for example
    >> [["A", "B"], ["A", "B", "D", "C"], ["B", "D"], ["B", "C", "F", "E"],
    >> ["C", "F"], ["C", "E"], ["G"]]
    >>
    >> what would be a nice way of "merging" the items that seem to already be
    >> contained in another array.

    >
    > Try this:
    >
    > arr = [["A", "B"], ["A", "B", "D", "C"], ["B", "D"], ["B", "C", "F",
    > "E"],
    > ["C", "F"], ["C", "E"], ["G"]]
    >
    >
    > arr = arr.flatten.sort
    >
    > str = arr.to_s.squeeze
    >
    > arr = str.split(//)
    >
    >
    > This takes the array of arrays, flattens it into a single array
    > and sorts it. Then turns it into a string so we can use the
    > squeeze method that eliminates duplicate characters. Then
    > it changes it back into an array. =)


    Well, this will just yield the discrete strings -- not what the OP
    asked. But what you're talking about can be done more efficiently with
    arr.flatten.uniq.sort . No need for the intermediate string
    representation.

    Best,
    --
    Marnen Laibow-Koser
    http://www.marnen.org

    --
    Posted via http://www.ruby-forum.com/.
    Marnen Laibow-Koser, Nov 5, 2009
    #6
  7. On Wed, Nov 4, 2009 at 4:19 PM, George George <> w=
    rote:
    > Given an array of arrays for example
    > [["A", "B"], ["A", "B", "D", "C"], ["B", "D"], ["B", "C", "F", "E"],
    > ["C", "F"], ["C", "E"], ["G"]]
    >
    > what would be a nice way of "merging" the items that seem to already be
    > contained in another array. e.g.
    > ["A","B"] and ["B", "D"] are subsets of ["A", "B", "D", "C"] I would
    > like to drop the subsets =A0and be left with ["A", "B", "D", "C"] only.


    Here are two ways:

    require 'set'

    # --------------------------------------------------------------
    # method 1:

    sets =3D [["A", "B"], ["A", "B", "D", "C"], ["B", "D"], ["B", "C", "F",
    "E"], ["C", "F"], ["C", "E"], ["G"]]

    sets =3D sets.map {|x| x.to_set}.sort_by {|x| -x.size}

    (0...(sets.length)).each do |i|
    next unless sets
    ((i+1)...(sets.length)).each do |j|
    sets[j] =3D nil if sets[j] && sets[j].subset?(sets)
    end
    end

    sets =3D sets.compact.map {|x| x.to_a}
    p sets

    # --------------------------------------------------------------
    # method 2:

    sets =3D [["A", "B"], ["A", "B", "D", "C"], ["B", "D"], ["B", "C", "F",
    "E"], ["C", "F"], ["C", "E"], ["G"]]

    sets =3D sets.map {|x| x.to_set}.sort_by {|x| -x.size}

    i =3D 0
    while i < sets.length
    ((i+1)...(sets.length)).each do |j|
    sets[j] =3D nil if sets[j].subset?(sets)
    end
    sets.compact!
    i +=3D 1
    end

    sets =3D sets.map {|x| x.to_a}
    p sets

    martin
    Martin DeMello, Nov 5, 2009
    #7
    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. shland
    Replies:
    4
    Views:
    574
    shland
    Oct 20, 2003
  2. Biffo

    Best method to accomplish?

    Biffo, Feb 3, 2005, in forum: ASP .Net
    Replies:
    0
    Views:
    326
    Biffo
    Feb 3, 2005
  3. glunk
    Replies:
    4
    Views:
    402
    Steve Horsley
    Jun 30, 2004
  4. Augustine Kaplan

    what could you accomplish with a degree?

    Augustine Kaplan, May 19, 2004, in forum: Python
    Replies:
    0
    Views:
    308
    Augustine Kaplan
    May 19, 2004
  5. Danny

    how do you guys accomplish this

    Danny, May 10, 2004, in forum: ASP General
    Replies:
    3
    Views:
    120
    Aaron Bertrand - MVP
    May 10, 2004
Loading...

Share This Page