string - 包含字符列表的所有固定长度子串(子集的任意 1 个排列)的最短字符串

Question

如果给我一个字符列表 {s1,s2,s3,...,s10}，我想找到一个长度最短的字符串，其中长度为 3 的所有无序子集组合都作为字符串中的子字符串出现。例如，如果我考虑子集 { s2, s4, s9 } 那么我将能够找到至少一个包含这三个字符的字符串实例(以任何顺序作为子字符串)。没有重复，因为不需要包含 's1s1s1' 形式的子字符串。

Answer 1

我使用 MiniZinc 解决了这个问题约束求解器:

%  dimensions
int: N = 10;  %  number of characters
set of int: Characters = 1..N;
int: L = 416;  %  length of shortest string

%  decision variables
array[0..L-1] of var Characters: shortest;

%  every unordered subset must occur somewhere in shortest
constraint forall(a, b, c in 1..N where (a < b) /\ (b < c)) (
    exists(i in 0..L-3) (
        ((shortest[i] == a) \/(shortest[i+1] == a) \/ (shortest[i+2] == a)) /\
        ((shortest[i] == b) \/(shortest[i+1] == b) \/ (shortest[i+2] == b)) /\
        ((shortest[i] == c) \/(shortest[i+1] == c) \/ (shortest[i+2] == c))
    )
  );

%  to speed things up, we enforce the first N entries
constraint forall(i in 0..N-1) (
  shortest[i] == i+1
);

%  further speedup: adjacent entries are probably different
constraint forall(i in N..L-2) (
  shortest[i] != shortest[i+1]
);

solve satisfy;

%
%  Output solution as table of variable value assignments
%%
output 
[ show(shortest[i]) ++ " " | i in 0..L-1 ];

对于5个字符的字符集，瞬间找到解决方案:

1 2 3 4 5 1 2 4 1 3 5 2 4 

但对于更多字符，更不用说 10 个字符，搜索时间太长而不实用。

我注意到每增加一个字符，最小长度似乎大约翻倍。 对于 3 个字符，长度通常为 3。对于 4 个字符，长度为 6，对于 5 个字符，长度为 13。但是我找不到 6 个或更多字符的解决方案。

我找到了一篇相关论文On strings containing all subsets as substrings这证实了我对 5 个字符的发现。但这篇论文早在 1978 年就发表了。可能存在更多最近的发现。