code: def _optimal_path(input_sets, output_set, idx_dict, memory_limit):
      """
      Computes all possible pair contractions, sieves the results based
      on ``memory_limit`` and returns the lowest cost path. This algorithm
      scales factorial with respect to the elements in the list ``input_sets``.
  
      Parameters
      ----------
      input_sets : list
          List of sets that represent the lhs side of the einsum subscript
      output_set : set
          Set that represents the rhs side of the overall einsum subscript
      idx_dict : dictionary
          Dictionary of index sizes
      memory_limit : int
          The maximum number of elements in a temporary array
  
      Returns
      -------
      path : list
          The optimal contraction order within the memory limit constraint.
  
      Examples
      --------
      >>> isets = [set('abd'), set('ac'), set('bdc')]
      >>> oset = set()
      >>> idx_sizes = {'a': 1, 'b':2, 'c':3, 'd':4}
      >>> _optimal_path(isets, oset, idx_sizes, 5000)
      [(0, 2), (0, 1)]
      """
  
      full_results = [(0, [], input_sets)]
      for iteration in range(len(input_sets) - 1):
          iter_results = []
  
          # Compute all unique pairs
          for curr in full_results:
              cost, positions, remaining = curr
              for con in itertools.combinations(
                  range(len(input_sets) - iteration), 2
              ):
                  # Find the contraction
                  cont = _find_contraction(con, remaining, output_set)
                  (
                      new_result,
                      new_input_sets,
                      idx_removed,
                      idx_contract,
                  ) = cont
  
                  # Sieve the results based on memory_limit
                  new_size = _compute_size_by_dict(new_result, idx_dict)
                  if new_size > memory_limit:
                      continue
  
                  # Build (total_cost, positions, indices_remaining)
                  total_cost = cost + _flop_count(
                      idx_contract, idx_removed, len(con), idx_dict
                  )
                  new_pos = positions + [con]
                  iter_results.append(
                      (total_cost, new_pos, new_input_sets)
                  )
  
          # Update combinatorial list, if we did not find anything return best
          # path + remaining contractions
          if iter_results:
              full_results = iter_results
          else:
              path = min(full_results, key=lambda x: x[0])[1]
              path += [tuple(range(len(input_sets) - iteration))]
              return path
  
      # If we have not found anything return single einsum contraction
      if len(full_results) == 0:
          return [tuple(range(len(input_sets)))]
  
      path = min(full_results, key=lambda x: x[0])[1]
      return path
  
file_path: mars/mars/tensor/einsum/einsumfunc.py
imports: import itertools
  from numpy.compat import basestring
  from ..datasource.array import tensor
label_desc: Use image node_id 4 for calling a global function with example usage: _optimal_path(input_sets, output_set, idx_dict, memory_limit) and returns: path, list, path