class Algebra::Set

Attributes

body[RW]

Public Class Methods

[](*a) click to toggle source
# File lib/algebra/finite-set.rb, line 13
def self.[](*a)
  new(*a)
end
empty_set() click to toggle source
# File lib/algebra/finite-set.rb, line 36
def self.empty_set
  new
end
Also aliased as: phi, null
new(*m) click to toggle source
# File lib/algebra/finite-set.rb, line 28
def initialize(*m)
  @body = {}
  m.each do |x|
    @body.store(x, true)
  end
end
new_a(a) click to toggle source
# File lib/algebra/finite-set.rb, line 17
def self.new_a(a)
  new(*a)
end
new_h(h) click to toggle source
# File lib/algebra/finite-set.rb, line 21
def self.new_h(h)
  new.instance_eval do
    @body = h
    self
  end
end
null()
Alias for: empty_set
phi()
Alias for: empty_set
singleton(x) click to toggle source
# File lib/algebra/finite-set.rb, line 45
def self.singleton(x)
  new(x)
end

Public Instance Methods

&(other = nil)
Alias for: intersection
*(other, s = phi)
Alias for: product
**(other)
Alias for: power
+(other = nil)
Alias for: union
-(other)
Alias for: difference
/(equiv = nil)
Alias for: equiv_class
<(other) click to toggle source
# File lib/algebra/finite-set.rb, line 182
def <(other)
  self <= other && size < other.size
end
<<(x)
Alias for: append!
<=(other)
Alias for: subset?
==(other)
Alias for: eql?
>(other) click to toggle source
# File lib/algebra/finite-set.rb, line 186
def >(other)
  self >= other && size > other.size
end
>=(other)
Alias for: superset?
append(x) click to toggle source
# File lib/algebra/finite-set.rb, line 124
def append(x)
  dup.append!(x)
end
append!(x) click to toggle source
# File lib/algebra/finite-set.rb, line 116
def append!(x)
  @body.store(x, true)
  self
end
Also aliased as: push, <<
bijections(other) click to toggle source
# File lib/algebra/finite-set.rb, line 437
def bijections(other)
  size == other.size ? injections(other) : Set[]
end
cap(other = nil)
Alias for: intersection
cast(klass = Set) { || ... } click to toggle source
# File lib/algebra/finite-set.rb, line 49
def cast(klass = Set)
  x = klass.new_h(@body)
  if block_given?
    x.instance_eval do
      yield
    end
  end
  x
end
concat(other) click to toggle source
# File lib/algebra/finite-set.rb, line 128
def concat(other)
  case other
  when Set
    @body.update other.body
  when Array
    other.each do |x|
      append!(x)
    end
  else
    raise "unknown self.class #{other.class}"
  end
  self
end
contains?(x)
Alias for: include?
cup(other = nil)
Alias for: union
decreasing_series(x = self) { |x)| ... } click to toggle source
# File lib/algebra/finite-group.rb, line 121
def decreasing_series(x = self)
  a = []
  loop do
    a.push x
    if x <= (y = yield x)
      break
    end
    x = y
  end
  a
end
difference(other) click to toggle source
# File lib/algebra/finite-set.rb, line 208
def difference(other)
  h = @body.dup
  h.delete_if { |k, _v| other.include?(k) }
  self.class.new_h(h)
end
Also aliased as: -
dup() click to toggle source
# File lib/algebra/finite-set.rb, line 112
def dup
  self.class.new(*to_a)
end
each(&b) click to toggle source
# File lib/algebra/finite-set.rb, line 86
def each(&b)
  @body.each_key(&b)
end
each_member(n) { || ... } click to toggle source
# File lib/algebra/finite-set.rb, line 247
def each_member(n)
  if n == 0
    yield []
  elsif n == 1 # redundant but effective
    each do |x|
      yield [x]
    end
  else
    stock = self.class[]
    each do |x|
      stock.each_member(n - 1) do |a|
        yield a + [x]
      end
      stock.push x
    end
  end
end
each_non_trivial_subset() { |x| ... } click to toggle source
# File lib/algebra/finite-set.rb, line 272
def each_non_trivial_subset # each without empty set and total set
  n = size
  _each_subset do |x|
    yield x unless x.size == n
  end
