Definitions
An -formation is a concatenation of permutations of letters, e.g. is a -formation.
For every sequence define , the formation width of , to be the minimum for which there exists such that there is a subsequence isomorphic to in every -formation.
The algorithm in the second paper is faster than the first, but both algorithms are very slow. Find a faster algorithm to compute .
Notes
Both papers have Python formation width algorithms at the end.
Suppose that and . A formation with all permutations equal to or for some is called a binary formation.
The key fact used for both algorithms is Corollary 12 in the first paper:
If has distinct letters, then every binary -formation contains if and only if .
Algorithm for calculating :
Let be the number of distinct letters in . Starting with , check if every binary -formation contains . If so, output and halt. Otherwise increment and repeat.
One of the problems for is to find an algorithm to compute that is polynomial-time in the length of . There is already a polynomial-time algorithm for when has two distinct letters. Is there a polynomial-time algorithm for for sequences with three distinct letters?
probabilistic algorithms for computing formation width
JGeneson2
NNov 26, 2019
by solvingking
For definition of , see the Problems page.
Any ideas for probabilistic algorithms for computing ?
For example, how accurate a value can we get for by checking only a random subset of the binary formations with permutations instead of the full set of binary formations with permutations in order to to compute ?