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

Help
1

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
2

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
3

But perhaps you should explain the background of your question :slight_smile:

4

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
5

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.