From: Niklas Frykholm <niklas@...>
Date: 2001-06-22T00:09:19+09:00
Subject: [ruby-talk:16711] Re: bag difference

On Thu, Jun 21, 2001 at 11:41:27PM +0900, Hugh Sasse Staff Elec Eng wrote:
> On Thu, 21 Jun 2001, HarryO wrote:
> 
> Thank you.  I was a bit confused by the other solution too, but it seemed
> to rely on going through the array more than once.  Anyway, I 
> settled on this:

The idea was to use something similar to a "Schwartzian transform" to allow us
to use the ordiary #- operator. First, we map each object to an array that
contains the object and a counter specifying how many times the object has
appeared

    h = {}; h.default = 0
    self.collect {|x| [x, h[x] += 1}

    [1, 1, 1, 2, 3, 3] -> [[1,1], [1,2], [1,3], [2,1], [3,1], [3,2]]
    [1, 1, 2] -> [[1,1], [1,2], [2,1]]

Then we can do an ordinary set difference between these two arrays:

    a - b

    [[1,3], [3,1], [3, 2]]

Finally we remove the counters

    self.collect {|x| x[0]}

    [1, 3, 3]

But using #delete_at is better: faster, simpler...

// Niklas