Efficient way to store an isomorphism?

Hi,

I was wondering if anyone would be able to help me with the following
problem: I need to find an efficient implementation of a function "m",
where "m" is some isomorphism between two sets A and B, both of which
are subsets of N.

The obvious way to do this is to store "m" as a 2D array, every row of
which contains an element from A and the corresponding element from B.
To find m(a) from some element in A, we need to search the table. Thus,
if "n" is the size of both sets, it takes O(n) space to store the array
and O(n) time to perform a lookup.

An alternative is to define a hash function h: A -> {0 .. n-1}. Then we
store the hash function along with a 1D array B' that contains the
elements of B. To find m(a), we calculate i = h(a), and then find
B'[i]. Now we can do lookups in O(1) time, but we still need O(n) space
to store the array (assuming that storing the hash function takes less
than O(n) space).

This is better, but perhaps it is possible to go one step further:
would it be possible to define a hash function h': A -> B, that would
"hash" an element of A directly onto the corresponding element of B?
Then we only need to store this hash function, and finding m(a)
corresponds to calculating h'(a). Then we can do lookups in O(1) time;
additionally, we should be able to store the hash function in less than
O(n) space.

Does such a function exist? If so, is there an algorithm to calculate
it? Is it possible to give bounds on the size of this function?

Thanks very much,

Edsko

.

Relevant Pages

  • Re: Efficient way to store an isomorphism?
    ... we should be able to store the hash function in less than ... because lookups are actually Oworst case. ... Google for "minimal perfect hashing". ...
    (comp.theory)
  • Re: Finding the nearest match without reusing results
    ... comparing an array with a value generates an array of Trues and ... Any diff with wrong State or with used Store is implicitly zeroed out. ... Each must be larger than the absolute value of the maximum Sales ... go.....it just needs to return the closest match. ...
    (microsoft.public.excel.programming)
  • Re: read keyboard input and storing in an array?
    ... > I'm trying to store user input in an array, ... You have the beginnings of that logic already since your prompt tells the ... 201st value since the array only has room for 200 values. ... This will force you to store the int values as Integer ('Integer' ...
    (comp.lang.java.help)
  • Re: Challenge: reading ascii data
    ... to store all the data before producing any output. ... would be bad practice in terms of memory consumption to use a standard ... So I use hashes to create a two-level "sparse array", ... Well the original problem definition was: ...
    (comp.lang.fortran)
  • Re: attempting an actual game...
    ... >>> and inflexible by the absurd decision to use a bit array for square ... as then one has 8 bits in which to store a color and a few flags ... Using a 2D int (or, ... > Change direction and you may eventually complete a game. ...
    (comp.games.development.programming.misc)