Transformation Combinatorics

04 Apr 2014

Transformations, also known as endofunctions, are superset of permutations where repeated elements in the codomain are allowed. Composing transformations can be done with the same algorithm as permutations.

def trans_mult(transa, transb)
  trans_ret =
  0.upto(transa.length-1) do |index|
  return trans_ret

My particiular interest in transformations is their application in sofware testing, but they are a ubiquitous concept in mathematics and sofware engineering.

As we play with transformations it will be nice to have the following enumerator that generates natural numbers starting at zero.

counting_numbers = do |yielder|
  (0..1.0/0).each do |number| 
  	yielder.yield number

Now if we want to print all transformations of size k we can use an enumerator.

	puts t.inspect

A first question we should ask ourselves, “Since transformations are a superset of permutations, do they have any analogues?”

The answer is a resounding yes!

As we explore transformations and related mathematical structures many will be crossreferenced with their OEIS sequence. I have a few dozen queued up so this should take a few posts :)