Newbie question about sets

I'm just curious if there's any way to duplicate values in a set. After
quiz 108, I modified my submission so that it was a fully functional game.
I then passed around my finished program to some of my coworkers who are
interested in ruby. After a few days, someone came back to me with a bug,
and this appears to be the root cause of that bug.

irb(main):001:0> target = "stuff"
=> "stuff"
irb(main):002:0> a = target.split(//).sort
=> ["f", "f", "s", "t", "u"]
irb(main):003:0> require 'Set'
=> true
irb(main):004:0> s1 = Set.new(a)
=> #<Set: {"f", "s", "t", "u"}>

As it stands, if the word ffffuuuuussssstttt existed, it would be considered
a subset of a. How do you avoid this using sets?

Doh! first line of ri Set told me what I needed to know - that it's not
really possible.

Set implements a collection of unordered values with no duplicates.

···

On 1/15/07, Jason Mayer <slamboy@gmail.com> wrote:

I'm just curious if there's any way to duplicate values in a set. After
quiz 108, I modified my submission so that it was a fully functional game.

I then passed around my finished program to some of my coworkers who are
interested in ruby. After a few days, someone came back to me with a bug,
and this appears to be the root cause of that bug.

irb(main):001:0> target = "stuff"
=> "stuff"
irb(main):002:0> a = target.split(//).sort
=> ["f", "f", "s", "t", "u"]
irb(main):003:0> require 'Set'
=> true
irb(main):004:0> s1 = Set.new(a)
=> #<Set: {"f", "s", "t", "u"}>

As it stands, if the word ffffuuuuussssstttt existed, it would be
considered
a subset of a. How do you avoid this using sets?

You shouldn't really have to avoid this. The 6 letter word should be 6 unique letters, otherwise how would there be 6 letters for the user to guess?

Dan

Jason Mayer wrote:

···

I'm just curious if there's any way to duplicate values in a set. After
quiz 108, I modified my submission so that it was a fully functional game.
I then passed around my finished program to some of my coworkers who are
interested in ruby. After a few days, someone came back to me with a bug,
and this appears to be the root cause of that bug.

irb(main):001:0> target = "stuff"
=> "stuff"
irb(main):002:0> a = target.split(//).sort
=> ["f", "f", "s", "t", "u"]
irb(main):003:0> require 'Set'
=> true
irb(main):004:0> s1 = Set.new(a)
=> #<Set: {"f", "s", "t", "u"}>

As it stands, if the word ffffuuuuussssstttt existed, it would be considered
a subset of a. How do you avoid this using sets?

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

[*] Multiset -- from Wolfram MathWorld

···

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

Set implements a collection of unordered values with no duplicates.

So here's what one of my coworkers sent to me:

Current score: 5900
Incorrect: 2
EIINSS
17 possible words left!
word:inn
Current score: 5990
Incorrect: 0

In this case, "inn".split(//).sort would be s2, and @s1 would be
EIINSS.split(//). N did not appear in the word list twice, but the part of
my code that said if s2.subset?(@s1) returned true because the actual values
compared were
s2= Set: {"i", "n"}
@s1 = Set: {"e", "i", "n", "s"}
s2 is in fact a subset of @s1, but if Set allowed for multiple non-unique
values (i.e. {"i", "n", "n"}) then it wouldn't have been the case.

In the end, it doesn't matter... I was just looking to make a game for me
and my coworkers. Tech support is boring. But maybe finding all the words
in seisin is more boring. I don't know.

···

On 1/15/07, Daniel Finnie <danfinnie@optonline.net> wrote:

You shouldn't really have to avoid this. The 6 letter word should be 6
unique letters, otherwise how would there be 6 letters for the user to
guess?

Dan

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
...) :slight_smile:

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.

···

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.

--
Stefano Zacchiroli -*- Computer Science PhD student @ Uny Bologna, Italy
zack@{cs.unibo.it,debian.org,bononia.it} -%- http://www.bononia.it/zack/
(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

Answering to myself ...

    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 :frowning:

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

···

On Mon, Jan 15, 2007 at 10:29:11PM +0900, Stefano Zacchiroli wrote:

--
Stefano Zacchiroli -*- Computer Science PhD student @ Uny Bologna, Italy
zack@{cs.unibo.it,debian.org,bononia.it} -%- http://www.bononia.it/zack/
(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

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

···

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 :frowning:

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