From: Christian Szegedy <szegedy@...>
Date: 2001-06-21T23:57:10+09:00
Subject: [ruby-talk:16708] e: bag difference

Hugh Sasse Staff Elec Eng wrote:

> >     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
[...]
> 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:
[...]
> class Array
>    def bag_subtract!(other)
>       other.each {
>          |value|
>          i = index(value)
>          delete_at(i) if i
>      }
>      self
>   end
> end

Both soultions are quadratic, because index is linear.
It could be solved in n*log(n) time.
It does not matter for small arrays  
but can be quite slow even if self has only 100 elements.

Christian