[Edu-sig] Reversing dictionaries, closures, permutations etc.

[Kirby Urner]

> Be aware also that the reverse (or inverse) may also be degenerate, unless
> you have a strict 1:1 correspondence between keys and values.  There are
> cases of use of course, and bear in mind that the inverse of the inverse
> of dictionary is *guaranteed* to be 1:1.  I use something like this when I
> need to have such a guarantee and want a reversible mapping.
> 
> Cheers,
> Terry

Yes, good point.  It's not just the immutability of the values that's
required for inverting, but their uniqueness.  Without that, the inverse
dictionary drops pairs (which in some applications might be OK):

 >>> adict = {1:2, -1:2}
 >>> invdict(adict)
 {2: -1}

This is akin to functions like def f(x): return x**2, in that f(-2) and f(2)
both return 4, yet given def g(x): return math.sqrt(x), g(4) returns 2 only.


So g is not truly f's inverse (f has no true inverse, because it's
many-to-one).

What I'm thinking about in this thread is a way to define functions and
inverse functions in a namespace, then pass them to a class P so that
operator overloading will allow:

   (1) using p(x) to get back y, where x:y is in a function's dictionary
   (2) composition using the * operator (e.g. p3 = p1 * p2)
   (3) using ~p after defining p, where ~p uses an inverse function

A special case application of this framework would be permutations, which
simply maps the elements of a set to a reordering of the same set.  

Such functions are guaranteed to be bidirectional, so the degenerate inverse
won't be a problem.

If invf is the inverse of f, and invg is the inverse of g, what's the
inverse of f*g (i.e. f(g(x)) for any x)?  It needs to be invg * invf yes?
That way, invg(invf(f(g(x)) = x for all x.  This presumes associativity, but
not commutativity (which is the case for permutations in general).

Here's some source code:

class P:
    """
    Class wants both function and inverse function for construction.
    User builds these before instantiating
    """

    def __init__(self, f, invf):
        self.f    = f
	  self.invf = invf

    def __mul__(self, other):   # composition
	  f =     self._compose(self.f, other.f)
	  invf =  self._compose(other.invf, self.invf)
	  return P(f, invf)

    def __call__(self, x):
        return self.f(x)
		
    def __invert__(self):
        return P(self.invf, self.f)

    def _compose(self, f, g):
	  return lambda x:  f(g(x))

def invdict(adict):
    """
    Invert a dictionary
    """
    return dict([(val, key) for key, val in adict.items()])        
             
def makefunc(adict):
    """
    Build a function, given a dictionary
    """
    def anon(y):
        return adict[y]
    return lambda y: anon(y)
            
def randomdict(alist):
    """
    Generate a random permutation mapping alist to itself
    Returns a dictionary
    """
    from random import shuffle
    alist2 = alist[:]
    shuffle(alist2)
    return dict(zip(alist,alist2))
 
def test():
    d = randomdict(range(6))
    f1, invf1 = makefunc(d), makefunc( invdict(d) )
    p1 = P(f1, invf1)

    print 'p1:       ' , [(i, p1(i)) for i in range(6)]
    print '~pi:      ' , [(i, (~p1)(i)) for i in range(6)]
    print 'p1 * ~p1: ' , [(i, (p1 * ~p1)(i)) for i in range(6)]


Usage:

 >>> from mathstuff.perm import *

 >>> test()
 p1:        [(0, 3), (1, 1), (2, 0), (3, 2), (4, 4), (5, 5)]
 ~pi:       [(0, 2), (1, 1), (2, 3), (3, 0), (4, 4), (5, 5)]
 p1 * ~p1:  [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)]

 >>> test()
 p1:        [(0, 2), (1, 0), (2, 3), (3, 4), (4, 5), (5, 1)]
 ~pi:       [(0, 1), (1, 5), (2, 0), (3, 2), (4, 3), (5, 4)]
 p1 * ~p1:  [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)]

 >>> test()
 p1:        [(0, 5), (1, 3), (2, 2), (3, 4), (4, 0), (5, 1)]
 ~pi:       [(0, 4), (1, 5), (2, 2), (3, 1), (4, 3), (5, 0)]
 p1 * ~p1:  [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)]

Kirby