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
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
