Object

- Enumerable
- Comparable

- VERSION
Permutation version

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

<=>(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

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

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

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

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

Disabled; run with --debug to generate this.

Generated with the Darkfish Rdoc Generator 1.1.6.