# Path: opt_einsum/helpers.py
# @overload
# def compute_size_by_dict(indices: Iterable[int], idx_dict: List[int]) -> int:
#     ...
# 
# def flop_count(
#     idx_contraction: Collection[str],
#     inner: bool,
#     num_terms: int,
#     size_dictionary: Dict[str, int],
# ) -> int:
#     """
#     Computes the number of FLOPS in the contraction.
# 
#     Parameters
#     ----------
#     idx_contraction : iterable
#         The indices involved in the contraction
#     inner : bool
#         Does this contraction require an inner product?
#     num_terms : int
#         The number of terms in a contraction
#     size_dictionary : dict
#         The size of each of the indices in idx_contraction
# 
#     Returns
#     -------
#     flop_count : int
#         The total number of FLOPS required for the contraction.
# 
#     Examples
#     --------
# 
#     >>> flop_count('abc', False, 1, {'a': 2, 'b':3, 'c':5})
#     30
# 
#     >>> flop_count('abc', True, 2, {'a': 2, 'b':3, 'c':5})
#     60
# 
#     """
# 
#     overall_size = compute_size_by_dict(idx_contraction, size_dictionary)
#     op_factor = max(1, num_terms - 1)
#     if inner:
#         op_factor += 1
# 
#     return overall_size * op_factor
# 
# Path: opt_einsum/typing.py



import functools
import heapq
import itertools
import operator
import random
import re
import numpy as np
from collections import Counter, OrderedDict, defaultdict
from typing import Any, Callable
from typing import Counter as CounterType
from typing import Dict, FrozenSet, Generator, List, Optional, Sequence, Set, Tuple, Union
from .helpers import compute_size_by_dict, flop_count
from .typing import ArrayIndexType, PathType
    from .path_random import random_greedy_128
    - **minimize** - *({'flops', 'size', 'write', 'combo', 'limit', callable}, optional)* What to minimize:

        - 'flops' - minimize the number of flops
        - 'size' - minimize the size of the largest intermediate
        - 'write' - minimize the size of all intermediate tensors
        - 'combo' - minimize `flops + alpha * write` summed over intermediates, a default ratio of alpha=64
          is used, or it can be customized with `f'combo-{alpha}'`
        - 'limit' - minimize `max(flops, alpha * write)` summed over intermediates, a default ratio of alpha=64
          is used, or it can be customized with `f'limit-{alpha}'`
        - callable - a custom local cost function

    - **cost_cap** - *({True, False, int}, optional)* How to implement cost-capping:

        - True - iteratively increase the cost-cap
        - False - implement no cost-cap at all
        - int - use explicit cost cap

    - **search_outer** - *(bool, optional)* In rare circumstances the optimal contraction may involve an outer
        product, this option allows searching such contractions but may well
        slow down the path finding considerably on all but very small graphs.
    """

    def __init__(self, minimize: str = "flops", cost_cap: bool = True, search_outer: bool = False) -> None:
        self.minimize = minimize
        self.search_outer = search_outer
        self.cost_cap = cost_cap

    def __call__(
        self,
        inputs_: List[ArrayIndexType],

# Path: opt_einsum/helpers.py
# @overload
# def compute_size_by_dict(indices: Iterable[int], idx_dict: List[int]) -> int:
#     ...
# 
# def flop_count(
#     idx_contraction: Collection[str],
#     inner: bool,
#     num_terms: int,
#     size_dictionary: Dict[str, int],
# ) -> int:
#     """
#     Computes the number of FLOPS in the contraction.
# 
#     Parameters
#     ----------
#     idx_contraction : iterable
#         The indices involved in the contraction
#     inner : bool
#         Does this contraction require an inner product?
#     num_terms : int
#         The number of terms in a contraction
#     size_dictionary : dict
#         The size of each of the indices in idx_contraction
# 
#     Returns
#     -------
#     flop_count : int
#         The total number of FLOPS required for the contraction.
# 
#     Examples
#     --------
# 
#     >>> flop_count('abc', False, 1, {'a': 2, 'b':3, 'c':5})
#     30
# 
#     >>> flop_count('abc', True, 2, {'a': 2, 'b':3, 'c':5})
#     60
# 
#     """
# 
#     overall_size = compute_size_by_dict(idx_contraction, size_dictionary)
#     op_factor = max(1, num_terms - 1)
#     if inner:
#         op_factor += 1
# 
#     return overall_size * op_factor
# 
# Path: opt_einsum/typing.py



# Path: opt_einsum/paths.py
import functools
import heapq
import itertools
import operator
import random
import re
import numpy as np
from collections import Counter, OrderedDict, defaultdict
from typing import Any, Callable
from typing import Counter as CounterType
from typing import Dict, FrozenSet, Generator, List, Optional, Sequence, Set, Tuple, Union
from .helpers import compute_size_by_dict, flop_count
from .typing import ArrayIndexType, PathType
    from .path_random import random_greedy_128

    - **minimize** - *({'flops', 'size', 'write', 'combo', 'limit', callable}, optional)* What to minimize:

        - 'flops' - minimize the number of flops
        - 'size' - minimize the size of the largest intermediate
        - 'write' - minimize the size of all intermediate tensors
        - 'combo' - minimize `flops + alpha * write` summed over intermediates, a default ratio of alpha=64
          is used, or it can be customized with `f'combo-{alpha}'`
        - 'limit' - minimize `max(flops, alpha * write)` summed over intermediates, a default ratio of alpha=64
          is used, or it can be customized with `f'limit-{alpha}'`
        - callable - a custom local cost function

    - **cost_cap** - *({True, False, int}, optional)* How to implement cost-capping:

        - True - iteratively increase the cost-cap
        - False - implement no cost-cap at all
        - int - use explicit cost cap

    - **search_outer** - *(bool, optional)* In rare circumstances the optimal contraction may involve an outer
        product, this option allows searching such contractions but may well
        slow down the path finding considerably on all but very small graphs.
    """

    def __init__(self, minimize: str = "flops", cost_cap: bool = True, search_outer: bool = False) -> None:
        self.minimize = minimize
        self.search_outer = search_outer
        self.cost_cap = cost_cap

    def __call__(
        self,
        inputs_: List[ArrayIndexType],

        output_: ArrayIndexType,