Class: Algebra::Set

Inherits:
Object show all
Includes:
OperatorDomain, Enumerable
Defined in:
lib/algebra/finite-set.rb,
lib/algebra/finite-group.rb

Direct Known Subclasses

Group, Map

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from OperatorDomain

#left_act, #left_orbit!, #left_quotient, #left_representatives, #right_act, #right_orbit!, #right_quotient, #right_representatives

Methods included from Enumerable

#all?, #any?, #collecti, #sum

Constructor Details

#initialize(*m) ⇒ Set

Returns a new instance of Set.



28
29
30
31
32
33
 
# File 'lib/algebra/finite-set.rb', line 28

def initialize(*m)
  @body = {}
  m.each do |x|
    @body.store(x, true)
  end
end

Instance Attribute Details

#body ⇒ Object

Returns the value of attribute body.



34
35
36
 
# File 'lib/algebra/finite-set.rb', line 34

def body
  @body
end

Class Method Details

.[](*a) ⇒ Object 



13
14
15
 
# File 'lib/algebra/finite-set.rb', line 13

def self.[](*a)
  new(*a)
end

.empty_set ⇒ Object 



36
37
38
 
# File 'lib/algebra/finite-set.rb', line 36

def self.empty_set
  new
end

.new_a(a) ⇒ Object 



17
18
19
 
# File 'lib/algebra/finite-set.rb', line 17

def self.new_a(a)
  new(*a)
end

.new_h(h) ⇒ Object 



21
22
23
24
25
26
 
# File 'lib/algebra/finite-set.rb', line 21

def self.new_h(h)
  new.instance_eval do
    @body = h
    self
  end
end

.null ⇒ Object 



42
43
44
 
# File 'lib/algebra/finite-set.rb', line 42

def self.empty_set
  new
end

.phi ⇒ Object 



41
42
43
 
# File 'lib/algebra/finite-set.rb', line 41

def self.empty_set
  new
end

.singleton(x) ⇒ Object 



45
46
47
 
# File 'lib/algebra/finite-set.rb', line 45

def self.singleton(x)
  new(x)
end

Instance Method Details

#<(other) ⇒ Object 



182
183
184
 
# File 'lib/algebra/finite-set.rb', line 182

def <(other)
  self <= other && size < other.size
end

#>(other) ⇒ Object 



186
187
188
 
# File 'lib/algebra/finite-set.rb', line 186

def >(other)
  self >= other && size > other.size
end

#append(x) ⇒ Object 



124
125
126
 
# File 'lib/algebra/finite-set.rb', line 124

def append(x)
  dup.append!(x)
end

#append!(x) ⇒ Object Also known as: push, << 



116
117
118
119
 
# File 'lib/algebra/finite-set.rb', line 116

def append!(x)
  @body.store(x, true)
  self
end

#bijections(other) ⇒ Object 



437
438
439
 
# File 'lib/algebra/finite-set.rb', line 437

def bijections(other)
  size == other.size ? injections(other) : Set[]
end

#cast(klass = Set) ⇒ Object 



49
50
51
52
53
54
55
56
57
 
# 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) ⇒ Object 



128
129
130
131
132
133
134
135
136
137
138
139
140
 
# 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

#decreasing_series(x = self) ⇒ Object 



121
122
123
124
125
126
127
128
129
130
131
 
# 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) ⇒ Object Also known as: - 



208
209
210
211
212
 
# 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

#dup ⇒ Object 



112
113
114
 
# File 'lib/algebra/finite-set.rb', line 112

def dup
  self.class.new(*to_a)
end

#each(&b) ⇒ Object 



86
87
88
 
# File 'lib/algebra/finite-set.rb', line 86

def each(&b)
  @body.each_key(&b)
end

#each_member(n) ⇒ Object 



247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
 
# 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 ⇒ Object

each without empty set and total set



272
273
274
275
276
277
 
# 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 ⇒ Object 



237
238
239
240
241
242
243
244
245
 
# 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) ⇒ Object 



300
301
302
303
304
305
306
 
# 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| ... } ⇒ Object

Yields:



265
266
267
268
269
270
 
# File 'lib/algebra/finite-set.rb', line 265

def each_subset
  yield phi
  _each_subset do |s|
    yield s
  end
end

#empty? ⇒ Boolean Also known as: phi?, empty_set?, nul?

Returns:

  • (Boolean) 


78
79
80
 
# File 'lib/algebra/finite-set.rb', line 78

def empty?
  @body.empty?
end

#empty_set ⇒ Object Also known as: phi, null 



59
60
61
 
