c-----------------------------------------------------------
c Chapter 9: Next partition of integer n(p69)
c-----------------------------------------------------------
c   Name of subroutine: NEXPAR
c
c   Algorithm:Find next partition of n.
c
c   input:    n=10
c   complier: f77 nexpar.f
c-----------------------------------------------------------
      
	program driver
	parameter (n=10)
	logical mtc
	integer r(n), m(n), d
	integer i
	write(6,*) "The number for output partition is 10"
	write(6,*) "Please input the number of distinct parts in output partition:"
	read(5,*) d
	write(6,*) "Read in the initial R(10):"
	read(5,*) (r(i), i=1,n)
	write(6,*) "Read in the initial M(10):"
	read(5,*) (m(i), i=1,n)
	mtc=.false.	

	call nexpar(n, r, m, d, mtc)
	write(6,*) "The distinct parts of the output partition:"
	write(6,7 ) (r(i), i=1,n)
	write(6,*) "The multiplicity of the distinct parts of the output partition:"
	write(6,7 ) (m(i), i=1,n)
7	format(10i3)
	end

c-----Subroutine begins here------------------------------------------------
      subroutine nexpar(n,r,m,d,mtc)
      implicit integer(a-z)
      logical mtc
      dimension m(n),r(n)
      data nlast/0/
   10 if(n.eq.nlast) go to 20
      nlast=n
   30 s=n
      d=0
   50 d=d+1
      r(d)=s
      m(d)=1
   40 mtc=m(d).ne.n
      return
   20 if(.not.mtc) go to 30
      sum=1
      if(r(d).gt.1) go to 60
      sum=m(d)+1
      d=d-1
   60 f=r(d)-1
      if(m(d).eq.1) go to 70
      m(d)=m(d)-1
      d=d+1
   70 r(d)=f
      m(d)=1+sum/f
      s=mod(sum,f)
      if(s) 40,40,50
      end

