Class: MoreMath::Permutation

Inherits:
Object
  • Object
show all
Includes:
Comparable, Enumerable, RankingCommon
Defined in:
lib/more_math/permutation.rb

Instance Attribute Summary

Attributes included from RankingCommon

#collection, #last, #rank, #size

Class Method Summary collapse

Instance Method Summary collapse

Methods included from RankingCommon

#each, #each!, #next, #next!, #pred, #pred!, #random, #random!

Constructor Details

#initialize(size, rank = 0) ⇒ Permutation

Creates a new Permutation instance of size (and ranked with rank).



11
12
13
14
 
# File 'lib/more_math/permutation.rb', line 11

def initialize(size, rank = 0)
  @size, self.rank = size, rank
  @last = factorial(size) - 1
end

Class Method Details

.for(collection, rank = 0) ⇒ Object

A permutation instance of size collection.size is created with collection as the default Permutation#project data object. A collection should respond to size, [], and []=. The Permutation instance will default to rank 0 if none is given.



48
49
50
51
52
 
# File 'lib/more_math/permutation.rb', line 48

def self.for(collection, rank = 0)
  perm = new(collection.size, rank)
  perm.instance_variable_set(:@collection, collection)
  perm
end

.for_mapping(a, b) ⇒ Object

Builds a permutation that maps a into b. Both arguments must be the same length and must contain the same elements. If these arrays contain duplicate elements, the solution will not be unique.



70
71
72
73
74
75
76
77
78
79
80
81
82
 
# File 'lib/more_math/permutation.rb', line 70

def self.for_mapping(a, b)
  a.size == b.size or
    raise ArgumentError, "Initial and final lists must be the same length"

  lookup = Hash.new { |h, k| h[k] = [] }
  a.size.times { |i| lookup[a[i]] <<= i }

  value = Array.new(b.size) do |i|
    e = b[i]
    lookup[e].pop or raise ArgumentError, "no corresponding element for #{e.inspect}"
  end
  Permutation.from_value value
end

.from_cycles(cycles, max = 0) ⇒ Object

Creates a new Permutation instance from the Array of Arrays cycles. This is for example the result of a call to the Permutation#cycles method .



32
33
34
35
36
37
38
39
40
41
42
 
# File 'lib/more_math/permutation.rb', line 32

def self.from_cycles(cycles, max = 0)
  indices = Array.new(max)
  cycles.each do |cycle|
    cycle.empty? and next
    for i in 0...cycle.size
      indices[ cycle[i - 1] ] = cycle[i]
    end
  end
  indices.each_with_index { |r, i| r or indices[i] = i }
  from_value(indices)
end

.from_value(indices) ⇒ Object

Creates a new Permutation instance from the Array indices, that should consist of a permutation of Fixnums in the range of 0 and indices.size - 1. This is for example the result of a call to the Permutation#value method.



20
21
22
23
24
25
26
27
 
# File 'lib/more_math/permutation.rb', line 20

def self.from_value(indices)
  indices = indices.clone
  obj = new(indices.size)
  obj.instance_eval do
    self.rank = rank_indices(indices)
  end
  obj
end

.identity(n) ⇒ Object

Shortcut to generate the identity permutation that has Permutation#size n.



56
57
58
 
# File 'lib/more_math/permutation.rb', line 56

def self.identity(n)
  new(n)
end

Instance Method Details

#<=>(other) ⇒ Object

Compares to Permutation instances according to their Permutation#size and the Permutation#rank.

The mixed in methods from the Comparable module rely on this method.



144
145
146
 
# File 'lib/more_math/permutation.rb', line 144

def <=>(other)
  size <=> other.size.zero? || rank <=> other.rank
end

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

Compose this Permutation instance and the other to a new Permutation. Note that a permutation composed with it’s inverted permutation yields the identity permutation, the permutation with rank 0.

Example:

p1 = Permutation.new(5, 42)
# => #<Permutation:0x75370 @last=119, @rank=42, @size=5>
p2 = p1.invert
# => #<Permutation:0x653d0 @last=119, @rank=51, @size=5>
p1.compose(p2)
=> #<Permutation:0x639a4 @last=119, @rank=0, @size=5>

Or a little nicer to look at:

p1 * -p1
# => #<Permutation:0x62004 @last=119, @rank=0, @size=5>



197
198
199
200
201
202
203
204
205
 
# File 'lib/more_math/permutation.rb', line 197

def compose(other)
  size == other.size or raise ArgumentError,
    "permutations of unequal sizes cannot be composed!"
  indices = value
  composed = other.value.map { |i| indices[i] }
  klon = clone
  klon.rank = rank_indices(composed)
  klon
end

#cycles ⇒ Object

Returns the cycles representation of this Permutation instance. The return value of this method can be used to create a new Permutation instance with the Permutation.from_cycles method.

Example:

perm = Permutation.new(7, 23)
# => #<Permutation:0x58541c @last=5039, @rank=23, @size=7>
perm.cycles
# => [[3, 6], [4, 5]]



