How would you accomplish this?

[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 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?

 

[Robert Klemme]

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/

 

[Jesús Gabriel y Galán]

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.

 

[Robert Klemme]

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/

 

[Greg Barozzi]

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

 

[Marnen Laibow-Koser]

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,

 

[Martin DeMello]

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