Two mappings inverse to each other: f, g = biject()

J

Jonathan Fine

Hello

As part of the MathTran project I found myself
wanting to maintain a bijection between long
names and short names.
http://www.open.ac.uk/mathtran

In other words, I wanted to have two dictionaries
f and g such that
f[a] == b
g == a
are equivalent statements.

A google search for biject.py and bijection.py
produced no hits, so I suspect that this may not
have been done before.

I've written a partial implementation of this,
and would appreciate comments.

http://texd.cvs.sourceforge.net/texd/tex/util.py?revision=1.1&view=markup
http://texd.cvs.sourceforge.net/texd/test_tex/test_util.py?revision=1.1&view=markup

Here's the code from test_util.py, that shows how it
works. The weakref stuff is so that there isn't a
circular reference f to g to f.
===
from tex.util import biject

f, g = biject()
assert f.inverse is g
assert g.inverse is f

f[1] = 2
assert f[1] == 2
assert g[2] == 1
assert f.has_value(2)

import weakref

wr_g = weakref.ref(g)
del g
assert wr_g() == None
assert f.inverse == None
===

best regards


Jonathan
 
N

Nick Vatamaniuc

Hello

As part of the MathTran project I found myself
wanting to maintain a bijection between long
names and short names.
http://www.open.ac.uk/mathtran

In other words, I wanted to have two dictionaries
f and g such that
f[a] == b
g == a
are equivalent statements.

A google search for biject.py and bijection.py
produced no hits, so I suspect that this may not
have been done before.

I've written a partial implementation of this,
and would appreciate comments.

http://texd.cvs.sourceforge.net/tex...rge.net/texd/test_tex/test_util.py?revision=1...

Here's the code from test_util.py, that shows how it
works. The weakref stuff is so that there isn't a
circular reference f to g to f.
===
from tex.util import biject

f, g = biject()
assert f.inverse is g
assert g.inverse is f

f[1] = 2
assert f[1] == 2
assert g[2] == 1
assert f.has_value(2)

import weakref

wr_g = weakref.ref(g)
del g
assert wr_g() == None
assert f.inverse == None
===

best regards

Jonathan


Jonathan,

If you need to get a short name, given a long name or vice-verse _and_
the set of short names and long names is distinct (it would be
confusing if it wasn't!) then you can just have one dictionary, no
need to complicate things too much:
f[a]=b
f=a
You won't know which is a short and which is a long based just on
this, so you need to keep track of it. But it will give you the
mapping.
Here is an example:
------------------------------------ ....: f[S]=L
....: f[L]=S{'a': 'alpha',
'alpha': 'a',
'b': 'beta',
'beta': 'b',
'd': 'delta',
'delta': 'd'}
'b'
----------------------------------

Hope this helps,
And remember : "Simple Is Better Than Complex" [http://www.python.org/
doc/Humor.html#zen]

Nick Vatamaniuc
 
J

Jonathan Fine

Nick said:
If you need to get a short name, given a long name or vice-verse _and_
the set of short names and long names is distinct (it would be
confusing if it wasn't!) then you can just have one dictionary, no
need to complicate things too much:
f[a]=b
f=a
You won't know which is a short and which is a long based just on
this, so you need to keep track of it. But it will give you the
mapping.


Thank you for this suggestion, Nick. It's not
something I thought of. And I'm sure that in some
cases it might be just the right thing. It would
hold something like 'other-name' values. (Every
cat should have at least two names ...)

But for my application, I think it complicates the
code that uses the bijection.

For example, I want to say:
# Write the font dictionary to a file
for key in font_dict:
# write the font

# Does value already exist in the font dictionary?
# If not, add it to the font dictionary.
key = font_dict.inverse.get(value)
if key is None:
key = len(font_dict)
font_dict[key] = value

Following your suggestion, ingenious though it is,
would make the above code much more complicated and
error prone.

Perhaps it helps to think of
f, g = biject()
as establishing a database, that has a consistency
condition, and which has two views.

There we are: biject() gives two views on a
mapping (of a particular type). Thank you for
you suggestion - it has clarified my thinking.
 
J

Jonathan Fine

There are few (good too) implementations around, but they are called
bidict or bidirectional dicts. Sometimes I use this implementation,
with few changes:
http://www.radlogic.com.au/releases/two_way_dict.py

Thank you for this. You are quite right, a dictionary
is a particular type of mapping. A mapping with an
inverse is called (at least by me) a bijection. Therefore,
as you say, bidict or something similar is correct for
a bijection that is based on dictionaries.

I had a look at the code in radlogic. There, the
design philosophy is to add 'inverse operations' to
a dictionary. Thus, it adds a method reversed_items.

In my code, I used a different philosophy, which
comes down to this. If a mapping is by design a
bijection, then it should have an inverse method
that gives the inverse mapping. This preserves the
symmetry between a mapping and its inverse. (The
inverse has an inverse, which is the original mapping.)

Therefore, my semantics comes down to
f, g = bidict() # Use the better name.
assert f = g.inverse
assert g = f.inverse
and also
f[a] = b if and only if g = a

By the way, it turns out that a bidict is not what
my application needs. But I find it an interesting
problem, and time spent on it I do not consider
wasted.

Best regards

Jonathan
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top