CODEWITHSUNDEEP
randommultidimensional-array
Ha-eun Chung
Ha-eun Chung

Reputation: 455

pick random element from 2d array equally likely

I have two dimension array that each 1 layer of elements has different size of array. For example, its something like 

 first element  1  9
 second element 7
 third element  10 3  2
 fourth element 6  92 14 73

How to pick an element from this 2d array equally likely? The one obvious way to pick random element from 2d is generate random numbers and pick like row of array[first random] and generate second based on size of that element, but it doesn't pick an element equally likely (e.g second element contains 1 element which will have more probabilities than others 25% chance where other elements have less than 25%). This approach will work if all elements in first layer have same size of array but not this case. I also consider performance (array is quite big enough)

Upvotes: 0

Views: 1299

Answers (4)

Jeff Swensen
Jeff Swensen

Reputation: 3573

I would generate a random number from 1 to your entire element count (10 in your example). Then loop through the first level of your array, keeping track of how many elements you've encountered so far.

i.e. in psuedo:

randomNumber = rand(1,10)
soFar = 0
for(i=0, i<topLevel.size, i++)
  if ((soFar + topLevel[i].size) > randomNumber)
    return topLevel[i][randomNumber - soFar]
  else
    soFar += topLevel[i].size

Upvotes: 1

jwd
jwd

Reputation: 11124

Why not just normalize it into a 1D array?

Visually, if your 2D array looks like this:

0:  X X
1:  X
2:  X X X
3:  X X X X

Think of it like this:

0: (X X) (X) (X X X) (X X X X)

Parentheses just added for clarity, to show that each row of the original is being concatenated into one long row.

Now you just have to get a single random number from 0 to N-1, where N is the total number of 'X's in the diagram.

Of course, in order to actually access the chosen random element, you will have to skip through the 2D array appropriately (see Jeff Swensen's answer).

Upvotes: 3

orlp
orlp

Reputation: 117761

Generate a random number from 0 to (exclusive) (#layer1+#layer2+#layer3+#layer4), where the # operator means "number of elements". Now if the random number is between 0 and #layer1 return layer1[randomnumber]. Etcetera.

So basicly, treat the array as one long one-dimension array.

Upvotes: 0

Rob P.
Rob P.

Reputation: 15071

Treat the collection as a long 1-dimensional array. Generate a random number between 0 and the length -1 of that array.

So, in your example, you have 10 total items (0-9 assuming 0-based indexing). Now each item has an equal chance of being selected.

You'll either have to calculate the total items or maintain it as you add/subtract items.

Upvotes: 0

Related Questions