# File 'lib/algebra/finite-set.rb', line 59

def empty_set
  self.class.new
end

#eql?(other) ⇒ Boolean Also known as: ==

Returns:

  • (Boolean) 


146
147
148
 
# File 'lib/algebra/finite-set.rb', line 146

def eql?(other)
  subset?(other) && superset?(other)
end

#equiv_class(equiv = nil) ⇒ Object 



323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
 
# 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

#hash ⇒ Object 



152
153
154
155
156
157
158
 
# 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 ⇒ Object 



401
402
403
404
405
406
407
 
# 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

#include?(x) ⇒ Boolean Also known as: member?, has?, contains?

Returns:

  • (Boolean) 


160
161
162
 
# File 'lib/algebra/finite-set.rb', line 160

def include?(x)
  @body.include?(x)
end

#increasing_series(x = unit_group) ⇒ Object 



109
110
111
112
113
114
115
116
117
118
119
 
# 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) ⇒ Object 



419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
 
# 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) ⇒ Object 



415
416
417
 
# File 'lib/algebra/finite-set.rb', line 415

def injections0(other)
  (self**other).separate(&:injective?)
end

#inspect ⇒ Object 



370
371
372
 
# File 'lib/algebra/finite-set.rb', line 370

def inspect
  '{' + @body.keys.collect(&:inspect).join(', ') + '}'
end

#intersection(other = nil) ⇒ Object Also known as: &, cap 



216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
 
# 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

#map_s(&b) ⇒ Object 



97
98
99
 
# File 'lib/algebra/finite-set.rb', line 97

def map_s(&b)
  self.class.new(*map(&b))
end

#pick ⇒ Object 



101
102
103
104
105
106
 
# File 'lib/algebra/finite-set.rb', line 101

def pick
  each do |x|
    return x
  end
  nil
end

#power(other) ⇒ Object Also known as: ** 



386
387
388
389
390
391
392
393
394
395
396
397
398
399
 
# 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

#power_set ⇒ Object 



292
293
294
295
296
297
298
 
# 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) ⇒ Object 



308
309
310
311
312
313
314
315
316
317
318
319
 
# 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

#rehash ⇒ Object 



142
143
144
 
# File 'lib/algebra/finite-set.rb', line 142

def rehash
  @body.rehash
end

#separate(&b) ⇒ Object Also known as: select_s, find_all_s 



90
91
92
 
# File 'lib/algebra/finite-set.rb', line 90

def separate(&b)
  self.class.new(*find_all(&b))
end

#shift ⇒ Object 



108
109
110
 
# File 'lib/algebra/finite-set.rb', line 108

def shift
  (x = @body.shift) && x.first
end

#singleton(x) ⇒ Object 



66
67
68
 
# File 'lib/algebra/finite-set.rb', line 66

def singleton(x)
  self.class.new(x)
end

#singleton? ⇒ Boolean

Returns:

  • (Boolean) 


70
71
72
 
# File 'lib/algebra/finite-set.rb', line 70

def singleton?
  size == 1
end

#size ⇒ Object 



74
75
76
 
# File 'lib/algebra/finite-set.rb', line 74

def size
  @body.size
end

#sort ⇒ Object 



382
383
384
 
# File 'lib/algebra/finite-set.rb', line 382

def sort
  to_a.sort
end

#subset?(other) ⇒ Boolean Also known as: <=, part_of?

self is a part of other

Returns:

  • (Boolean) 


175
176
177
 
# 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

#superset?(other) ⇒ Boolean Also known as: >=, incl?

self includes other

Returns:

  • (Boolean) 


168
169
170
 
# File 'lib/algebra/finite-set.rb', line 168

def superset?(other) # self includes other
  other.is_a?(Set) && other.all? { |x| member?(x) }
end

#surjections(other) ⇒ Object 



411
412
413
 
# File 'lib/algebra/finite-set.rb', line 411

def surjections(other)
  (self**other).separate(&:surjective?)
end

#to_a ⇒ Object 



374
375
376
 
# File 'lib/algebra/finite-set.rb', line 374

def to_a
  @body.keys
end

#to_ary ⇒ Object 



378
379
380
 
# File 'lib/algebra/finite-set.rb', line 378

def to_ary
  to_a
end

#to_s ⇒ Object 



366
367
368
 
# File 'lib/algebra/finite-set.rb', line 366

def to_s
  '{' + @body.keys.collect(&:inspect).join(', ') + '}'
end

#union(other = nil) ⇒ Object Also known as: |, +, cup 



190
191
192
193
194
195
196
197
198
199
200
201
202
 
# 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