seeking help with an algorithm

[jason]

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

 

[Bruno Jouhier [MVP]]

Just add a random positive number at every step, and encode in base 36 (10 +
26). Something like:

i += Math.Abs(Random.NextInt() % MaxIncrement)
str = Encode36(i);

The only problem is that you have to be clever in the way you choose
MaxIncrement.
If MaxIncrement is too low, the sequence will not look very random.
If MaxIncrement is too high, i might overflow.
So, if you want to generate N numbers, you have to choose MaxIncrement as
Int32.MaxValue / N

Bruno.

 

[Guest]

Just add a random positive number at every step, and encode in base 36 (10 +
26). Something like:

i += Math.Abs(Random.NextInt() % MaxIncrement)
str = Encode36(i);

I don't think this will satisfy the uniqueness constraint the original
poster wanted though.

 

[jason]

but in that solution, won't the algorithm effectively "skip" all the
string values between i and i + random int?

for example the first pass might generate i == 35, or string 000Z
but the next pass might generate i == 70, or string 001Z

i'm looking for somethign that will actually generate all possible
combinations of 0000 - ZZZZ, just in a random order. i don't want to
lose any to the incrementation approach.

thanks for the comment though,

jason

 

[Guest]

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:

possibly nonworkable kluge warning.

Treat your index number as a 21bit string. Shuffle the bits in a fixed
pattern. Then convert the shuffled bitstring into a base36 number with each
digit ranging across 0-9A-Z.

You might have a problem with the leading bit being zero more often than 1,
which is why I'm not sure if this idea would work or not.

Anyway food for thought.

 

[Jeremy Williams]

Basically, your requirements are:

1) Use a known range of values (0000 - ZZZZ)
2) Use these values once and only once
3) Use these values in a random order

You will probably need to build them ahead of time, say in an array, and
"shuffle" the array to obtain randomness. Then you can just grab the next
item off the array.

 

[Fred Mellender]

If you can use generics, you can use my library for generating combinations
(etc), at
http://www.frontiernet.net/~fredm/dps/Contents.htm But this does not
generate in a random
order. After you get the combinations, you can shuffle that list:

public static List<T> shuffledList(List<T> listToShuffle)

{

/*

* Make a new list of elements picked from aList

* in a random order.

*/

List<int> ints = new List<int>(listToShuffle.Count);

for (int i = 0; i < listToShuffle.Count; i++)

ints.Add(i);

List<int> randIndx = new List<int>(listToShuffle.Count);

for (int k = 0; k < listToShuffle.Count; k++)

{

int randK = Common.rand.Next(ints.Count);

randIndx.Add(ints[randK]);

ints.RemoveAt(randK);

}

List<T> randList = new List<T>(listToShuffle.Capacity);

foreach (int r in randIndx)

randList.Add(listToShuffle[r]);

return randList;

}



So far as I know, there is no way to generate the combinations in a random
order, efficiently.

 

[wASP]

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
======================

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

 

[jason]

this is a one-comment thank-you to everyone who has contributed here.
it's great to see everyone's approaches. i will investigate each one of
these as a possible solution, and i'm sure one will be found.

thanks again,

jason