end
each_pair() { |a, x| ... } click to toggle source
# File lib/algebra/finite-set.rb, line 237
def each_pair
  stock = []
  each do |x|
    stock.each do |a|
      yield a, x
    end
    stock.push x
  end
end
each_product(other) { |x, y| ... } click to toggle source
# File lib/algebra/finite-set.rb, line 300
def each_product(other)
  each do |x|
    other.each do |y|
      yield [x, y]
    end
  end
end
each_subset() { |phi| ... } click to toggle source
# File lib/algebra/finite-set.rb, line 265
def each_subset
  yield phi
  _each_subset do |s|
    yield s
  end
end
empty?() click to toggle source
# File lib/algebra/finite-set.rb, line 78
def empty?
  @body.empty?
end
Also aliased as: phi?, empty_set?, nul?
empty_set() click to toggle source
# File lib/algebra/finite-set.rb, line 59
def empty_set
  self.class.new
end
Also aliased as: phi, null
empty_set?()
Alias for: empty?
eql?(other) click to toggle source
# File lib/algebra/finite-set.rb, line 146
def eql?(other)
  subset?(other) && superset?(other)
end
Also aliased as: ==
equiv_class(equiv = nil) { |pick, e| ... } click to toggle source
# File lib/algebra/finite-set.rb, line 323
def equiv_class(equiv = nil)
  classes = Set.phi
  if equiv && equiv.is_a?(Symbol) && !block_given?
    each do |e|
      if c = classes.find do |s|
           send(equiv, s.pick, e)
         end
        c.push e
        classes.rehash
      else
        classes.push singleton(e)
      end
    end
  elsif equiv && !block_given?
    each do |e|
      if c = classes.find do |s|
           equiv.call(s.pick, e)
         end
        c.push e
        classes.rehash
      else
        classes.push singleton(e)
      end
    end
  elsif !equiv && block_given?
    each do |e|
      if c = classes.find do |s|
           yield(s.pick, e)
         end
        c.push e
        classes.rehash
      else
        classes.push singleton(e)
      end
    end
  else
    raise "illegal call `equiv_class'"
  end
  classes
end
Also aliased as: /
find_all_s(&b)
Alias for: separate
has?(x)
Alias for: include?
hash() click to toggle source
# File lib/algebra/finite-set.rb, line 152
def hash
  s = 0
  @body.each_key do |k|
    s ^= k.hash
  end
  s
end
identity_map() click to toggle source
# File lib/algebra/finite-set.rb, line 401
def identity_map
  a = Map.phi(self)
  each do |x|
    a.append!(x, x)
  end
  a
end
incl?(other)
Alias for: superset?
include?(x) click to toggle source
# File lib/algebra/finite-set.rb, line 160
def include?(x)
  @body.include?(x)
end
Also aliased as: member?, has?, contains?
increasing_series(x = unit_group) { |x)| ... } click to toggle source
# File lib/algebra/finite-group.rb, line 109
def increasing_series(x = unit_group)
  a = []
  loop do
    a.push x
    if x >= (y = yield x)
      break
    end
    x = y
  end
  a
end
injections(other) click to toggle source
# File lib/algebra/finite-set.rb, line 419
def injections(other)
  maps = Set[]
  if size < other.size
    phi
  elsif other.empty?
    maps.push Map.phi(self)
  else
    each do |x|
      a = self - self.class[x]
      o = other.dup
      h = o.shift
      maps.concat a.injections(other)
      maps.concat a.injections(o).map_s { |m| m.append(h, x) }
    end
  end
  maps
end
injections0(other) click to toggle source
# File lib/algebra/finite-set.rb, line 415
def injections0(other)
  (self**other).separate(&:injective?)
end
inspect() click to toggle source
# File lib/algebra/finite-set.rb, line 370
def inspect
  '{' + @body.keys.collect(&:inspect).join(', ') + '}'
end
intersection(other = nil) click to toggle source
# File lib/algebra/finite-set.rb, line 216
def intersection(other = nil)
  if other
    h = @body.dup
    h.delete_if { |k, _v| !other.include?(k) }
    self.class.new_h(h)
  else
    i = nil # nil is a universe?
    each do |s|
      i = if i.nil?
            s
          else
            i.intersection(s)
          end
    end
    i
  end
