polymerist.genutils.sequences.discernment ========================================= .. py:module:: polymerist.genutils.sequences.discernment .. autoapi-nested-parse:: Tools for solving the DISCERNMENT (Determination of Index Sequences from Complete Enumeration of Ransom Notes - Multiset Extension with Nonlexical Types) problem DISCERNMENT problem definition: Given a "word" (a sequence of N symbols of type T), and a mapped sequence of "bins" (ordered collection of multisets of type T, each assigned a label of type L), enumerate all N-tuples of labels such that the symbols of the words could be drawn from the bins with those labels in that order Submodules ---------- .. toctree:: :maxdepth: 1 /autoapi/polymerist/genutils/sequences/discernment/enumeration/index /autoapi/polymerist/genutils/sequences/discernment/examples/index /autoapi/polymerist/genutils/sequences/discernment/inventory/index /autoapi/polymerist/genutils/sequences/discernment/strategies/index Classes ------- .. autoapisummary:: polymerist.genutils.sequences.discernment.DISCERNMENTSolver polymerist.genutils.sequences.discernment.DISCERNMENTStrategyStack polymerist.genutils.sequences.discernment.DISCERNMENTStrategyCartesian polymerist.genutils.sequences.discernment.DISCERNMENTStrategyRecursive polymerist.genutils.sequences.discernment.SymbolInventory Package Contents ---------------- .. py:class:: DISCERNMENTSolver(symbol_inventory: Union[polymerist.genutils.sequences.discernment.inventory.SymbolInventory[polymerist.genutils.sequences.discernment.inventory.T, polymerist.genutils.sequences.discernment.inventory.L], Sequence[Iterable[polymerist.genutils.sequences.discernment.inventory.T]], Mapping[polymerist.genutils.sequences.discernment.inventory.L, Sequence[Iterable[polymerist.genutils.sequences.discernment.inventory.T]]]], strategy: polymerist.genutils.sequences.discernment.strategies.DISCERNMENTStrategy = DISCERNMENTStrategyStack()) Encapsulation class for solving generalized ransom-note index enumeration problems for arbitrary words, bins, and solving algorithms .. py:attribute:: strategy .. py:property:: symbol_inventory :type: polymerist.genutils.sequences.discernment.inventory.SymbolInventory[polymerist.genutils.sequences.discernment.inventory.T, polymerist.genutils.sequences.discernment.inventory.L] Cast symbol inventory as copy to avoid mutation during partial traversals (i.e. peek at first item) .. py:method:: enumerate_choices(word: Sequence[polymerist.genutils.sequences.discernment.inventory.T], ignore_multiplicities: bool = False, unique_bins: bool = False) -> Generator[polymerist.genutils.sequences.discernment.inventory.L, None, None] Enumerate all possible choices using specified solution strategy .. py:method:: choice_solutions_exist(word: Sequence[polymerist.genutils.sequences.discernment.inventory.T], ignore_multiplicities: bool = False, unique_bins: bool = False) -> bool Precheck to see if a solution exists without attemting full enumeration .. py:class:: DISCERNMENTStrategyStack Bases: :py:obj:`DISCERNMENTStrategy` Stack-based implementation of generalized ransom note enumeration strategy Pushes all valid symbol-index pairs onto a stack for the current word positions, then advances and does the same until reaching the final symbol, backtracking and restoring symbols afterwards Fastest of all strategies across benchmark (except Cartesian **specifically** when ignore_multiplicities=True) .. py:method:: enumerate_choice_labels(word: Sequence[polymerist.genutils.sequences.discernment.inventory.T], symbol_inventory: polymerist.genutils.sequences.discernment.inventory.SymbolInventory[polymerist.genutils.sequences.discernment.inventory.T, polymerist.genutils.sequences.discernment.inventory.L], ignore_multiplicities: bool = False, unique_bins: bool = False) -> Generator[tuple[polymerist.genutils.sequences.discernment.inventory.L, Ellipsis], None, None] Takes a word (N-element sequence of type T) and a symbol inventory (map from symbols and bin labels to counts), Exhaustively enumerates all N-tuples of indices corresponding to ordering of bins from which the word could be drawn Support modifications to base behavior: *** If ignore_multiplicities=True, will not respect the counts of elements in each bin when drawing For a given symbol, this allows a bin containing the symbol to appear more times than that symbol is present in that bin *** If unique_bins=True, will only allow each bin to be sampled from once, EVEN if that bin contains symbols appearing later in the word .. py:class:: DISCERNMENTStrategyCartesian Bases: :py:obj:`DISCERNMENTStrategy` Naive implementation of generalized ransom note enumeration strategy based on cartesian products Generates all possible index sequences ignoring multiplicity, then checks them one-by-one to see if they're valid Roughly 1-2 OOM slower (prefactor) than Recursive and Stack unless ignoring multiplicity in which case this is ~1 OOM faster .. py:method:: enumerate_choice_labels(word: Sequence[polymerist.genutils.sequences.discernment.inventory.T], symbol_inventory: polymerist.genutils.sequences.discernment.inventory.SymbolInventory[polymerist.genutils.sequences.discernment.inventory.T, polymerist.genutils.sequences.discernment.inventory.L], ignore_multiplicities: bool = False, unique_bins: bool = False) -> Generator[tuple[polymerist.genutils.sequences.discernment.inventory.L, Ellipsis], None, None] Takes a word (N-element sequence of type T) and a symbol inventory (map from symbols and bin labels to counts), Exhaustively enumerates all N-tuples of indices corresponding to ordering of bins from which the word could be drawn Support modifications to base behavior: *** If ignore_multiplicities=True, will not respect the counts of elements in each bin when drawing For a given symbol, this allows a bin containing the symbol to appear more times than that symbol is present in that bin *** If unique_bins=True, will only allow each bin to be sampled from once, EVEN if that bin contains symbols appearing later in the word .. py:class:: DISCERNMENTStrategyRecursive Bases: :py:obj:`DISCERNMENTStrategy` Recursive implementation of generalized ransom note enumeration strategy via divide-and-conquer approach Breaks sequence down into first and all remaining symbols ("head" and "tail", respectively) Yields solution as all indices where the head occurs + recursive solutions to the tail sequence enumeration Easiest to analyze and reason about, but imposes cap on word length due to Python call stack size Performs intermediately in benchmark (faster than Cartesian, but slower than Stack) .. py:method:: enumerate_choice_labels(word: Sequence[polymerist.genutils.sequences.discernment.inventory.T], symbol_inventory: polymerist.genutils.sequences.discernment.inventory.SymbolInventory[polymerist.genutils.sequences.discernment.inventory.T, polymerist.genutils.sequences.discernment.inventory.L], ignore_multiplicities: bool = False, unique_bins: bool = False, _buffer: tuple[int] = None) -> Generator[tuple[polymerist.genutils.sequences.discernment.inventory.L, Ellipsis], None, None] Takes a word (N-element sequence of type T) and a symbol inventory (map from symbols and bin labels to counts), Exhaustively enumerates all N-tuples of indices corresponding to ordering of bins from which the word could be drawn Support modifications to base behavior: *** If ignore_multiplicities=True, will not respect the counts of elements in each bin when drawing For a given symbol, this allows a bin containing the symbol to appear more times than that symbol is present in that bin *** If unique_bins=True, will only allow each bin to be sampled from once, EVEN if that bin contains symbols appearing later in the word .. py:class:: SymbolInventory(*args, _number_of_symbols: Optional[int] = None, _number_of_bins: Optional[int] = None, _symbol_index_map: Optional[dict[T, int]] = None, _bin_index_map: Optional[dict[L, int]] = None, **kwargs) Bases: :py:obj:`dict`, :py:obj:`Generic`\ [\ :py:obj:`T`\ , :py:obj:`L`\ ] Representation of a map from a set of symbols of type T and a set of bin labels of type L to integer counts Implemented as a dict, keyed by symbol, whose values count the number of occurrences of that symbol in all bins that symbol occurs Data structure with specific methods which are useful in solving the generalized ransom note enumeration problem .. py:method:: from_bin_sequence_mapping(choice_bin_map: Mapping[L, Sequence[Iterable[T]]], _symbol_index_map: Optional[dict[T, int]] = None, _bin_index_map: Optional[dict[L, int]] = None) -> SymbolInventory[T, L] :classmethod: Initialize inventory from a mapping of labels to bins .. py:method:: from_bin_sequence(choice_bins: Sequence[Iterable[T]]) -> SymbolInventory[T, int] :classmethod: Initialize inventory from an ordered sequence of bins Special case of mapping instantiation for sequences of bins; simply uses the index of a bin as its label .. py:method:: from_bins(choice_bins: Union[Sequence[Iterable[T]], dict[L, Sequence[Iterable[T]]]]) -> SymbolInventory[T, L] :classmethod: "Smart" initialization method which dispatches to from_bin_sequence() or from_bin_sequence_mapping(), depending on the nature of the "choice_bins" container provided .. py:property:: number_of_symbols :type: int Number of unique symbols present in the SymbolInventory .. py:property:: number_of_bins :type: int Number of unique symbols present in the SymbolInventory .. py:property:: symbol_index_map :type: dict[T, int] Arbitrary one-to-one mapping between all symbols present in the inventory and integer indices .. py:property:: bin_index_map :type: dict[T, int] Arbitrary one-to-one mapping between all bins present in the inventory and integer indices .. py:method:: contains_word(sequence: Sequence[T], ignore_multiplicities: bool = False) -> bool Check if a word (i.e. sequence of symbols of type T) could possibly be produced from a SymbolInventory Returns bool; True indicated the word can be made from the inventory False return indicates the sequence contains symbols not present in the inventory OR contains more of one particular symbol than are present in the whole inventory .. py:method:: deepcopy() -> SymbolInventory[T, L] Create a deep copy of the current SymbolInventory .. py:property:: involution :type: SymbolInventory[L, T] Returns a new SymbolInventory which switches the order of precedence of the symbols and bin labels So-called because self.involution.involution returns a SymbolInventory identical to self (by construction) .. py:property:: occurence_matrix :type: Union[list[list[int]], numpy.ndarray[Any, int]] Creates an NxM matrix (N is the number of symbols, and M is the number of bins) which represents a SymbolInventory Matrix element A_ij denotes the number of occurences of the i-th symbol (according to an arbitrary numbering) in the j-th bin Will attempt to return matrix as a 2-D numpy array, but will default to a doubly-nested list if numpy is not found to be installed