program PN_nonperiodic
! Identification of leading pairwise-nonrecurrant NONPERIODIC sequences, by Thomas Bewley.
integer :: a(50),count(6),pairs(6,50),mm(6)
integer :: b,e,n,m,flag,s,s1,i,is,k,k2,ks,kb,ks1,t; integer*8 :: iter,ip=100000000
do m=6,6; iter=0; 
  select case (m)
  case (2); n=7;  a(1:n)=[0,0,0,0,1,1,1]+1;
  case (3); n=14; a(1:n)=[0,0,0,0,0,1,1,1,1,1,2,2,2,2]+1;
  case (4); n=24; a(1:n)=[0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,3]+1; 
  case (5); n=35; a(1:n)=[0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,              &
                          3,3,3,3,3,3,3,4,4,4,4,4,4,4]+1; 
  case (6); n=48; a(1:n)=[0,0,1,1,2,2,0,0,0,0,0,0,1,1,1,1,1,1,2,2,2,2,2,2,        &
                          3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5]+1;
  end select 
  write(*,'(A,I2,A,I2)') 'nonperiodic case: m=',m,', n=',n
  
  kb=2; pairs(1:m,1:n-1)=0;  
  do; iter=iter+1;  flag=1; 
    if (mod(iter,ip)==1) write(*,'(A,ES9.2,A,72I2)') 'iter=',real(iter), ', a=',a(1:n)-1
    l1: do ks=kb,n       ! Sweep to detect & disregard sequences with repeated pairs
      do k=1,ks-1; if (a(k)==a(ks)) then; s1=ks-k
        if (pairs(a(k),s1)==0) then
          pairs(a(k),s1)=k; 
        else ! If repeated pair detected, reorder elements after ks from largest 
             ! to smallest and then increment a (thus incrementing ks) via Alg L below
          count(1:m)=0; do i=ks+1,n; count(a(i))=count(a(i))+1; end do
          t=ks+1; do i=m,1,-1; l=count(i); a(t:t+l-1)=i; t=t+l; end do
          flag=0; exit l1
        end if
      end if; end do
    end do l1	
    if (flag==1) exit  ! If successful quit

    ! Find next permutation (First half of Algorithm L in Knuth 2005, Sec 7.2.1.2)
    b=min(ks,n-1); do while (b>0 .and. a(b)>=a(b+1)); b=b-1; end do;  ! b=begin, e=end
    e=n;   do while (a(b)>=a(e)); e=e-1; end do
    if (b==0) exit; kb=b;    ! If exhausted all permutations quit

    ! Reset the pertinent section of the pairs counter that must be recalculated
    ! during the next sweep.
    do k2=1,k-1; if (a(k2)==a(ks)) then  ! Reset contributions from the (bad) a(ks) entry
      s1=ks-k2; pairs(a(k2),s1)=0; 
    end if; end do;	
    do ks1=kb,ks-1           ! Reset contributions from the (modified) a(kb:ks-1) entries
      do k=1,ks1-1; if (a(k)==a(ks1)) then
        s1=ks1-k; pairs(a(k),s1)=0;
      end if; end do
    end do
		
    ! Second half of Algorithm L
    t=a(b); a(b)=a(e); a(e)=t;
    b=b+1; e=n; do while (b<e); t=a(b); a(b)=a(e); a(e)=t; b=b+1; e=e-1; end do
  end do

  write(*,'(A,72I2)') 'done: a=',a(1:n)-1
  write(*,'(A,I2,A,I2,A,I2,A,I32/)') 'success=',flag,', m=',m,', n=',n,', iter=',iter
end do
end program PN_nonperiodic