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-----------------------------------------------------------------

c-----   The driver program is in nxksrd_2.f  --------------------

c-----Subroutine begins here--------------------------------------
      subroutine nxksrd(n,k,a,mtc,in,out)
      integer a(k),out
      logical mtc
      data nlast,klast/0,0/
5     if(n.eq.nlast.and.k.eq.klast) go to 20
      nlast=n
      klast=k
6     mtc=.true.
10    do 11  i=1,k
11    a(i)=i
      in=0
      out=0
      go to 120
20    if(.not.mtc)  go to 6
25    if(mod(k,2).eq.0) go to 29
26    if(k.eq.1.or.a(2)-a(1).gt.1)  go to 100
27    if(a(1).gt.1) go to 110
28    km1=k-1
      do 40  n1=1,km1
      if(a(n1+1).gt.a(n1)+1)  go to 41
40    continue
      n1=k
41    if(mod(n1+k,2).eq.0)  go to 60
30    if(n1.eq.km1.or.(n1.lt.km1.and.a(n1+2).gt.a(n1+1)+1)) go to 90
      go to 80
29    if(a(1)-1) 29,28,70
60    out=a(n1-1)
      in=out+2
      a(n1-1)=a(n1)
      a(n1)=out+2
      go to 120
70    in=a(1)-1
      out=a(1)
      a(1)=in
      go to 120
80    in=a(n1)+1
      out=a(n1+2)
      a(n1+2)=a(n1+1)
      a(n1+1)=in
      go to 120
90    in=a(n1+1)+1
      out=a(n1)
      a(n1)=in-1
      a(n1+1)=in
      go to 120
100   in=a(1)+1
      out=a(1)
      a(1)=in
      go to 120
110   in=1
      out=a(2)
      a(2)=a(1)
      a(1)=1
120   mtc=a(k).ne.n.or.(k.ne.1.and.a(k-1).ne.k-1)
      return
      end