Iterating through Permutations

In a previous post I described how to use inversion tables to iterate through all the permutations of a set. Here’s a Ruby code implementation. First how to use it:

a = %w( a b c )
p = Permutation.new(a.size)
(0...a.size.factorial).each do |i|
  puts p.permute(a).join
  p.next!
end

The output is:

abc
acb
bac
bca
cab
cba

The constructor takes the size of the permutation as an argument. It starts with the identity permutation. An optional second argument specifies a later permutation in the sequence.

It’s also possible to specify a permutation by passing the constructor an array. For an n-permutation, the array must contain the integers from 0 to n-1 in some order.

The next method will return nil when it gets to the end of the sequence.

The compose method creates a new permutation from the argument permutation and the object permutation.

Here’s the source:

class Integer
  def factorial
    (1..self).inject(1) { |n,i| n*i }
  end
end

class Permutation

  def initialize(arg, n=0)
    begin
      @size = arg.length
      @it = Permutation.to_inversion_table(arg)
      @n = @it_n = Permutation.inversion_table_number(@it)
    rescue NoMethodError
      @size = arg
      @n = n
    end
  end

  def permute(a)
    b = Array.new
    (0..._permutation_array.size).each do |i|
      b[_permutation_array[i]] = a[i]
    end
    r = b.size...a.size
    b[r] = a[r]
    b
  end

  def permute!(a)
    b = permute(a)
    (0...a.size).each { |i| a[i] = b[i] }
  end

  def next
    self.deep_dup.next!
  end

  def next!
    _inversion_table
    next_inversion_table
  end

  def self.to_permutation_array(it)
    pa = Array.new
    (it.size-1).downto(0) do |i|
      pa.insert(it[i],i)
    end
    pa
  end

  def self.inversion_table_number(it)
    (1..it.size).inject(0) do |m,o|
      m += (it.size-o)*(it.size-o).factorial
    end
  end

  def self.to_inversion_table(pa)
    t = pa.dup
    it = Array.new
    (0...pa.size).each do |i|
      it[i] = t.index(i)
      raise "not a permutation array: #{pa.inspect}" if it[i].nil?
      t.delete(i)
    end
    it
  end

  def permutation_array
    _permutation_array.dup
  end

  def inversion_table
    _inversion_table.dup
  end

  def compose(p)
    a = p._permutation_array
    b = _permutation_array
    raise "permutation size mismatch" if a.size != b.size
    c = Array.new
    (0...a.size).each { |i| c[i] = b[a[i]] }
    Permutation.new(c)
  end

  def compose!(p)
    @pa = compose(p).permutation_array
    @it = Permutation.to_inversion_table(@pa)
    @it_n = Permutation.inversion_table_number(@it)
  end

protected

  def deep_dup
    p = self.dup
    p.dup_attributes
    p
  end

  def dup_attributes
    @it = @it.dup unless @it.nil?
    @pa = @pa.dup unless @pa.nil?
  end

  def _inversion_table
    return @it if !@it.nil? and @it_n == @n
    if @it.nil?
      @it = Array.new(@size,0)
      @it_n = 0
    end
    while (@it_n < @n )
      next_inversion_table
    end
    @it
  end

  def next_inversion_table
    @pa = nil
    @it_n += 1
    (@size-1).downto(0) do |i|
      @it[i] += 1
      return if @it[i] <= @size-(i+1)
      @it[i] = 0
    end
    @it_n = 0
    @it = nil
  end

  def _permutation_array
    return @pa unless @pa.nil?
    @pa = Permutation.to_permutation_array(_inversion_table)
  end
end