Y by RedFireTruck, ImSh95, Adventure10, Mango247
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.
Problem:
In the first papers on (https://arxiv.org/abs/1308.3810 and https://arxiv.org/abs/1502.04095), we found an algorithm to calculate for any sequence .
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.
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.
Problem:
In the first papers on (https://arxiv.org/abs/1308.3810 and https://arxiv.org/abs/1502.04095), we found an algorithm to calculate for any sequence .
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.