c-----------------------------------------------------------
c Chapter 4: Random k-subset of an n-set(p43)
c-----------------------------------------------------------
c   Name of subroutine: RANKSB
c
c   Algorithm:Choose a random k-subset of {1,2,...n}
c
c   input:    n=5, k=3
c   number of calls: run=100
c   complier: f77 ranksb_2.f
c-----------------------------------------------------------

      parameter(n=5,k=3,run=100)
      integer a(n)
      do 20 m=1,run 
      call ranksb(n,k,a)
      write(*,*),(a(i),i=1,k)
   20 continue    
      end


c-----Subroutine begins here--------------------------------
      subroutine ranksb(n,k,a)
      integer a(k),x,r,ds,p,s,c
      c=k
      do 1 i=1,k
    1 a(i)=(i-1)*n/k
   10 x=1+n*rand(iseed)
      l=1+(x*k-1)/n
      if(x.le.a(l))goto 10
      a(l)=a(l)+1
      c=c-1
      if(c.ne.0)goto 10
      p=0
      s=k
      do 20 i=1,k
      m=a(i)
      a(i)=0
      if(m.eq.(i-1)*n/k) goto 20
      p=p+1
      a(p)=m
   20 continue
   30 l=1+(a(p)*k-1)/n
      ds=a(p)-(l-1)*n/k
      a(p)=0
      a(s)=l
      s=s-ds
      p=p-1
      if(p.gt.0)goto 30
      l=k
   40 if(a(l).eq.0)goto 50
      r=l
      m0=1+(a(l)-1)*n/k
      m=a(l)*n/k-m0+1
   50 x=m0+m*rand(iseed)
      i=l
   60 i=i+1
      if(i.le.r)goto 80
   70 a(i-1)=x
      m=m-1
      l=l-1
      if(l.eq.0)return
      goto 40
   80 if(x.lt.a(i)) goto 70
      x=x+1
      a(i-1)=a(i)
      goto 60
      end

