OK - I'm going to take a stab at this ...
How 'bout using an AVL tree?
In every node, the value that was previously generated is stored,
along with a running count for the total number of nodes to the left
(a count of values less than the value in the parent node).
A random number is generated, and the process begins:
for (max_lmt = MAX_VAL; max_lmt; max_lmt--)
{
new_number = RAND(seed) % max_lmt;
add_to_tree (new_number);
}
For each insertion made to the AVL tree,
move to the left if the new value is less than the value in the
current node, pushing a reference to the current node onto a stack,
and, if the current node value is less than the new value,
add the left_count (total number of children with values less than
the current tree node) to the current value, then add one more
(for the current node itself), then move to the right.
When a leaf node is encountered, pop from the stack,
compare the current value to the value on the stack.
If the current value is greater than the value popped,
then add one more to the current value, move to the right from
that node, repeating the process, until you pop a value
from the stack that is greater than the current value,
or the stack is empty (which would be moving to the right
from the top of the tree at that point).
You might be able to do this using recursion, but it could
get to be a bit hairy when you get to the point that the value
in the node on the stack is greater than the new value
- and insertion has to be made at the point that you left
after returning from a recursive call - unless you pass the
value of the parent node in the arg list - I dunno - I'm just
making this garbage up off the top of my pointy little head
- after taking a few hard slugs fwum tis boddel uh rummm
tha' I've gotte sitttn hear onnn th flore. <hic>
Once you get that, then add the node to the tree at that point,
and rebalance. Rebalancing will be interesting, as you will
have to adjust the left_count for each node as the shifts are made.
HTH.
wASP
======================
On 25 Jul 2005 08:34:05 -0700, "jason" <ia****@yahoo.com> wrote:
Hello everyone,
I am looking for an algorithm that would take an incremental value and
map that to a case-inspecific alphanumeric string. However,
I don't want the string to simply step through 0000, 0001 ... ZZZZ. I
would ideally like the value to appear to jump around randomly, but
still be traced back to an incrementing value. So, for example, while a
simple standard mapping might look like:
foo(1) => 0000
foo(2) => 0001
...
foo(1679616) => ZZZZ
I would prefer a psuedo-random mapping, which might look like:
foo(1) => AF23
foo(2) => 4PQT
...
foo(1679616) => 0FZ1
But still guaranteeing that all values are iterated through uniquely,
like in the simple mapping above. The only thing that is coming to mind
to use for this to generate a predictable, psuedo-random order of the
range of integers, and step through that order as the incrementing
value? That doesn't seem like the most efficient algorithm though.
Any guidance is greatly appreciated.
jason
- wASP