Блог

Если мне предоставлен список символов, скажем {s1,s2, s3, …, s10}, я хочу найти строку наименьшей длины, содержащую все неупорядоченные комбинации подмножеств длины три, встречающиеся в качестве подстрок внутри строки. Например, если я рассмотрю подмножество { s2, s4, s9}, то я смогу найти по крайней мере один экземпляр строки, содержащей эти три символа в любом порядке, в качестве подстроки. Здесь нет повторов, так как в нем не требуется включать подстроку вида ‘s1s1s1’.

Я решил эту проблему, используя решатель ограничений 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 или более символов.

Я нашел соответствующую статью О строках, содержащих все подмножества в качестве подстрок, которая подтверждает мой вывод для 5 символов. Но статья была опубликована еще в 1978 году. Могут существовать более поздние открытия.