Amusing myself with concepts from "Omnibus Sequences, Coupon Collection, and Missing Word Counts", in particular the sequences.
To paraphrase the concept, a string is k-Omni over some alphabet a if any string of length k (or less) from the alphabet can be found as a sequence of the string.
e.g.,
string={5, 4, 0, 5, 3, 3, 1, 4, 0, 2, 4, 0, 2, 3, 5, 0, 0, 0, 5, 4, 2, 3, 3, 5, 5, 4, 1, 5, 5, 4, 4, 5, 3, 2, 1, 3, 1, 2, 2, 4}
is 2-Omni over the alphabet of the string, and 4-Omni over a restricted alphabet of {1,2,3}
.
I'm using
kOmni = Block[{f = Total@BitSet[0, DeleteDuplicates@#1], z, cnt = 0},
Fold[If[(z = BitAnd[f, BitSet[#, #2]]) == f, cnt++; 0, z] &, 0, #2];cnt] &
which takes the alphabet and string as arguments, to determine the k for various conditions, e.g. kOmni[{1, 2, 3}, string]
returns the desired 4 result.
Might there be a more efficient way to do this? You can assume strings (and alphabets) are limited to non-negative integers, and alphabets are almost always under 200 distinct values, but the strings can be quite large (>10^5 elements).
Update: An optimization I came up with nodding off...
kOmniO = Block[{f, z, cnt = 0, s = #2, a = DeleteDuplicates@#1},
s = Join[a, s];
s = s[[Sort@(Join @@
GatherBy[Range@Length@s, s[[#]] &][[;; Length@a, 2 ;;]])]];
f = Total@BitSet[0, a];
Fold[If[(z = BitSet[#, #2]) == f, cnt++; 0, z] &, 0, s];
cnt] &
About 50% faster for full alphabet, and with alphabet that is a subset of string alphabet, can be over an order of magnitude faster. I still have a gut feeling there's a faster/smarter way to do this... c'mon wizards ;-)
Tuples[{1, 2, 3}, {4}]
...And @@ (LongestCommonSequence[#, string] == # & /@ Tuples[{1, 2, 3}, {#}]) & /@ {4, 5}
->{True,False}
So, the string in the example has all of those tuples of length 4 as subsequences, and it is 4-omni (not the subsequences themselves). $\endgroup$