# How would you accomplish this?

**URL:** <https://www.ruby-forum.com/t/how-would-you-accomplish-this/178424>\
**Category:** Ruby\
**Created:** [November 4, 2009, 11:49am UTC](https://www.ruby-forum.com/t/how-would-you-accomplish-this/178424 "2009-11-04T11:49:23Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\
**Post date:** [November 4, 2009, 11:49am UTC](https://www.ruby-forum.com/t/how-would-you-accomplish-this/178424/1 "2009-11-04T11:49:23Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\
**Post date:** [November 4, 2009, 12:56pm UTC](https://www.ruby-forum.com/t/how-would-you-accomplish-this/178424/2 "2009-11-04T12:56:45Z")

</div>

2009/11/4 George G. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid):

> 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 = [[“A”, “B”], [“A”, “B”, “D”, “C”], [“B”, “D”], [“B”, “C”, “F”,  
“E”],  
[“C”, “F”], [“C”, “E”], [“G”]]

result = []

arrs.sort\_by {|a| -a.size}.each do |a|  
s = 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

---

<div class="post-metadata">

**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\
**Post date:** [November 4, 2009, 12:57pm UTC](https://www.ruby-forum.com/t/how-would-you-accomplish-this/178424/3 "2009-11-04T12:57:55Z")

</div>

On Wed, Nov 4, 2009 at 11:49 AM, George G.  
[removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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 and be left with [“A”, “B”, “D”, “C”] only.

This is one way:

irb(main):025:0\> a = [[“A”, “B”], [“A”, “B”, “D”, “C”], [“B”, “D”],  
[“B”, “C”, “F”, “E”],[“C”, “F”], [“C”, “E”], [“G”]]  
=\> [[“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 != y) && ((x&y).size  
== x.size)}}  
=\> [[“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.

---

<div class="post-metadata">

**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\
**Post date:** [November 4, 2009, 12:59pm UTC](https://www.ruby-forum.com/t/how-would-you-accomplish-this/178424/4 "2009-11-04T12:59:05Z")

</div>

2009/11/4 Jesús Gabriel y Galán [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid):

> 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

---

<div class="post-metadata">

**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\
**Post date:** [November 5, 2009, 5:22am UTC](https://www.ruby-forum.com/t/how-would-you-accomplish-this/178424/5 "2009-11-05T05:22:04Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\
**Post date:** [November 5, 2009, 5:52am UTC](https://www.ruby-forum.com/t/how-would-you-accomplish-this/178424/6 "2009-11-05T05:52:37Z")

</div>

Greg B. wrote:

> George G. 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](http://www.marnen.org)  
removed\_email\_address@domain.invalid

---

<div class="post-metadata">

**Author:** ![georgeuoa](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/g/7ab992/32.png) [@georgeuoa](https://www.ruby-forum.com/u/georgeuoa)\
**Post date:** [November 5, 2009, 6:38am UTC](https://www.ruby-forum.com/t/how-would-you-accomplish-this/178424/7 "2009-11-05T06:38:01Z")

</div>

On Wed, Nov 4, 2009 at 4:19 PM, George G.  
[removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) 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 and be left with [“A”, “B”, “D”, “C”] only.

Here are two ways:

require ‘set’

# --------------------------------------------------------------

# method 1:

sets = [[“A”, “B”], [“A”, “B”, “D”, “C”], [“B”, “D”], [“B”, “C”, “F”,  
“E”], [“C”, “F”], [“C”, “E”], [“G”]]

sets = sets.map {|x| x.to\_set}.sort\_by {|x| -x.size}

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

sets = sets.compact.map {|x| x.to\_a}  
p sets

# --------------------------------------------------------------

# method 2:

sets = [[“A”, “B”], [“A”, “B”, “D”, “C”], [“B”, “D”], [“B”, “C”, “F”,  
“E”], [“C”, “F”], [“C”, “E”], [“G”]]

sets = sets.map {|x| x.to\_set}.sort\_by {|x| -x.size}

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

sets = sets.map {|x| x.to\_a}  
p sets

martin