Class: MoreMath::Permutation

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

Overview

A permutation represents a rearrangement of elements in a set. Permutations are ranked in lexicographic order, allowing efficient enumeration and indexing.

Examples:

Create a permutation of size 3

perm = Permutation.new(3)
# => #<Permutation:0x6ae34 @last=5, @rank=0, @size=3>

Create a permutation with specific rank

perm = Permutation.new(3, 5)
# => #<Permutation:0x6ae34 @last=5, @rank=5, @size=3>

Get the permutation as an array of indices

perm = Permutation.new(3, 5)
perm.value
# => [2, 1, 0]

Project onto actual data

perm = Permutation.new(3, 5)
perm.project(['a', 'b', 'c'])
# => ['c', 'b', 'a']

Constant Summary collapse

@@fcache = 
[ 1 ]

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). Creates a new Permutation instance of size (and ranked with rank).

Parameters:

  • size (Integer) —

    The size of the permutation

  • rank (Integer) (defaults to: 0) —

    The rank of the permutation (default: 0)



36
37
38
39
 
# File 'lib/more_math/permutation.rb', line 36

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

Class Method Details

.for(collection, rank = 0) ⇒ Permutation

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.

Parameters:

  • collection (Object) —

    collection to use for projection

  • rank (Integer) (defaults to: 0) —

    the rank of this permutation (default: 0)

Returns:



84
85
86
87
88
 
# File 'lib/more_math/permutation.rb', line 84

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

.for_mapping(a, b) ⇒ Permutation

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.

Parameters:

  • a (Array) —

    initial array of elements

  • b (Array) —

    target array of elements

Returns:



115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/more_math/permutation.rb', line 115

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) ⇒ Permutation

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 .

Parameters:

  • cycles (Array<Array<Integer>>) —

    array of cycles

  • max (Integer) (defaults to: 0) —

    maximum element index (default: 0)

Returns:



64
65
66
67
68
69
70
71
72
73
74
 
# File 'lib/more_math/permutation.rb', line 64

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) ⇒ Permutation

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.

Parameters:

  • indices (Array<Integer>) —

    array of indices representing a permutation

Returns:



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

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) ⇒ Permutation

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

Parameters:

  • n (Integer) —

    size of identity permutation

Returns:



95
96
97
 
# File 'lib/more_math/permutation.rb', line 95

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

Instance Method Details

#<=>(other) ⇒ Integer

Compare this permutation with another based on size and rank.

This method implements the comparison operator for Permutation objects, allowing them to be sorted and compared using standard Ruby comparison operators. The comparison is first done by size, then by rank for permutations of the same size.

Parameters:

  • other (Object) —

    the other permutation to compare with

Returns:

  • (Integer) —

    -1 if this permutation should be ordered before the other, 0 if they are equal, 1 if this permutation should be ordered after the other



206
207
208
209
210
211
212
213
 
# File 'lib/more_math/permutation.rb', line 206

def <=>(other)
  sc = size <=> other.size
  if sc.zero?
    rank <=> other.rank
  else
    sc
  end
end

#compose(other) ⇒ Permutation 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.

Examples:

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>

Parameters:

Returns:



277
278
279
280
281
282
283
284
285
 
# File 'lib/more_math/permutation.rb', line 277

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 ⇒ Array<Array<Integer>>

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.

Examples:

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

Returns:

  • (Array<Array<Integer>>) —

    array of cycles



300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
 
# File 'lib/more_math/permutation.rb', line 300

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.

Parameters:

  • other (Object) —

    object to compare with

Returns:

  • (Boolean) —

    true if equal



221
222
223
 
# File 'lib/more_math/permutation.rb', line 221

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) —

    true if even permutation



346
347
348
 
# File 'lib/more_math/permutation.rb', line 346

def even?
  signum == 1
end

#factorial(n) ⇒ Integer (private)

Computes the factorial of a number using memoization for efficiency. This method is used internally by the permutation ranking system to calculate the total number of permutations for a given size.

Parameters:

  • n (Integer) —

    the number to calculate factorial for

