Pick random element from 2D array

[SteveChandler]

I have a 2D array of integers. I want to randomly select an element from the array. That's easy - just generate 2 random numbers and index the array.

Here is the twist. I want elements to be more likely to be chosen the higher their value is relative to the rest of the elements. This is for a memory game.

If all elements contain the same value then the probability of any one being chosen is the same as any other. If one element has a value greater than all others then it is the most likely to be chosen. If an element has a value lower than all others then it is least likely to be chosen. Finally if an element contains a value of zero then it will never be chosen.

The only way I can think of doing this is by using a 1D array of clusters of x and y to be used for indexing the 2D array. I would iterate through the 2D array. For each element I would read the value and create that many x,y clusters set to the current index and insert them into the 1D array of indexes. Now I simply generate a random number and index the 1D array, then index the 2D array. I would probably have to "shuffle" the 1D array of indexes though, wouldn't I?

It seems a little Rube Goldberg and I am hoping someone can come up with a simpler method.

[johnsold]

Steve,

Let me see if I understand your problem correctly.  You have a 2D array Y[i,j] of integers and some values may occur at multiple places in the array.  You want to select values randomly but with the probability that the element at [i,j] is chosen is proportional to the value of Y[i,j]. The special case of Y[i,j] = 0 results in zero probability that that element will be chosen.

Questions: Can a given element be chosen more than one time or is it excluded after being chosen once?  How large will the array be?  How fast do you have to do the selection?  Do you need to keep track of the indexes or the values selected (after the selection)?  Will all eligible elements be chosen? Is the weighting of the probabilities linear with value of Y[i,j] or will some non-linear mapping be applied?

Lynn

[altenbach]

Reshape the corresponding probability array into a 1D array and then threshold into a normalized integral of it using a 0..1 random number. You can easily calculate the 2D index from the resulting index and the original 2D array dimensions.  

See this example for details.

[johnsold]

I was thinking along the same lines as Christian's suggestion.  I had not yet reached the point where I could articulate it clearly as he has done.

Lynn

[SteveChandler]

---

@johnsold wrote:

Steve,

Let me see if I understand your problem correctly.  You have a 2D array Y[i,j] of integers and some values may occur at multiple places in the array.  You want to select values randomly but with the probability that the element at [i,j] is chosen is proportional to the value of Y[i,j]. The special case of Y[i,j] = 0 results in zero probability that that element will be chosen.

Questions: Can a given element be chosen more than one time or is it excluded after being chosen once? more than once  How large will the array be? very small, probably never larger than 25x25  How fast do you have to do the selection? within 500mS would be fine   Do you need to keep track of the indexes or the values selected (after the selection)? no Will all eligible elements be chosen? yes Is the weighting of the probabilities linear with value of Y[i,j] or will some non-linear mapping be applied? linear

Lynn

---

First paragraph, yes you understand correctly. Answers to questions in the second paragraph are in red although the link in Christian's reply does answer the question.

[altenbach · Accepted solution]

Here's a very rought draft. Modify as needed.

(probably needs a few tweaks)

 

[SteveChandler]

Awesome! Thank you very much. This works perfectly.

[PiDi]

Hello All

Just for reference, as I've noticed that Prob&Stat pallete is often overlooked ;): you can use random generator with desired distribution (for example - triangle). This might not exactly fit into Steves probem, but nonetheless it is useful function.