[Jprogramming] subsequent draws from arrays

[Alexander Mikhailov]

Hi,

a few times already I've had a task of modeling several subsequent random selections from an array. I thought this is a rather common problem, but couldn't find it in Puzzles of Phrases. I've decided to try it myself; then the forum will definitely give good suggestions.

So, suppose we have an array of integers of some shape 

shp =. 5 6 7

(the values are unimportant) and we want to randomly extract a few

num =. 11

items from different places in the array. We may generate 11 numbers from 0 to 5*6*7 (not including the last, 210th)

idxs =. ?. num $ */ shp

but then we'll need to make sure we don't have repetitions and add more numbers until all 11 are unique. Then the indices may be translated into coordinates in the array by

shp #: idxs

We can try to (re)invent a non-repeating algorithm. Note that if we at first draw, say, 5th item - and remove it from initial array - its place will be taken by 6th item, so if second time we again draw 5th item, it's going to be the 6th element in the original array. So, if we imagine a sequence of draws -

4 6 5 10

taken in the order from right to left (i.e., first we take - and remove - 10th item from original array, then 5th item of remaining array, then 6th item of remaining array, then 4th of remaining), the items in the original array actually take places

4 7 5 10

because when we took 6th item, all items after 5 got their positions decremented (and all after 10 decremented twice), so item on the 6th place was actually item from 7th place in the original array.

After each draw the length of array decrements, so if first draw selects from */ 5 6 7 possible choices, the second one selects from <: */ 5 6 7 choices, the third one - from <: <: */ 5 6 7 etc. To draw 11 times, we randomly choose numbers from shrinking sets:

   ]idx =. ?. (i. num) + num -~ */ shp
61 155 161 80 184 27 75 79 175 2 16

Now for each number we need to find how many numbers to the right of it are smaller or equal to this number. It can be found using prefixes and suffixes

   ]dlt =. (}:@(<@{:\)   (>@[ +/@:>: >@])"0 0   <\.@}.) idx
3 6 6 5 6 2 2 2 2 0

Now we're adding this index corrections ("deltas") to the idx array and obtain final unique indexes in the original array

   idx + dlt
64 161 167 85 190 29 77 81 177 2 16

Now, question to the forum. How this problem should be solved? What better solutions are there?

Thanks,

Alex