polymerist.genutils.sequences.discernment.strategies

Abstract base and concrete implementations of algorithms which solve the DISCERNMENT Problem

Attributes

P

Classes

`DISCERNMENTStrategy`	DISCERNMENT = the Determination of Index Sequences from Complete Enumeration of Ransom Notes (Multiset Extension with Nonlexical Types)
`DISCERNMENTStrategyCartesian`	Naive implementation of generalized ransom note enumeration strategy based on cartesian products
`DISCERNMENTStrategyRecursive`	Recursive implementation of generalized ransom note enumeration strategy via divide-and-conquer approach
`DISCERNMENTStrategyStack`	Stack-based implementation of generalized ransom note enumeration strategy

Functions

is_unique(→ bool)

Whether or not a Sequence contains repeating items

Module Contents

polymerist.genutils.sequences.discernment.strategies.P

polymerist.genutils.sequences.discernment.strategies.is_unique(seq: Sequence) → bool[source]: Whether or not a Sequence contains repeating items

class polymerist.genutils.sequences.discernment.strategies.DISCERNMENTStrategy[source]

Bases: abc.ABC, Generic[polymerist.genutils.sequences.discernment.inventory.T, polymerist.genutils.sequences.discernment.inventory.L]

DISCERNMENT = the Determination of Index Sequences from Complete Enumeration of Ransom Notes (Multiset Extension with Nonlexical Types) Provides an implementation of the general ransom note enumeration problem

abstractmethod 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, **kwargs: P) → Generator[tuple[polymerist.genutils.sequences.discernment.inventory.L, Ellipsis], None, None][source]

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

class polymerist.genutils.sequences.discernment.strategies.DISCERNMENTStrategyCartesian[source]

Bases: 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

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][source]

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

class polymerist.genutils.sequences.discernment.strategies.DISCERNMENTStrategyRecursive[source]

Bases: 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)

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][source]

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

class polymerist.genutils.sequences.discernment.strategies.DISCERNMENTStrategyStack[source]

Bases: 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)

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][source]

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