Permutation

Constants

VERSION: Permutation version

Attributes

size[R]

Returns the size of this permutation, a Fixnum.

rank[R]

Returns the size of this permutation, a Fixnum in the range of 0 and Permutation#last.

last[R]

Returns the rank of the last ranked Permutation of size Permutation#size .

Public Class Methods

for(collection, rank = 0) click to toggle source

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.

# File lib/permutation.rb, line 43
  def self.for(collection, rank = 0)
    perm = new(collection.size, rank)
    perm.instance_variable_set(:@collection, collection)
    perm
  end

from_cycles(cycles, max = 0) click to toggle source

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 .

# File lib/permutation.rb, line 27
  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) click to toggle source

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.

# File lib/permutation.rb, line 16
  def self.from_value(indices)
    obj = new(indices.size)
    obj.instance_eval do
      self.rank = rank_indices(indices)
    end
    obj
  end

new(size, rank = 0) click to toggle source

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

# File lib/permutation.rb, line 7
  def initialize(size, rank = 0)
    @size, @rank = size, rank
    @last = factorial(size) - 1
  end

Public Instance Methods

*(other) click to toggle source

Alias for compose

-@() click to toggle source

Alias for invert

<=>(other) click to toggle source

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.

# File lib/permutation.rb, line 183
  def <=>(other)
    size <=> other.size.zero? || rank <=> other.rank
  end

==(other) click to toggle source

Alias for eql?

compose(other) click to toggle source

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>

# File lib/permutation.rb, line 236
  def compose(other)
    size == other.size or raise ArgumentError,
      "permutations of unequal sizes cannot be composed!"
    indices = self.value
    composed = other.value.map { |i| indices[i] }
    klon = clone
    klon.rank = rank_indices(composed)
    klon
  end

Also aliased as: *

cycles() click to toggle source

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]]

# File lib/permutation.rb, line 257
  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

each() click to toggle source

Iterates over all permutations of size Permutation#size starting with the first (rank == 0) ranked permutation and ending with the last (rank == Permutation#last) ranked permutation while yielding to a freshly created Permutation instance for every iteration step.

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

# File lib/permutation.rb, line 155
  def each # :yields: perm
    0.upto(last) do |r|
      klon = clone
      klon.rank = r
      yield klon
    end
  end

each!() click to toggle source

Does something similar to Permutation#each. It doesn’t create new instances (less overhead) for every iteration step, but yields to a modified self instead. This is useful if one only wants to call a method on the yielded value and work with the result of this call. It’s not a good idea to put the yielded values in a data structure because the will all reference the same (this!) instance. If you want to do this use Permutation#each.

# File lib/permutation.rb, line 170
  def each!
    old_rank = rank
    0.upto(last) do |r|
      self.rank = r
      yield self
    end
    self.rank = old_rank
  end

eql?(other) click to toggle source

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.

# File lib/permutation.rb, line 190
  def eql?(other)
    self.class == other.class && size == other.size && rank == other.rank
  end

Also aliased as: ==

even?() click to toggle source

Returns true if this permutation is even, false otherwise.

# File lib/permutation.rb, line 299
  def even?
    signum == 1
  end

hash() click to toggle source

Computes a unique hash value for this Permutation instance.

# File lib/permutation.rb, line 197
  def hash
    size.hash ^ rank.hash
  end

invert() click to toggle source

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

# File lib/permutation.rb, line 215
  def invert
    clone.invert!
  end

Also aliased as: -@

invert!() click to toggle source

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

# File lib/permutation.rb, line 203
  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

next() click to toggle source

Returns the next ranked Permutation instance. If this instance is the Permutation#last permutation it returns the first (rank == 0) permutation.

# File lib/permutation.rb, line 113
  def next
    clone.next!
  end

Also aliased as: succ

next!() click to toggle source

Switches this instance to the next ranked Permutation. If this was the Permutation#last permutation it wraps around the first (rank == 0) permutation.

# File lib/permutation.rb, line 102
  def next!
    @rank += 1
    @rank = 0 if @rank > last
    self
  end

Also aliased as: succ!

odd?() click to toggle source

Returns true if this permutation is odd, false otherwise.

# File lib/permutation.rb, line 304
  def odd?
    signum == -1
  end

pred() click to toggle source

Returns the previously ranked Permutation. If this was the first permutation it returns the last (rank == Permutation#last) permutation.

# File lib/permutation.rb, line 131
  def pred
    clone.pred!
  end

pred!() click to toggle source

Switches this instance to the previously ranked Permutation. If this was the first permutation it returns the last (rank == Permutation#last) permutation.

# File lib/permutation.rb, line 122
  def pred!
    @rank -= 1
    @rank = last if @rank < 0
    self
  end

project(data = @collection) click to toggle source

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"

# File lib/permutation.rb, line 91
  def project(data = @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

random() click to toggle source

Returns a random Permutation instance # of size Permutation#size.

# File lib/permutation.rb, line 144
  def random
    clone.random!
  end

random!() click to toggle source

Switches this Permutation instance to random permutation of size Permutation#size.

# File lib/permutation.rb, line 137
  def random!
    new_rank = rand(last + 1).to_i
    self.rank = new_rank
    self
  end

rank=(m) click to toggle source

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.

# File lib/permutation.rb, line 64
  def rank=(m)
    @rank = m % factorial(size) 
  end

sgn() click to toggle source

Alias for signum

signum() click to toggle source

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.

# File lib/permutation.rb, line 288
  def signum
    s = 1
    cycles.each do |c|
      c.size % 2 == 0 and s *= -1
    end
    s
  end

Also aliased as: sgn

succ() click to toggle source

Alias for next

succ!() click to toggle source

Alias for next!

value() click to toggle source

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]

# File lib/permutation.rb, line 76
  def value
    unrank_indices(@rank)
  end

Private Instance Methods

factorial(n) click to toggle source

(Not documented)

# File lib/permutation.rb, line 312
  def factorial(n)
    @@fcache.size.upto(n) { |i| @@fcache[i] =  i * @@fcache[i - 1] }
    @@fcache[n]
  end

rank_indices(p) click to toggle source

(Not documented)

# File lib/permutation.rb, line 317
  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

unrank_indices(m) click to toggle source

(Not documented)

# File lib/permutation.rb, line 328
  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

In Files

Parent

Methods

Included Modules

Files

Class Index

Permutation

Constants

Attributes

Public Class Methods

Public Instance Methods

Private Instance Methods