By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
424,850 Members | 967 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 424,850 IT Pros & Developers. It's quick & easy.

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

P: n/a
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[b] == 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....1&view=markup
http://texd.cvs.sourceforge.net/texd....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

Feb 6 '07 #1
Share this Question
Share on Google+
4 Replies


P: n/a
On Feb 6, 5:22 am, Jonathan Fine <j...@pytex.orgwrote:
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[b] == 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....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[b]=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:
------------------------------------
>>S=('a','b','d')
L=('alpha,'beta','delta')
f={}
for i in range(3):
....: f[S[i]]=L[i]
....: f[L[i]]=S[i]
>>f
{'a': 'alpha',
'alpha': 'a',
'b': 'beta',
'beta': 'b',
'd': 'delta',
'delta': 'd'}
>>f['b']
'beta'
>>f['beta']
'b'
----------------------------------

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

Nick Vatamaniuc

Feb 6 '07 #2

P: n/a
Nick Vatamaniuc wrote:
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[b]=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.

--
Jonathan
Feb 6 '07 #3

P: n/a
Jonathan Fine:
A google search for biject.py and bijection.py
produced no hits, so I suspect that this may not
have been done before.
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

Bye,
bearophile

Feb 6 '07 #4

P: n/a
be************@lycos.com wrote:
>>A google search for biject.py and bijection.py
produced no hits, so I suspect that this may not
have been done before.


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[b] = 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

Feb 7 '07 #5

This discussion thread is closed

Replies have been disabled for this discussion.