function [ cost, p ] = matrix_chain_brute ( dims )

%*****************************************************************************80
%
%% matrix_chain_brute() finds the lowest cost to form a multiple matrix product.
%
%  Discussion:
%
%    This code represents a brute force approach.
%
%    An "efficient" brute force approach would only go through every
%    possible parenthesization of the multiplication, and a cost of
%    catalan(n_mats-1).  But it's not clear to me how to generate a sequence
%    of parentheses and properly interpret them as a multiplication ordering.
%
%    Instead, we rely on the fact that, to multiply N matrices, there are
%    N-1 multiplications to carry out, in any order.  This means that,
%    if we do some careful bookkeeping, we have N-1 choices for the first
%    multiplication, N-2 for the second, and a total of factorial(N-1)    
%    distinct cases to consider.  Some of these cases collapse to the
%    same paretheses representation, but we don't care.
%
%  Licensing:
%
%    This code is distributed under the MIT license.
%
%  Modified:
%
%    26 June 2024
%
%  Author:
%
%    John Burkardt
%
%  Input:
%
%    integer dims(n_mats+1): matrix dimension information.  Matrix A(i)
%    has dimensions dims(i) x dims(i+1).  All entries must be positive.
%
%  Output:
%
%    integer cost: the minimal cost, in terms of scalar multiplications,
%    for the optimal ordering of the matrix multiplications.
%
%    integer p(n_mats-1): defines the order of the multiplications.
%
  n_dims = length ( dims );
  n_mats = n_dims - 1;
  n_mults = n_mats - 1;
%
%  Deal with stupidity.
%
  if ( n_mats == 1 )
    cost = 0;
    p = [ ];
    return
  end

  if ( any ( dims <= 0 ) )
    cost = 0;
    p = linspace ( n_mults, 1, n_mults );
    return
  end
%
%  Initialize the output.
%
  cost = inf;
  p = linspace ( n_mults, 1, n_mults );
%
%  Prepare to loop over all orderings.
%
  this_p = p;
  pivot_sequence_num = pivot_sequence_enum ( n_mults );

  for i = 1 : pivot_sequence_num

    this_p = pivot_sequence_successor ( this_p );
    this_cost = pivot_sequence_to_matrix_chain_cost ( n_mats, this_p, dims );

    if ( this_cost < cost )
      cost = this_cost;
      p = this_p;
    end

  end

  return
end

