0

Trying to plan out a function and I wanted to get some input. I am trying to find an efficient way to:

  1. Double the frequency of numbers in an array

  2. Randomize the location of the values in the array.

For example: Lets say I have an array. [0,1,2,3]

  1. first I want to duplicate each number once in a new array. So now we would have something like this. [0,0,1,1,2,2,3,3].

  2. Lastly, I want to randomize these values so: [0,4,2,3,0,2,3,4]

Eventually, the algorithm I write will need to handle an initial array of 18 digits (so the final, randomized array will be of size 36)

My initial thoughts are to just have a simple while loop that:

  1. Randomly selects a spot in the new array
  2. Checks to see if it is full -If it is full, then it will select a new spot and check again.
  3. If it is not full, then it will place the value in the new array, and go to the next value.

I am leaving out some details, etc. but I want this algorithm to be fairly quick so that the user doesn't notice anything.

My concern is that when there is only one digit left to be placed, the algorithm will take forever to place it because there will be a 1/36 chance that it will select the empty space.

In general terms, how can I make a smarter and faster algorithm to accomplish what I want to do?

Many thanks!

trinaldi
  • 2,872
  • 2
  • 32
  • 37
user3765881
  • 5
  • 2
  • 2
    1) A concise way would be `var newArr = arr.concat(arr);`. 2) [How to randomize (shuffle) a JavaScript array?](http://stackoverflow.com/q/2450954/218196) – Felix Kling Dec 04 '14 at 16:01

2 Answers2

1

first I want to duplicate each number once in a new array. So now we would have something like this. [0,0,1,1,2,2,3,3].

That would be rather complicated to accomplish. Since the positions are not relevant anyway, just build [0,1,2,3,0,1,2,3] by

var newArray = arr.concat(arr);

Lastly, I want to randomize these values so: [0,4,2,3,0,2,3,4]

Just use one of the recognized shuffle algorithms - see How to randomize (shuffle) a JavaScript array?. There are rather simple ones that run in linear time and do not suffer from the problem you described, because they don't need to randomly try.

Community
  • 1
  • 1
Bergi
  • 630,263
  • 148
  • 957
  • 1,375
  • *"That would be rather complicated to accomplish"* Why? If every element is unique in the input array, then `var newArr = arr.reduce(function(narr, v) { narr.push(v, v); return narr;}, []);` is not too complicated. – Felix Kling Dec 04 '14 at 16:05
  • 1
    It is more complicated than concatenating the array with itself and the result is going to be the same. – Pedro Montoto García Dec 04 '14 at 16:09
0

Here is an alternative to the known methods with two arrays, I came up with. It gives relatively good randomization.

    var array1=[]
    var array=[0,1,2,3,0,1,2,3]
    a=array.length;
    b=a;
    c=b;
    function rand(){for (i=0;i<c;i++){
    n=Math.floor(Math.random()*b);
    array1[i]=array[n]; array.splice(n,1);b--;}
    for (i1=0;i1<c;i1++){array[i1]=array1[i1]}
HLNGR
  • 1