 # What's the best to chose n number from an array without replacement?

Just like the `numpy.random.choice`. I know a solution which is shuffling the array Fisher-Yates Shuffle, and extract the first n number. Is it there another way to solve this ?

1 Like

Most algorithms I can imagine are some variation on this. But perhaps this one (not necessarily efficient)

• Create a logical array, set all elements to .false.
• Randomly set elements to .true. until you have n different elements that are .true.
• When done, use pack() to compress the original array
2 Likes

But perhaps you should explain the background of your question John Burkardt has coded all algorithms in Fortran 90, in this case #1096 out of 1403, in

SUBSET , a FORTRAN90 code which enumerates, generates, randomizes, ranks and unranks combinatorial objects including combinations, compositions, Gray codes, index sets, partitions, permutations, polynomials, subsets, and Young tables. Backtracking routines are included to solve some combinatorial problems. Other routines handled continued fractions, and Diophantine equations.

The following driver

``````program xksub_random
! driver for John Burkardt's ksub_random2, which generates random subsets without replacement
implicit none
integer, parameter :: k = 10, n = 30, niter = 2
integer            :: i,j,a(k),seed,ncount(n)
write (*, "(a)") ""
write (*, "(a)") "KSUB_RANDOM2_TEST"
write (*, "(a)") "  KSUB_RANDOM2 generates a random K subset of an N set."
write (*, "(a,i8)") "  Set size is N =    ", n
write (*, "(a,i8)") "  Subset size is K = ", k
write (*, "(a)") ""
seed = 123456789
do i = 1, niter
ncount = 0
call ksub_random2(n,k,seed,a) ! inout: seed ; output: a
do j=1,k
ncount(a(j)) = ncount(a(j)) + 1
end do
write (*,"(/,5a8)") "imin","imax","count","max#","mean"
write (*,"(4i8,f8.1)") minval(a),maxval(a),sum(ncount),maxval(ncount),sum(dble(a))/k
write (*,"(/,'a =',*(1x,i0))") a
end do
end program xksub_random
``````

gave output

``````KSUB_RANDOM2_TEST
KSUB_RANDOM2 generates a random K subset of an N set.
Set size is N =          30
Subset size is K =       10

imin    imax   count    max#    mean
1      23      10       1    12.0

a = 1 6 7 8 9 11 16 19 20 23

imin    imax   count    max#    mean
1      28      10       1    14.0

a = 1 2 4 7 14 17 21 22 24 28``````
2 Likes

One of the references Burkardt provides for the SUBSET program is

ML Wolfson, HV Wright,
ACM Algorithm 160: Combinatorial of M Things Taken N at a Time,
Communications of the ACM,
Volume 6, Number 4, April 1963, page 161.

Is the short code presented there Algol 60? I wonder if it can be compiled. Many Algol codes have been translated to FORTRAN, but have they all been translated to modern Fortran? The Fortran code and text of another reference, Nijenhuis and Wilf: Combinatorial Algorithms, is here.