end
Also aliased as: &, cap
map_s(&b) click to toggle source
# File lib/algebra/finite-set.rb, line 97
def map_s(&b)
  self.class.new(*map(&b))
end
member?(x)
Alias for: include?
nul?()
Alias for: empty?
null()
Alias for: empty_set
part_of?(other)
Alias for: subset?
phi()
Alias for: empty_set
phi?()
Alias for: empty?
pick() click to toggle source
# File lib/algebra/finite-set.rb, line 101
def pick
  each do |x|
    return x
  end
  nil
end
power(other) click to toggle source
# File lib/algebra/finite-set.rb, line 386
def power(other)
  a = Map.phi(self)
  s = [a]
  other.each do |x|
    tmp = []
    each do |y|
      s.each do |m|
        tmp << m.append(x, y)
      end
    end
    s = tmp
  end
  self.class[*s]
end
Also aliased as: **
power_set() click to toggle source
# File lib/algebra/finite-set.rb, line 292
def power_set
  s = phi
  each_subset do |u|
    s.append! u
  end
  s
end
product(other, s = phi) { |x, y| ... } click to toggle source
# File lib/algebra/finite-set.rb, line 308
def product(other, s = phi)
  if block_given?
    each_product(other) do |x, y|
      s.append! yield(x, y)
    end
  else
    each_product(other) do |x, y|
      s.append! [x, y]
    end
  end
  s
end
Also aliased as: *
push(x)
Alias for: append!
rehash() click to toggle source
# File lib/algebra/finite-set.rb, line 142
def rehash
  @body.rehash
end
select_s(&b)
Alias for: separate
separate(&b) click to toggle source
# File lib/algebra/finite-set.rb, line 90
def separate(&b)
  self.class.new(*find_all(&b))
end
Also aliased as: select_s, find_all_s
shift() click to toggle source
# File lib/algebra/finite-set.rb, line 108
def shift
  (x = @body.shift) && x.first
end
singleton(x) click to toggle source
# File lib/algebra/finite-set.rb, line 66
def singleton(x)
  self.class.new(x)
end
singleton?() click to toggle source
# File lib/algebra/finite-set.rb, line 70
def singleton?
  size == 1
end
size() click to toggle source
# File lib/algebra/finite-set.rb, line 74
def size
  @body.size
end
sort() click to toggle source
# File lib/algebra/finite-set.rb, line 382
def sort
  to_a.sort
end
subset?(other) click to toggle source
# File lib/algebra/finite-set.rb, line 175
def subset?(other) # self is a part of other
  other.is_a?(Set) && all? { |x| other.member?(x) }
end
Also aliased as: <=, part_of?
superset?(other) click to toggle source
# File lib/algebra/finite-set.rb, line 168
def superset?(other) # self includes other
  other.is_a?(Set) && other.all? { |x| member?(x) }
end
Also aliased as: >=, incl?
surjections(other) click to toggle source
# File lib/algebra/finite-set.rb, line 411
def surjections(other)
  (self**other).separate(&:surjective?)
end
to_a() click to toggle source
# File lib/algebra/finite-set.rb, line 374
def to_a
  @body.keys
end
to_ary() click to toggle source
# File lib/algebra/finite-set.rb, line 378
def to_ary
  to_a
end
to_s() click to toggle source
# File lib/algebra/finite-set.rb, line 366
def to_s
  '{' + @body.keys.collect(&:inspect).join(', ') + '}'
end
union(other = nil) click to toggle source
# File lib/algebra/finite-set.rb, line 190
def union(other = nil)
  if other
    h = @body.dup
    h.update other.body
    self.class.new_h(h)
  else
    u = phi
    each do |s|
      u = u.union(s)
    end
    u
  end
end
Also aliased as: |, +, cup
|(other = nil)
Alias for: union

Protected Instance Methods

_each_subset() { |class| ... } click to toggle source
# File lib/algebra/finite-set.rb, line 279
def _each_subset
  stock = phi
  each do |x|
    yield self.class[x]
    stock._each_subset do |a|
      yield a + self.class[x]
    end
    stock.push x
  end
  stock
end