218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
 
# File 'lib/more_math/permutation.rb', line 218

def cycles
  perm = value
  result = [[]]
  seen = {}
  current = nil
  loop do
    current or current = perm.find { |x| !seen[x] }
    break unless current
    if seen[current]
      current = nil
      result << []
    else
      seen[current] = true
      result[-1] << current
      current = perm[current]
    end
  end
  result.pop
  result.select { |c| c.size > 1 }.map do |c|
    min_index = c.index(c.min)
    c[min_index..-1] + c[0...min_index]
  end
end

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

Returns true if this Permutation instance and the other have the same value, that is both Permutation instances have the same Permutation#size and the same Permutation#rank.

Returns:

  • (Boolean) 


151
152
153
 
# File 'lib/more_math/permutation.rb', line 151

def eql?(other)
  self.class == other.class && size == other.size && rank == other.rank
end

#even? ⇒ Boolean

Returns true if this permutation is even, false otherwise.

Returns:

  • (Boolean) 


260
261
262
 
# File 'lib/more_math/permutation.rb', line 260

def even?
  signum == 1
end

#hash ⇒ Object

Computes a unique hash value for this Permutation instance.



158
159
160
 
# File 'lib/more_math/permutation.rb', line 158

def hash
  size.hash ^ rank.hash
end

#identity ⇒ Object

Returns the identity permutation that has the same Permutation#size as this instance.



62
63
64
 
# File 'lib/more_math/permutation.rb', line 62

def identity
  self.class.new(size)
end

#invert ⇒ Object Also known as: -@

Returns the inverted Permutation of this Permutation instance. (See Permutation#compose for an example.)



176
177
178
 
# File 'lib/more_math/permutation.rb', line 176

def invert
  clone.invert!
end

#invert! ⇒ Object

Switchtes this Permutation instance to the inverted permutation. (See Permutation#compose for an example.)



164
165
166
167
168
169
170
171
172
 
# File 'lib/more_math/permutation.rb', line 164

def invert!
  indices = unrank_indices(rank)
  inverted = Array.new(size)
  for i in 0...size
    inverted[indices[i]] = i
  end
  self.rank = rank_indices(inverted)
  self
end

#odd? ⇒ Boolean

Returns true if this permutation is odd, false otherwise.

Returns:

  • (Boolean) 


265
266
267
 
# File 'lib/more_math/permutation.rb', line 265

def odd?
  signum == -1
end

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

Computes the nth power (ie the nth repeated permutation) of this instance. Negative powers are taken to be powers of the inverse.



86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/more_math/permutation.rb', line 86

def power(n)
  if n.respond_to?(:to_int)
    n = n.to_int
  else
    raise TypeError, "#{n.inspect} cannot be converted to an integer"
  end
  if n >= 0
    (1..n).inject(identity) { |p, e| p * self }
  else # negative powers are taken to be powers of the inverse
    -power(-n)
  end
end

#project(data = (@collection if defined? @collection)) ⇒ Object

Returns the projection of this instance’s Permutation#value into the data object that should respond to the #[] method. If this Permutation inbstance was created with Permutation.for the collection used to create it is used as a data object.

Example:

perm = Permutation.new(6, 312)
# => #<Permutation:0x6ae34 @last=719, @rank=312, @size=6>
perm.project("abcdef")
# => "ceabdf"

Raises:

  • (ArgumentError) 


132
133
134
135
136
137
138
 
# File 'lib/more_math/permutation.rb', line 132

def project(data = (@collection if defined? @collection))
  data or raise ArgumentError, "a collection is required to project"
  raise ArgumentError, "data size is != #{size}!" if data.size != size
  projection = data.clone
  value.each_with_index { |i, j| projection[j] = data[i] }
  projection
end

#rank=(m) ⇒ Object

Assigns m to the rank attribute of this Permutation instance. That implies that the indices produced by a call to the Permutation#value method of this instance is the permutation ranked with this new rank.



105
106
107
 
# File 'lib/more_math/permutation.rb', line 105

def rank=(m)
  @rank = m % factorial(size)
end

#signum ⇒ Object Also known as: sgn

Returns the signum of this Permutation instance. It’s -1 if this permutation is odd and 1 if it’s an even permutation.

A permutation is odd if it can be represented by an odd number of transpositions (cycles of length 2), or even if it can be represented of an even number of transpositions.



249
250
251
252
253
254
255
 
# File 'lib/more_math/permutation.rb', line 249

def signum
  s = 1
  cycles.each do |c|
    c.size % 2 == 0 and s *= -1
  end
  s
end

#value ⇒ Object

Returns the indices in the range of 0 to Permutation#size - 1 of this permutation that is ranked with Permutation#rank.

Example:

perm = Permutation.new(6, 312)
# => #<Permutation:0x6ae34 @last=719, @rank=312, @size=6>
perm.value
# => [2, 4, 0, 1, 3, 5]



117
118
119
 
# File 'lib/more_math/permutation.rb', line 117

def value
  unrank_indices(@rank)
end