Class: Algebra::Permutation

Inherits:
Object show all
Includes:
Powers, Enumerable
Defined in:
lib/algebra/permutation-group.rb

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Methods included from Powers

#**

Methods included from Enumerable

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

Constructor Details

#initialize(x) ⇒ Permutation 



57
58
59
 
# File 'lib/algebra/permutation-group.rb', line 57

def initialize(x)
  @perm = x
end

Instance Attribute Details

#perm ⇒ Object

Returns the value of attribute perm.



61
62
63
 
# File 'lib/algebra/permutation-group.rb', line 61

def perm
  @perm
end

Class Method Details

.[](*a) ⇒ Object 



49
50
51
 
# File 'lib/algebra/permutation-group.rb', line 49

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

.cyclic2perm(c, n = nil) ⇒ Object 



218
219
220
221
222
223
224
225
226
227
228
229
 
# File 'lib/algebra/permutation-group.rb', line 218

def self.cyclic2perm(c, n = nil)
  n = c.flatten.max + 1 unless n
  a = (0...n).collect do |i|
    c.each do |b|
      if j = b.index(i)
        i = b[(j + 1) % b.size]
      end
    end
    i
  end
  new(a)
end

.unity(d) ⇒ Object 



53
54
55
 
# File 'lib/algebra/permutation-group.rb', line 53

def self.unity(d)
  new((0...d).to_a)
end

Instance Method Details

#[](i) ⇒ Object Also known as: call 



95
96
97
 
# File 'lib/algebra/permutation-group.rb', line 95

def [](i)
  @perm[i] || i
end

#conjugate(g) ⇒ Object 



138
139
140
 
# File 'lib/algebra/permutation-group.rb', line 138

def conjugate(g)
  g * self * g.inverse
end

#decompose_cyclic ⇒ Object 



142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
# File 'lib/algebra/permutation-group.rb', line 142

def decompose_cyclic
  s = []
  remain = (0...size).to_a
  while f = remain.shift
    a = [f]
    i = f
    loop do
      j = self[i]
      if j == f
        s.push a if a.size > 1
        break
      else
        remain.delete j
        a.push j
        i = j
      end
    end
  end
  s
end

#decompose_transposition ⇒ Object 



197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
 
# File 'lib/algebra/permutation-group.rb', line 197

def decompose_transposition
  a = []
  (0...degree).each do |i|
    a << [i, self[i]]
  end
  r = []
  loop do
    a.delete_if { |i, x| i == x }
    break if a.empty?
    i, x = a.shift
    x, j = alpha = a.assoc(x)
    a.delete(alpha)
    unless j == i
      a.rassoc(i)[1] = j
      r.unshift [i, j]
    end
    r.unshift [i, x]
  end
  r
end

#degree ⇒ Object Also known as: size 



67
68
69
 
# File 'lib/algebra/permutation-group.rb', line 67

def degree
  @perm.size
end

#each(&b) ⇒ Object 



73
74
75
 
# File 'lib/algebra/permutation-group.rb', line 73

def each(&b)
  @perm.each(&b)
end

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



77
78
79
 
# File 'lib/algebra/permutation-group.rb', line 77

def eql?(other)
  @perm.eql?(other.perm)
end

#hash ⇒ Object 



83
84
85
 
# File 'lib/algebra/permutation-group.rb', line 83

def hash
  @perm.hash
end

#index(i) ⇒ Object

def []=(i, x); @perm = x; end



103
104
105
 
# File 'lib/algebra/permutation-group.rb', line 103

def index(i)
  @perm.index(i)
end

#inspect ⇒ Object 



87
88
89
 
# File 'lib/algebra/permutation-group.rb', line 87

def inspect
  @perm.inspect
end

#inverse ⇒ Object Also known as: inv

alias * left_act



119
120
121
 
# File 'lib/algebra/permutation-group.rb', line 119

def inverse
  self.class.new((0...degree).collect { |i| index(i) })
end

#left_act(other) ⇒ Object 



113
114
115
 
# File 'lib/algebra/permutation-group.rb', line 113

def left_act(other)
  self.class.new(other.collect { |i| self[i] })
end

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

permutation’s traditional product (g*h) == h[g]



107
108
109
 
# File 'lib/algebra/permutation-group.rb', line 107

def right_act(other) # permutation's traditional product (g*h)[x] == h[g[x]]
  self.class.new(collect { |i| other[i] })
end

#sign ⇒ Object 



125
126
127
128
129
130
131
132
133
134
135
136
 
# File 'lib/algebra/permutation-group.rb', line 125

def sign
  a = perm.dup
  b = inverse.perm
  s = 1
  (0...(degree - 1)).each do |i|
    next unless (j = a[i]) != i
    a[b[i]] = j
    b[j] = b[i]
    s = -s
  end
  s
end

#to_map ⇒ Object

require “algebra/finite-map”



189
190
191
192
193
194
195
 
# File 'lib/algebra/permutation-group.rb', line 189

def to_map
  m = Map.phi
  @perm.each_with_index do |x, i|
    m.append!(i, x)
  end
  m
end

#to_s ⇒ Object 



91
92
93
 
# File 'lib/algebra/permutation-group.rb', line 91

def to_s
  @perm.inspect
end

#unity ⇒ Object 



63
64
65
 
# File 'lib/algebra/permutation-group.rb', line 63

def unity
  self.class.unity(@perm.size)
end