c-----------------------------------------------------------------
c Chapter 3: Next k-subset of an n-set(p33)
c-----------------------------------------------------------------
c   Name of subroutine: NXKSRD
c
c   Algorithm:Generating subsets of {1,2,...,n} which
c             succeed input set, in lexicographical order, 
c             with optional jumps over supersets.     
c
c   input: n=7, k=4
c   compiler: f77 nxksrd_2.f
c-----------------------------------------------------------------

      parameter(n=7,k=4)
      logical mtc
      integer a(n) 
      mtc=.false.
10    call nxksrd(n,k,a,mtc,in,out)
      write(*,20) ,(a(i),i=1,k),in,out
20    format(1x,4(i2,1x),1x,i2,2x,i2)
      if(mtc)goto 10
      stop
      end   

c-----Subroutine begins here--------------------------------------
      subroutine nxksrd(n,k,a,mtc,in,out)
      integer a(k),out
      logical mtc
      if(mtc) goto 10
      do 1 i=1,k
    1 a(i)=i
      mtc=k.ne.n
      return
   10 j=0
   20 if(mod(k,2).ne.0)goto 100
   30 j=j+1
c 40 if(j.le.k)goto 60
c 50 a(k)=k
c in=k
c out=n
c return
   60 if(a(j).eq.j)goto 100
   70 out=a(j)
      in=out-1
      a(j)=in
   80 if(j.eq.1)goto 200
   90 in=j-1
      a(j-1)=in
      goto 200
  100 j=j+1
  130 m=n
  110 if(j.lt.k)m=a(j+1)-1
  140 if(m.eq.a(j)) goto 30
  150 in=a(j)+1
      a(j)=in
      out=in-1
      if(j.eq.1)goto 200
      a(j-1)=out
      out=j-1
  200 if(k.eq.1)goto 201
      mtc=a(k-1).eq.k-1
  201 mtc=(.not.mtc).or.a(k).ne.n
      return
      end