Returns:

  • (Integer) —

    the factorial of n



367
368
369
370
 
# File 'lib/more_math/permutation.rb', line 367

def factorial(n)
  @@fcache.size.upto(n) { |i| @@fcache[i] =  i * @@fcache[i - 1] }
  @@fcache[n]
end

#hash ⇒ Integer

Computes a unique hash value for this Permutation instance.

Returns:

  • (Integer) —

    hash value



230
231
232
 
# File 'lib/more_math/permutation.rb', line 230

def hash
  size.hash ^ rank.hash
end

#identity ⇒ Permutation

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

Returns:



103
104
105
 
# File 'lib/more_math/permutation.rb', line 103

def identity
  self.class.new(size)
end

#invert ⇒ Permutation Also known as: -@

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

Returns:



252
253
254
 
# File 'lib/more_math/permutation.rb', line 252

def invert
  clone.invert!
end

#invert! ⇒ Permutation

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

Returns:



238
239
240
241
242
243
244
245
246
 
# File 'lib/more_math/permutation.rb', line 238

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) —

    true if odd permutation



353
354
355
 
# File 'lib/more_math/permutation.rb', line 353

def odd?
  signum == -1
end

#power(n) ⇒ Permutation 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.

Parameters:

  • n (Integer) —

    power to raise permutation to

Returns:

  • (Permutation) —

    result of permutation raised to power n



134
135
136
137
138
139
140
141
142
143
144
145
 
# File 'lib/more_math/permutation.rb', line 134

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.

Examples:

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

Parameters:

  • data (Object) (defaults to: (@collection if defined? @collection)) —

    data to project onto (optional)

Returns:

  • (Object) —

    projected result

Raises:

  • (ArgumentError) 


188
189
190
191
192
193
194
 
# File 'lib/more_math/permutation.rb', line 188

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.dup
  value.each_with_index { |i, j| projection[j] = data[i] }
  projection
end

#rank=(m) ⇒ Integer

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.

Parameters:

  • m (Integer) —

    new rank value

Returns:

  • (Integer) —

    assigned rank



156
157
158
 
# File 'lib/more_math/permutation.rb', line 156

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

#rank_indices(p) ⇒ Integer (private)

Rank the indices of the permutation p. Beware that this method may change its argument p. Rank the indices of the permutation p. Beware that this method may change its argument p.

Parameters:

  • p (Array<Integer>) —

    the permutation indices to rank

Returns:

  • (Integer) —

    the rank of the permutation indices



378
379
380
381
382
383
384
385
386
387
 
# File 'lib/more_math/permutation.rb', line 378

def rank_indices(p)
  result = 0
  for i in 0...size
    result += p[i] * factorial(size - i - 1)
    for j in (i + 1)...size
      p[j] -= 1 if p[j] > p[i]
    end
  end
  result
end

#signum ⇒ Integer 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.

Returns:

  • (Integer) —

    1 for even, -1 for odd



333
334
335
336
337
338
339
 
# File 'lib/more_math/permutation.rb', line 333

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

#unrank_indices(m) ⇒ Array<Integer> (private)

Unranks the given index value into an array of permutation indices.

This method converts a rank value back into its corresponding permutation indices representation. It’s the inverse operation of the rank_indices method and is used internally by the permutation ranking system to reconstruct permutation arrays from their rank values.

Parameters:

  • m (Integer) —

    The rank value to unrank

Returns:

  • (Array<Integer>) —

    Array of indices representing the permutation



398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
 
# File 'lib/more_math/permutation.rb', line 398

def unrank_indices(m)
  result = Array.new(size, 0)
  for i in 0...size
    f = factorial(i)
    x = m % (f * (i + 1))
    m -= x
    x /= f
    result[size - i - 1] = x
    x -= 1
    for j in (size - i)...size
      result[j] += 1 if result[j] > x
    end
  end
  result
end

#value ⇒ Array<Integer>

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]

Returns:

  • (Array<Integer>) —

    array of indices representing this permutation



170
171
172
 
# File 'lib/more_math/permutation.rb', line 170

def value
  unrank_indices(@rank)
end