class MoreMath::Permutation

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

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

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

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

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

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

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

def even?
  signum == 1
end

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

def hash
  size.hash ^ rank.hash
end

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

def invert
  clone.invert!
end

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

def odd?
  signum == -1
end

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

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

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

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

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

def value
  unrank_indices(@rank)
end