[ruby-talk:16671] Re: bag difference

In article <p86Y6.80058$[e-mail]>, "Niklas
Frykholm" <[e-mail]> wrote:


> On Thu, Jun 21, 2001 at 02:56:51AM +0900, Hugh Sasse Staff Elec Eng
> wrote:
>> Is there an elegant way to do a bag diffeence between 2 arrays, rather
>> than a set difference?
>> [1,1,1,2,3,3,4,4,4] <something> [1,2,3,4,4] gives: [1,1,3,4]
>> If ordering is preserved that would be great.
> Don't know if this is the most elegant solution, but it is the first
> that comes to my mind.
> 
>     class Array
>         def with_count
>             h = {}; h.default = 0
>             self.collect {|x| [x, h[x] += 1]}
>         end
>         def bagminus(other)
>             (self.with_count - other.with_count).collect {|x| x[0]}
>         end
>     end
> 
>     a = [1,1,1,2,3,3,4,4,4]
>     b = [1,2,3,4,4]
> 
>     p a.bagminus b # --> [1, 1, 3, 4]
> // Niklas

I plan to read this carefully when I have time, but here's what I came up
with.  It's slightly more verbose, but I think an Array#delete_first()
would be useful, which is a bonus.  How efficient it is depends on how
efficient Array#index and Array#delete_at are, but I would guess they're
very simple.

class Array
 
    def delete_first(x)
 
        if (i = self.index(x))
            self.delete_at(i)
        end
 
    end
 
    def bag_minus(other)
 
        difference = Array.new
        unwanted  = other.clone
 
        self.each do |x|
            if !unwanted.delete_first(x)
                difference.push(x)
            end
        end
 
        return difference
    end
 
end
 
a = [0,0,1,1,1,2,2,3,3,3,3,4,4,5,5,6]
b = [1,2,3,3,4]
 
puts "#{a}.bag_minus(#{b}) = #{a.bag_minus(b)}" # -->
[0,0,1,1,2,3,3,4,5,5,6]