Asp Forum - Re: how to remove dups from 2 lists?

Rob Biedenharn

5/11/2007 3:11:00 AM

On May 10, 2007, at 10:18 PM, Mike Steiner wrote:

> I'm trying to write some code that removes all elements from 2
> lists that
> are in both lists. However, I don't want any duplicates from each list
> deleted also (which is what the array "-" operator does). The code
> I have
> now doesn't handle restarting the current iteration for both loops
> when a
> match is found and deleted in both loops. Here's the code:
>
> def RemoveDupsFromLists ( list1 , list2 )
> list1.each_index do | i |
> list2.each_index do | j |
> if list1[i] == list2[j]
> list1.delete_at ( i )
> list2.delete_at ( j )
> end
> end
> end
> return [ list1 , list2 ]
> end
>
> What's weird is that doing this is easy in C (my first language), but
> difficult in Ruby. Everything else I've seen has been MUCH easier
> in Ruby.
>
> Mike Steiner

Having some examples might help, but is something like this what
you're after?

>> a = %w[ a a a b b c ]
=> ["a", "a", "a", "b", "b", "c"]
>> b = %w[ b c c c d ]
=> ["b", "c", "c", "c", "d"]
>> a + b
=> ["a", "a", "a", "b", "b", "c", "b", "c", "c", "c", "d"]
>> a | b
=> ["a", "b", "c", "d"]
>> a - b
=> ["a", "a", "a"]
>> a & b
=> ["b", "c"]
>> a - (a & b)
=> ["a", "a", "a"]
>> b - (a & b)
=> ["d"]

In particular, which do you expect from RemoveDupsFromLists( a, b )?

What I have for the last two expressions above:
=> [ ["a", "a", "a"], ["d"] ]

Or:
=> [ ["a", "a", "a", "b"], ["c", "c", "d"] ]
because it works like canceling terms in a fraction:

["a", "a", "a", "b", "b", "c"]
-----------------------------------------------
["b", "c", "c", "c", "d"]

Basically, write a test:

require 'test/unit'
class RemoveDupsTest < Test::Unit::TestCase
def test_simple
list1 = ["a", "a", "a", "b", "b", "c"]
list2 = ["b", "c", "c", "c", "d"]
expects = [ [__,__], [__,__] ] #<=== fill me it!
assert_equals expects, RemoveDupsFromLists(list1, list2)
end
end

Then you'll know what you want (and so will we!) and you'll be sure
when you get it working.

-Rob

Rob Biedenharn http://agileconsult...
Rob@AgileConsultingLLC.com

7 Answers

Todd Benson

5/11/2007 4:04:00 PM

On 5/11/07, Mike Steiner <mikejaysteiner@gmail.com> wrote:
> I'm looking for a function that will eliminate all matching items, like
> canceling terms in a fraction. If the first list has 3 "a"s, and the second
> list has 5 "a"s, then afterwards the first list should have 0 "a"s and the
> second list should have 2 "a"s.

I thought this looked a lot like simplification. I can find a lot of
uses for this simple function.

WoNáDo

5/11/2007 7:50:00 PM

WoNáDo

5/11/2007 9:37:00 PM

> On May 10, 2007, at 10:18 PM, Mike Steiner wrote:
>
>> I'm trying to write some code that removes all elements from 2 lists that
>> are in both lists. However, I don't want any duplicates from each list
>> deleted also (which is what the array "-" operator does). The code I have
>> now doesn't handle restarting the current iteration for both loops when a
>> match is found and deleted in both loops. Here's the code:
>>
>> def RemoveDupsFromLists ( list1 , list2 )
>> list1.each_index do | i |
>> list2.each_index do | j |
>> if list1[i] == list2[j]
>> list1.delete_at ( i )
>> list2.delete_at ( j )
>> end
>> end
>> end
>> return [ list1 , list2 ]
>> end
>>
>> What's weird is that doing this is easy in C (my first language), but
>> difficult in Ruby. Everything else I've seen has been MUCH easier in
>> Ruby.
>>
>> Mike Steiner

Or is it something like this?

