subroutine perm1_next3 ( n, p, more, rank )

c*********************************************************************72
c
cc perm1_next3() computes permutations of (1,...,N).
c
c  Discussion:
c
c    The routine is initialized by calling with MORE = TRUE, in which case
c    it returns the identity permutation.
c
c    If the routine is called with MORE = FALSE, then the successor of the
c    input permutation is computed.
c
c    Trotter's algorithm is used.
c
c  Licensing:
c
c    This code is distributed under the MIT license.
c
c  Modified:
c
c    16 August 2026
c
c  Author:
c
c    Original Fortran77 version by Hale Trotter,
c    This version by John Burkardt
c
c  Reference:
c
c    Hale Trotter,
c    Algorithm 115:
c    PERM,
c    Communications of the Association for Computing Machinery,
c    Volume 5, 1962, pages 434-435.
c
c  Input:
c
c    integer N, the number of objects being permuted.
c
c    integer P(N), the current permutation.
c
c    logical MORE: Set MORE = FALSE before first calling this routine.
c
c    integer RANK, the rank of the current permutation.
c
c  Output:
c
c    integer P(N): If MORE is TRUE, then P is the next permutation.
c    Otherwise, P will be set to the "first" permutation.
c
c    logical MORE: ORE will be reset to TRUE and a permutation will be returned.
c    Each new call produces a new permutation until MORE is returned FALSE.
c
c    integer RANK, the rank of the next permutation.
c
      implicit none

      integer n

      integer i
      integer m2
      logical more
      integer n2
      integer p(n)
      integer q
      integer rank
      integer s
      integer t

      if ( .not. more ) then

        do i = 1, n
          p(i) = i
        end do

        more = .true.
        rank = 1

      else

        n2 = n
        m2 = rank
        s = n

        do

          q = mod ( m2, n2 )
          t = mod ( m2, 2 * n2 )

          if ( q /= 0 ) then
            exit
          end if

          if ( t == 0 ) then
            s = s - 1
          end if

          m2 = m2 / n2
          n2 = n2 - 1

          if ( n2 == 0 ) then
            do i = 1, n
              p(i) = i
            end do
            more = .false.
            rank = 1
            exit
          end if

        end do

        if ( n2 /= 0 ) then

          if ( q == t ) then
            s = s - q
          else
            s = s + q - n2
          end if
c
c  Swap.
c
          t      = p(s)
          p(s)   = p(s+1)
          p(s+1) = t

          rank = rank + 1

        end if

      end if

      return
      end
      subroutine tsp_brute ( n, x, cost_min, order_min )

c*********************************************************************72
c
cc tsp_brute() uses a brute force approach to the traveling salesperson problem.
c
c  Licensing:
c
c    This code is distributed under the MIT license.
c
c  Modified:
c
c    16 August 2026
c
c  Author:
c
c    John Burkardt
c
      implicit none

      integer, parameter :: rk8 = kind ( 1.0D+00 )

      integer n

      real ( kind = rk8 ) cost
      real ( kind = rk8 ) cost_min
      integer i
      logical more
      integer order(n)
      integer order_min(n)
      integer rank
      real ( kind = rk8 ) x(n,2)

      cost_min = huge ( 1.0D+00 )
      cost = huge ( 1.0D+00 )

      do i = 1, n
        order(i) = i
        order_min(i) = i
      end do
c
c  Generate every permutation and examine it.
c
      more = .false.
      rank = 0

      do

        call perm1_next3 ( n, order, more, rank )

        if ( .not. more ) then
          exit
        end if

        call tsp_tour_cost ( n, x, order, cost )

        if ( cost < cost_min ) then
          cost_min = cost
          order_min(1:n) = order(1:n)
        end if

      end do

      return
      end
      subroutine tsp_tour_cost ( n, x, order, cost )

c*********************************************************************72
c
cc tsp_tour_cost() evaluates the cost of a round trip.
c
c  Licensing:
c
c    This code is distributed under the MIT license.
c
c  Modified:
c
c    16 August 2026
c
c  Author:
c
c    John Burkardt
c
c  Input:
c
c    integer n: the number of cities.
c
c    real x(n,2): the city locations.
c
c    integer order(n): a permutation of 1:N, the route.
c
c  Output:
c
c    real cost: the cost of the route.
c
      implicit none

      integer, parameter :: rk8 = kind ( 1.0D+00 )

      integer n

      real ( kind = rk8 ) cost
      integer from
      integer order(n)
      integer to
      real ( kind = rk8 ) x(n,2)

      cost = 0.0D+00
      from = n
      do to = 1, n
        cost = cost + sqrt ( ( x(order(from),1) - x(order(to),1) )**2 
     &                     + ( x(order(from),2) - x(order(to),2) )**2 )
        from = to
      end do

      return
      end