[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

Re: newbie question about sets

Xavier Noria

1/15/2007 1:08:00 PM

On Jan 15, 2007, at 1:57 PM, Jason Mayer wrote:

> Set implements a collection of unordered values with no duplicates.

Yes, that implements sets as defined in math. What you wanted is
called "multiset"[*], though in my degree I never saw any of those
even mentioned.

-- fxn

[*] http://mathworld.wolfram.com/Mul...
3 Answers

Stefano Zacchiroli

1/15/2007 1:29:00 PM

0

On Mon, Jan 15, 2007 at 10:07:47PM +0900, Xavier Noria wrote:
> Yes, that implements sets as defined in math. What you wanted is
> called "multiset"[*], though in my degree I never saw any of those
> even mentioned.

I guess one can build them by herself on the following lines:

class MultiSet < Set
def initialize
super
@arity = {}
end
attr_reader :arity
def add(o)
super(o)
@arity[o] = 0 unless @arity.member? o
@arity[o] += 1
end
def delete(o)
super(o)
@arity[o] -= 1
@arity.delete o if @arity[o] == 0
end
end

but beware that the above is newbie's code (and also utterly simplified
...) :-)

And by the way, why the above class does not work properly with <<
(which is an alias for add according to my set.rb) while it works
properly with add?

E.g.

irb(main):019:0> m=MultiSet.new
=> #<MultiSet: {}>
irb(main):020:0> m.add 1
=> 1
irb(main):021:0> m.add 1
=> 2
irb(main):022:0> m.arity[1]
=> 2 # so far so good

irb(main):023:0> m << 2
=> #<MultiSet: {1, 2}>
irb(main):024:0> m << 2
=> #<MultiSet: {1, 2}>
irb(main):025:0> m.arity[2]
=> nil # aargh, do I need to alias again in
# derived classes? that's too bad ...

TIA,
Cheers.

--
Stefano Zacchiroli -*- Computer Science PhD student @ Uny Bologna, Italy
zack@{cs.unibo.it,debian.org,bononia.it} -%- http://www.bononi...
(15:56:48) Zack: e la demo dema ? /\ All one has to do is hit the
(15:57:15) Bac: no, la demo scema \/ right keys at the right time

Stefano Zacchiroli

1/15/2007 1:36:00 PM

0

Answering to myself ...

On Mon, Jan 15, 2007 at 10:29:11PM +0900, Stefano Zacchiroli wrote:
> def delete(o)
> super(o)
> @arity[o] -= 1
> @arity.delete o if @arity[o] == 0
> end

The above is of course wrong, elements get remove before their arity
reach 0.

> => nil # aargh, do I need to alias again in
> # derived classes? that's too bad ...

Apparently so, alias makes a *copy* of the method :(

Here is a better version:

require 'set'
class MultiSet < Set
def initialize
super
@arity = {}
end
attr_reader :arity
def add(o)
super(o)
@arity[o] = 0 unless @arity.member? o
@arity[o] += 1
end
def delete(o)
@arity[o] -= 1
if @arity[o] == 0
super(o)
@arity.delete o
end
end
alias << add
end

--
Stefano Zacchiroli -*- Computer Science PhD student @ Uny Bologna, Italy
zack@{cs.unibo.it,debian.org,bononia.it} -%- http://www.bononi...
(15:56:48) Zack: e la demo dema ? /\ All one has to do is hit the
(15:57:15) Bac: no, la demo scema \/ right keys at the right time

Robert Klemme

1/15/2007 3:47:00 PM

0

On 15.01.2007 14:36, Stefano Zacchiroli wrote:
> Answering to myself ...
>
> On Mon, Jan 15, 2007 at 10:29:11PM +0900, Stefano Zacchiroli wrote:
>> def delete(o)
>> super(o)
>> @arity[o] -= 1
>> @arity.delete o if @arity[o] == 0
>> end
>
> The above is of course wrong, elements get remove before their arity
> reach 0.
>
>> => nil # aargh, do I need to alias again in
>> # derived classes? that's too bad ...
>
> Apparently so, alias makes a *copy* of the method :(
>
> Here is a better version:
>
> require 'set'
> class MultiSet < Set
> def initialize
> super
> @arity = {}
> end
> attr_reader :arity
> def add(o)
> super(o)
> @arity[o] = 0 unless @arity.member? o
> @arity[o] += 1
> end
> def delete(o)
> @arity[o] -= 1
> if @arity[o] == 0
> super(o)
> @arity.delete o
> end
> end
> alias << add
> end
>

You can as well use a Hash as multi set:

irb(main):001:0> multi_set = Hash.new 0
=> {}
irb(main):002:0> multi_set['foo'] += 1
=> 1
irb(main):003:0> multi_set
=> {"foo"=>1}
irb(main):004:0> multi_set['foo'] += 1
=> 2
irb(main):005:0> multi_set
=> {"foo"=>2}
irb(main):006:0> multi_set['bar'] += 1
=> 1
irb(main):007:0> multi_set['bar']
=> 1
irb(main):008:0> multi_set['foo']
=> 2
irb(main):009:0> multi_set
=> {"foo"=>2, "bar"=>1}
irb(main):010:0> multi_set['foo'] -= 1
=> 1
irb(main):011:0> multi_set
=> {"foo"=>1, "bar"=>1}
irb(main):012:0> multi_set['xxx']
=> 0

Of course this does not prevent values other than numbers as well as
negative numbers.

Ah, and btw, I'm not sure whether it's a good idea to have a MultiSet
class inherit Set: after all Set /is (the special case of) a/ MultiSet -
not the other way round.

Kind regards

robert