Building an algorithm to generate random # Array (practice with recursion)
Published: 2023-06-27 18:06:38

####Intro
I recently decided to test a proof of concept that included designing a board of n X n squares (example 10X10), where each row as well as each column is assigned a number from 0 to n, and also restricted to only using each number once for each row and column. ![Squares board concept](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ld82ah2mj9rmu2zmb008.png) My goal was to design a function creating an array of n elements, and built so that each element was assigned a unique number randomly.  This required me to solve the specific problem of how to randomly assign a unique number for an array of n length from (0 to n).  The solution requires a few things to be true:
1. every number from 0 to n must be generated.
2. no two numbers can be the same.
3. the numbers should be randomly assigned within the array.

###### RNG with comparison function for unique Assignment
My first solution was to assign each element in the array sequentially with a random number.  This required the function to make sure that every number was randomly generated and only appeared once in the output array.  The code includes randomly generating a number from 0 to n and pushing it to the output array for n elements.  ![random assign over array with comparisons](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sgc0oof9pjm310g63amq.png) The solution included a comparison function to be called each time a new random number was going to be assigned to the output array.  This comparison function would then check the new random number against all current numbers in the output array and regenerate the random number if the comparison was true.  This process does use a bit of recursion; however, this was more for flavor since a simple for loop could have worked just as well.

A second solution would be to do something similar to the above but to instead have each unique number accounted for and then to randomly place them within the array.  I believe the code would follow similar logic where you are assigning numbers in turn from 0 to n to different index positions randomly and comparing to never assign the same index twice.

######Recursive Approach using unique Pools:
A third solution I explored used recursion as the primary tool.  In this function, I defined two pools of numbers (0 to n), with one for index and one for value, picked one value randomly from each pool, which would assign a random number to a random index for the output array.  Then, in order to fill out the remaining indexes with the remaining numbers, I used recursion to call my function within itself, but modifying the arguments passed in order to reduce the pools number of values by one for each recursive call. ![recursive solution based on shrinking pools](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gjdapbpq1uuozh7veclb.png)  The function is includes initializing three arrays based on the desired lengths including an index array having n elements from 0 to n, an element array having n elements from 0 to n, and an output array having n elements that are empty.  The first two arrays serve as the pools, from which we randomly draw a number that tells us which value to put in which index of the output array. After, which the elements selected randomly from the pools are then removed as options, and the function is then called recursively passing in the current output array, and the reduced pool arrays.  This sequence of operations is performed until the output array has been fully filled and permits the unique assignment of each number 0 to n to a unique index of 0 to n.

The results of these two approaches showed how vary different solutions can be used to solve the same problem.  Furthermore, I decided to log the execution time of each approach, and I found the differences to be quite interesting.  I may possibly look into why the results turned out as such in another post. ![Execution Time Testing of solutions](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pkkla593fvgbpobsni38.png)