Order Complexity for Ruby Combinatoric Functions

Question

In one of my algorithms I use Ruby's combination and permutation methods. I have to discuss this algorithms complexity. Where could I find information about their complexity/implementation?

I've tried implementing a simple 'hand made' function but the Ruby ones seem to run in near constant time!

Any information about where to look would be much appreciated.

Answer 1

Implementation can be shown on the same pages you linked. Hover your mouse over the name of the combination/permutation methods, and select click to toggle source.

You can view the latest and different versions of source here at the main repo: http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/

You can read the revision history of array.c to see perhaps why/when any changes were made to the combination/permutation methods. http://svn.ruby-lang.org/cgi-bin/viewvc.cgi/trunk/array.c?view=log. This may give you some indication into complexity and design choices made by the developers.

You may even be able to ask certain contributors to the source for reasons as to why they made XYZ change to the method, they may/may not help.

Answer 2

There is nothing in the Ruby Language Specification that requires implementors to guarantee a certain algorithmic complexity, and there is most certainly nothing that forces a particular implementation.

Every Ruby Execution Engine has their own implementation, and they may or may not have the same algorithmic complexity.

For example, here is Rubinius's implementation of Array#combination, located in kernel/common/array.rb#L360-394:

def combination(num)
  num = Rubinius::Type.coerce_to num, Fixnum, :to_int
  return to_enum(:combination, num) unless block_given?

  if num == 0
    yield []
  elsif num == 1
    each do |i|
      yield [i]
    end
  elsif num == size
    yield self.dup
  elsif num >= 0 && num < size
    stack = Rubinius::Tuple.pattern num + 1, 0
    chosen = Rubinius::Tuple.new num
    lev = 0
    done = false
    stack[0] = -1
    until done
      chosen[lev] = self.at(stack[lev+1])
      while lev < num - 1
        lev += 1
        chosen[lev] = self.at(stack[lev+1] = stack[lev] + 1)
      end
      yield chosen.to_a
      lev += 1
      begin
        done = lev == 0
        stack[lev] += 1
        lev -= 1
      end while stack[lev+1] + num == size + lev + 1
    end
  end
  self
end

And Array#permutation, located in kernel/common/array.rb#L935-969:

def permutation(num=undefined, &block)
  return to_enum(:permutation, num) unless block_given?

  if undefined.equal? num
    num = @total
  else
    num = Rubinius::Type.coerce_to num, Fixnum, :to_int
  end

  if num < 0 || @total < num
    # no permutations, yield nothing
  elsif num == 0
    # exactly one permutation: the zero-length array
    yield []
  elsif num == 1
    # this is a special, easy case
    each { |val| yield [val] }
  else
    # this is the general case
    perm = Array.new(num)
    used = Array.new(@total, false)

    if block
      # offensive (both definitions) copy.
      offensive = dup
      Rubinius.privately do
        offensive.__permute__(num, perm, 0, used, &block)
      end
    else
      __permute__(num, perm, 0, used, &block)
    end
  end

  self
end

As you can see, it delegates to a private helper method named Array#__permute__, defined in kernel/common/array.rb#L971-994:

def __permute__(num, perm, index, used, &block)
  # Recursively compute permutations of r elements of the set [0..n-1].
  # When we have a complete permutation of array indexes, copy the values
  # at those indexes into a new array and yield that array.
  #
  # num: the number of elements in each permutation
  # perm: the array (of size num) that we're filling in
  # index: what index we're filling in now
  # used: an array of booleans: whether a given index is already used
  #
  # Note: not as efficient as could be for big num.
  @total.times do |i|
    unless used[i]
      perm[index] = i
      if index < num-1
        used[i] = true
        __permute__(num, perm, index+1, used, &block)
        used[i] = false
      else
        yield values_at(*perm)
      end
    end
  end
end