Generating non-colliding random numbers using a binary tree with PID.

Generating non-colliding random numbers using a binary tree with PID.

Image source : https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1206/lectures/trees/img/binary-palm-tree.png

Random numbers(whether true or pseudo) have wide applications for various purposes including security, monetary transactions, machine learning, gaming, statistics, cryptography, simulation, literature, music, and art.

Various tools, machines, and algorithms exist for generating non-colliding random numbers including the popular Fischer / Knuth yates algorithm. Nowadays computers are not efficient for generating random numbers since they run on logic, and the input always depends on the output.

Besides the popular Fischer / Knuth yates algorithm, in this blog, I’ll show you how you can generate non-colliding pseudo-random numbers using a binary tree with PID(Process IDentifier) without any APIs.

Random numbers

A sequence of any numbers that cannot be reasonably predicted better than by random chance is generated.

This means that the particular outcome sequence will contain some patterns detectable in hindsight but unpredictable to foresight.

This blog doesn’t focus on true random number generators that generate random numbers, wherein each generation is a function of the current value of a physical environment’s attribute that is constantly changing in a manner that is practically impossible to model, it rather provides another way of generating non-colliding random numbers(psuedo) using a binary tree with PID similar to the popular Fischer / Knuth yates algorithm.

Non-colliding

To ensure no hashing collision or clash is considered while generating the desired random number, a binary tree is considered with PID is considered.

Example : Given a dataset of 1, 2, 3, 4, 5, 6, 7, 8, 9 ,10.

[1.] To ensure that any randomly picked number is not repeated twice, the hash table might be considered.

HashSet<Integer> storage = new HashSet<>();

public void generateRandomValue(){

int currentVal = new SecureRandom(0).next(10);

if(storage.contains(currentVal)){

currentVal = new SecureRandom(0).next(10);// Re-generate another random number

}

[2.] The above(just like any other programming language implementation) will work but with a high possibility of having hashing collisions. For large datasets (trillions), Hashing to recheck if the newly generated number hasn’t been used is not recommended.

PID

Process ID or PID is known as the process identifier used by most operating system kernels—such as those of Unix, macOS, and Windows—to uniquely identify an active process.

End goal

Without using any programming language APIs, and by using a binary tree with a PID, for any given number or dataset, no two values are generated twice.

Our approach

Starting from the head

[0.] Given a set of numbers 1…n

Example : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11

[1.] Embark on a random cycle (c)

By default, c = 0, and a cycle is completed when the root, left, and right nodes has been visited.

[2.] Start with the root node

Root node equal the mid index : (n / 2)

When c = 0, root_node = n / 2

[3.] Proceed with either right or left node

Left node : c

Right node : (n – 1 ) – c

[4.] Cycle completed (i.e root, left, and right already visited) node has been visited

or in last cycle (i.e (c * 3) == (n – 1) ?

Increase the next cycle(c) by one(1),
Decrease the given index(n) by one,
Go back to step [1] or check if all nodes are completely visited (i.e n / 2) + 1 == Root(n-1)

Walk-through

Example : x = [1, 2, …, 9, 10]

[1.] Embark on a random cycle (c)

First cycle(c) = 0

Root node = n / 2 (where n is the total number of datas)

10 / 2 = 5

X[5] = 6

Left node = c ← 0

X[0] ←1

Right node = (n – c) (When c = 0, assume 1, first traversal)

(10 – 1) ←x[9] ←10

Cycle(0) is completed (i.e root, left, and right already visited) node has been visited

generated_random_numbers ⇐ [6, 1, 10] (root, left, right)

[1, 10, 6] (left, right, root)

[10, 1, 6] (right, left, root)

[2.] Check if it has reached last cycle ⇐ (c * 3) == (n – 1) or (n / 2) + 1 == (n – 1) ?

(0 * 3) != (10 – 1)

(10 / 2) + 1 != (10 – 1)

[3.] Increase the next cycle(c) by one(1), c ←1

Decrease the given index(n) by one, n ←9

Second cycle(c) = 1

Root node = n / 2 (where n is the total number of datas)

9 / 2 = 4

X[4] = 5

Left node = c ← 1

X[1] ←2

Right node = (n – c )

(9 – 1) ←x[8] ←9

Cycle(1) is completed (i.e root, left, and right already visited) node has been visited

generated_random_numbers ⇐ [6, 1, 10, 5, 2, 9] (root, left, right, root, left, right)

[1, 10, 6, 2, 5, 9] (left, right, root, left, root, right)

[10, 1, 6, 9, 2, 5] (right, left, root, right, left, root)

[2.] Check if it has reached last cycle ⇐ (c * 3) == (n – 1) or (n / 2) + 1 == (n – 1) ?

(1 * 3) != (9 – 1)

(9 / 2) + 1 != (9 – 1)

[3.] Increase the next cycle(c) by one(1), c ←2

Decrease the given index(n) by one, n ←8

Third cycle(c) = 2

Root node = 8 / 2 (where n is the total number of datas)