Here only common elements of both lists are deleted from left to right, but if a
list contains more elements, e.g. "a" than the other, only the number of "a"s
that are in the other list will be deleted from the one, which has more "a"s (I
don't know how to describe it - the code should explain ist):

a = %w{a b a a c a b c d e f e a}
b = %w{a b a c d c d c c g h g c}
puts '--- before ---'
p a
p b
ah = a.inject(Hash.new(0)){|h,w|h[w]+=1;h}
bh = b.inject(Hash.new(0)){|h,w|h[w]+=1;h}
abh = (ah.keys & bh.keys).inject({}){|h,w|h[w]=[ah[w], bh[w]].min;h}
[a, b].each{|arr|abh.each{|k,v|v.times{arr.delete_at(arr.index(k)) if
arr.include?(k)}}}
puts '--- after ---'
p a
p b

Output:

--- before ---
["a", "b", "a", "a", "c", "a", "b", "c", "d", "e", "f", "e", "a"]
["a", "b", "a", "c", "d", "c", "d", "c", "c", "g", "h", "g", "c"]
--- after ---
["a", "a", "b", "e", "f", "e", "a"]
["d", "c", "c", "g", "h", "g", "c"]

Wolfgang Nádasi-Donner

WoNáDo

5/11/2007 11:52:00 PM

Wolfgang Nádasi-Donner schrieb:
> Or is it something like this?
>
> ...
> --- before ---
> ["a", "b", "a", "a", "c", "a", "b", "c", "d", "e", "f", "e", "a"]
> ["a", "b", "a", "c", "d", "c", "d", "c", "c", "g", "h", "g", "c"]
> --- after ---
> ["a", "a", "b", "e", "f", "e", "a"]
> ["d", "c", "c", "g", "h", "g", "c"]

If it is the wanted direction, the program is simple.

class Array
def remdups(b)
a= self.dup
b.each{|el|a.delete_at(a.index(el)) if a.include?(el)}
a
end
end

a = %w{a b a a c a b c d e f e a}
b = %w{a b a c d c d c c g h g c}
puts '--- before ---'
p a
p b
puts '--- after ---'
p a.remdups(b)
p b.remdups(a)
p [1,1,1,1].remdups([1,1,2])
p [1,1,2].remdups([1,1,1,1])

Output:

--- before ---
["a", "b", "a", "a", "c", "a", "b", "c", "d", "e", "f", "e", "a"]
["a", "b", "a", "c", "d", "c", "d", "c", "c", "g", "h", "g", "c"]
--- after ---
["a", "a", "b", "e", "f", "e", "a"]
["d", "c", "c", "g", "h", "g", "c"]
[1, 1]
[2]

Wolfgang Nádasi-Donner

Lloyd Linklater

5/12/2007 6:39:00 AM

Wolfgang, that is VERY slick! Well done!

--
Posted via http://www.ruby-....

Moises Machado

5/12/2007 1:47:00 PM

Mike Steiner wrote:
> while results

Well, this while loop will not terminate because [] is considered true
in ruby, use this instead

while results != []

or the more idiomatic

while not results.empty?

> a = a - m
> b = b - m

I don't think that this '-' works here, you probably meant:

a.delete_at(a.index(m))
b.delete_at(b.index(m))

because a = a - [m] will remove all m's of a and make the code do the
same as:

a, b = a - (a&b), b - (a&b)

although i like the elegance of that solution i prefer something like
this:

def removeDupsFromLists ( list1 , list2 )
x = list1.dup
x.each do | i |
if list2.include?(i)
list1.delete_at( list1.index(i) )
list2.delete_at( list2.index(i) )
end
end
return [ list1, list2 ]
end

just because is easier to follow and to debug: there is no way of get an
infinte loop

MoisesMachado

--
Posted via http://www.ruby-....

Rick DeNatale

5/12/2007 4:21:00 PM

On 5/11/07, Wolfgang Nádasi-Donner <wonado@donnerweb.de> wrote:
> Wolfgang Nádasi-Donner schrieb:
> > Or is it something like this?
> >
> > ...
> > --- before ---
> > ["a", "b", "a", "a", "c", "a", "b", "c", "d", "e", "f", "e", "a"]
> > ["a", "b", "a", "c", "d", "c", "d", "c", "c", "g", "h", "g", "c"]
> > --- after ---
> > ["a", "a", "b", "e", "f", "e", "a"]
> > ["d", "c", "c", "g", "h", "g", "c"]
>
> If it is the wanted direction, the program is simple.
>
> class Array
> def remdups(b)
> a= self.dup
> b.each{|el|a.delete_at(a.index(el)) if a.include?(el)}
> a
> end
> end

Or somewhat faster, particularly for long arrays:

class Array

def rem_dups(b)
a = dup
b.each { | e | i = a.index(e); a.delete_at(i) if i}
a
end
end

Which avoids scanning the array twice for each element.

--
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denh...

comp.lang.ruby

Re: how to remove dups from 2 lists?

Rob Biedenharn

Todd Benson

WoNáDo

WoNáDo

WoNáDo

Lloyd Linklater

Moises Machado

Rick DeNatale

x Login to ForumsZone