semvec/pypi-packages huggingface dataset:
longestrunsubsequence 1.0.1
Algorithm to compute the longest run subsequence of a string
License: MIT License
Requires Python: >=3.5

# Longest Run Subsequence

Implementation of a solver for the Longest Run Subsequence Problem. Given a
sequence as input, compute a longest subsequence such that there is at most
one run for every character.

## Example

A longest run subsequence of the string `ccbcbbbdaaddd` is `cccbbbaaddd`.

## Algorithms

Depending on the properties of an instance the solver uses one of two algorithms to solve the problem.
For long strings with small alphabets a dynamic
programming approach is used, while short strings with large alphabets are
solved via Integer Linear Programming. Every input instance is processed by
reduction rules first to split it into smaller instances, if possible. Details can be found in [1]. 
Please consider citing this paper if you find the implementation useful for your work.

## Installation

The Integer Linear Program algorithm is only available if PuLP is
installed on the system. PuLP is a free API for modelling linear programs
and available on PyPI or conda.

## Usage

To solve Longest Run Subsequence instances, the function ``lrs`` has to be
imported from the module.

Example code::

    from longestrunsubsequence import lrs
    print(lrs('ccbcbbbdaaddd'))
    > [0, 1, 3, 4, 5, 6, 8, 9, 10, 11, 12]

The output is a list of indices, which represent the elements of the longest
subsequence. The input can be a string or a list with arbitrary elements.

## References

[1] Schrinner, S., Goel, M., Wulfert, M., Spohr, P., Schneeberger, K., Klau, G.W.: The Longest Run Subsequence Problem.
In: Kingsford, C., Pisanti, N. (eds.) 20th International Workshop on Algorithms in Bioinformatics (WABI 2020). 
Leibniz International Proceedings in Informatics (LIPIcs), vol. 172, pp. 6–1613. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany (2020). doi:10.4230/LIPIcs.WABI.2020.6.
https://drops.dagstuhl.de/opus/volltexte/2020/12795