johnl@ima.UUCP (Compilers mailing list) (09/05/86)
I would like to know if anyone has heard of the following algorithm, or knows how to write it, or has any ideas about how it could be written. Say you have N numbers, {X}, which you know ahead of time, and you want to assign them the integers {1-N} in any order, but in a unique fashion. Numbers not in {X} can be assigned anything, although it would be nice if they were assigned to, say 0, or N+1. This is nice for parse tables, or for case statements where the {X} cover a large spread and the compiler uses an if-else tree. What I want is a program which writes the above program. The subroutine: alg(Y) for( i = {1-N} ) if( Y = X[i] ) return i is of order N operations, probably 3 or 4 N. Better is a binary tree: alg(Y) if( Y = X[N/2] ) return N/2 else if( Y < X[N/2] ) if( Y = X[N/4] ) return N/4 else if( Y < X[N/4] ) ... else if( Y > X[N/2] ) if( Y = X[3N/4] ) return 3N/4 ... which is of order 2logN operations, but longer. Also, there is the lookup table of size max{X}. Yuk. None of these are optimal. Now we get to the meat of the problem. I bet that there is an algorithm which will find a set of binary operations, such as binary and, or, not, xor, etc, which, when handed a Y, will return {1-N}. This would be a black box with about logN operations, and would be optimal for both speed and space. For example: X = { 0, 3, 5 }. then alg(Y) return X & 3 will map ( 0 -> 0 ), ( 3 -> 3 ), ( 5 -> 1 ). 2 was skipped, but oh well. Anyway, any ideas? Brian Sutin Department of Astrophysical Sciences/Princeton University { princeton, ... }!astrovax!sutin -- Send compilers mail to ima!compilers or, in a pinch to Levine@YALE.EDU Plausible paths are { ihnp4 | decvax | cbosgd | harvard | yale | bbncca}!ima Please send responses to the originator of the message -- I cannot forward mail accidentally sent back to compilers. Meta-mail to ima!compilers-request