Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Приветсвую, Олл!
PD>Решил и я предложить одну задачу. Возникла она у нас однажды, немного в PD>другой упаковке. Решить не смогли, и до сих пор решения я не знаю.
Так вы её решили хоть как-нибудь? Типа тупым перебором?
PD>Есть N строк разной длины. PD>Сформировать строку минимальной длины, в которой присутствовали бы все PD>эти N строк в качестве подстрок.
Самое примитивное — сложить все эти N строк, затем убирать более однократные вхождения. Тут можно построить лес вхождения строк в строки, т.е. напр. для строк аб и абц будет достаточно вхождения строки абц. Но на этом останавливаться глупо, т.к. ещё результат может зависеть от порядка конкатенации...
Примерно такие пока первые мысли...
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Решил и я предложить одну задачу. Возникла она у нас однажды, немного в PD>другой упаковке. Решить не смогли, и до сих пор решения я не знаю.
PD>Есть N строк разной длины. PD>Сформировать строку минимальной длины, в которой присутствовали бы все PD>эти N строк в качестве подстрок.
Эта задача имеет простое решение для N=2.
Для N>2 боюсь все намного мрачнее.
Пусть у нас
N - количество строк
s[i] - строки (i=0..N-1)
S - ответ
1. Сразу можно выкинуть все строки, являющиеся подстроками какой-либо другой строки. Далее предполагаем, что таких нет.
2. Очевидно, что S однозначно восстанавливается по N парам чисел
p[i] - какую строку брать i-й
l[i] - как далеко ее левый конец уходит в нашу строку
(i=0..N-1)
l[0] = 0;
l[i] < length(s[p[i-1]]) - из-за 1. (*)
3. Теорема. Пусть определен порядок p[i]. Тогда, при добавлении очережной строки, нужно бырать максимальное l[i].
Доказательство следует из (*).
4. Вычислим
L[i][j] = lenght(s[j]) - l[j], если до нее шла строка i
Задача сводится к нахождению Гамильтонова пути миниального веса.
5. Я думаю, такая задача хорошо изучена. Дальше предлагается решать методом ветвей и границ или генетическим алгоритмом.
Курилка wrote: > > Здравствуйте, Pavel Dvorkin, Вы писали: > > PD>Приветсвую, Олл! > > PD>Решил и я предложить одну задачу. Возникла она у нас однажды, немного в > PD>другой упаковке. Решить не смогли, и до сих пор решения я не знаю. > > Так вы её решили хоть как-нибудь? Типа тупым перебором?
Нет. Изменили алгоритм, так, что решать не потребовалось.
> > PD>Есть N строк разной длины. > PD>Сформировать строку минимальной длины, в которой присутствовали бы все > PD>эти N строк в качестве подстрок. > > Самое примитивное — сложить все эти N строк
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Привет!
PD>Курилка wrote: >> >> >> Самое примитивное — сложить все эти N строк
PD>Во всех комбинациях ? n! ?
Да нет — это уже будет лишнее если все сложить, то комбинации тут никчему, хотя если тупым перебором и поиском минимума, то будет так, хотя можно проверять вхождение сложив k строк (т.е. < n) и если в результате какую-то из строк можно выкинуть, то она уже не будет включаться и увеличивать число комбинаций, хотя я не думаю, что это радикально уменьшит число комбинаций...
Здравствуйте, Tan4ik, Вы писали:
T>Для N>2 боюсь все намного мрачнее.
Без особой потери общности, мы можем представить строки цепочками "наименьших общих слагаемых".
Например, abcde, cdefg, efghi = (ab)(cd)(e) (cd)(e)(f)(g) (e)(f)(g)(hi)
Получаем новое множество строк (теперь — на алфавите из лексем).
Каждой лексеме соответствует вес (её длина в исходном алфавите).
Построим недетерминированный конечный автомат Мура: лексеме соответствует состояние (вершина орграфа).
А строка задаёт набор переходов между состояниями (рёбра орграфа).
Введём дополнительные рёбра, соответствующие всем возможным склеиваниям строк.
Наша задача — обойти все вершины орграфа.
На самом деле, нам нужно обеспечить, чтобы исходные строки обязательно были пройдены.
Для этого:
1) Каждое реальное ребро (у пары смежных лексем) разрежем, вставив в него уникальную нуль-лексему (которой соответствует пустая цепочка). Между нуль-лексемами никаких дополнительных рёбер нет.
Чтобы породить все строки, необходимо (но не достаточно) посетить не только вершины с лексемами, но и вершины нуль-лексем.
2) Как-то нужно избежать "перекрёстков".
Например, в языке есть строки L1.L3.L4, L2.L3.L5.
Соответственно, можно полностью покрыть наш орграф в два захода: L2.L3.L4 и L1.L3.L5,
при этом смежность будет соблюдена, но ни одну из строк мы не породим.
Я не знаю, как навязать правильные пути, за исключением дублирования состояний (как это делается при преобразовании НДКА в ДКА). Но тогда встанет вопрос об избыточности. То есть, даже найдя гамильтонов путь, мы необязательно получим минимальное решение.
Хотя... если после детерминирования КА мы его ещё и минимизируем...
Кодт wrote: > > Здравствуйте, Tan4ik, Вы писали: > > T>Для N>2 боюсь все намного мрачнее. > > Без особой потери общности, мы можем представить строки цепочками "наименьших общих слагаемых". > Например, abcde, cdefg, efghi = (ab)(cd)(e) (cd)(e)(f)(g) (e)(f)(g)(hi)
Алгортим ? И какой у него будет временная зависимость ?
T>N - количество строк
T>s[i] - строки (i=0..N-1)
T>S - ответ
T>
T>1. Сразу можно выкинуть все строки, являющиеся подстроками какой-либо другой строки. Далее предполагаем, что таких нет.
Да, согласен.
T>2. Очевидно, что S однозначно восстанавливается по N парам чисел T>
T>p[i] - какую строку брать i-й
T>l[i] - как далеко ее левый конец уходит в нашу строку
T>(i=0..N-1)
T>l[0] = 0;
T>l[i] < length(s[p[i-1]]) - из-за 1. (*)
T>
Так, вот здесь хочется подробнее. Что значит "как далеко ее левый конец уходит в нашу строку"? Приведи пример, пожалуйста.
Здравствуйте, LCR, Вы писали:
T>>2. Очевидно, что S однозначно восстанавливается по N парам чисел T>>
T>>p[i] - какую строку брать i-й
T>>l[i] - как далеко ее левый конец уходит в нашу строку
T>>(i=0..N-1)
T>>l[0] = 0;
T>>l[i] < length(s[p[i-1]]) - из-за 1. (*)
T>>
LCR>Так, вот здесь хочется подробнее. Что значит "как далеко ее левый конец уходит в нашу строку"? Приведи пример, пожалуйста.
1. Делаем строку mystr, из символов которой можно получить любую из последовательности
2. Ищутся максимально привлекательные строки, которые в сумме (при удалении повторных символов) дают строку, из символов которых можно сделать mystr
это и есть ответ
под максимально привлекательными, я имею ввиду строки, которые:
1. Сокращают собой mystr на максимальное количетсво символов (назовем их maxstr)
2. Строки, которые в сложении дают строку короче maxstr, но уничтожают такоеже или большее количество символов в mystr
зы. пункт первый из определения привлекательных строк я сделал, а на второй забил, ибо лень ;-)
uses crt;
var
str: array [1..10] of string;
icnt,i,j,k: integer;
mystr: string;
noadd:boolean;
tmpstr:string;
tmpc:integer;
max, maxn, num:integer;
begin{ abc xyz abcx bcxyz cx z fgh yzfgh }
str[1]:='abcd';
str[2]:='xyz';
str[3]:='abcx';
str[4]:='bcxyz';
str[5]:='cx';
str[6]:='z';
str[7]:='fgh';
str[8]:='yzfgh';
icnt:=8;
for i:=1 to icnt do
for j:=1 to length(str[i]) do
begin
noadd := false;
for k:=1 to length(mystr) do
if mystr[k] = str[i][j] then noadd:=true;
if (not noadd) then mystr:=mystr+str[i][j];
end;
writeln('mystr is : ', mystr);
write('the result is : ');
repeat
max := -1;
for i:=1 to icnt do
begin
tmpstr:=mystr;
tmpc:=0;
for j:=1 to length(str[i]) do
for k:=1 to length(tmpstr) do
if (tmpstr[k] = str[i][j]) then
begin
delete(tmpstr,k,1);
inc(tmpc);
end;
if max < tmpc then
begin
max:= tmpc;
maxn:= i;
end;
end;
{udalyayem}for i:=1 to length(str[maxn]) do
for j:= 1 to length(mystr) do
if (mystr[j] = str[maxn][i]) then delete(mystr, j, 1);
write(str[maxn],'+');
until length(mystr) = 0;
writeln;
end.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Приветсвую, Олл!
PD>Решил и я предложить одну задачу. Возникла она у нас однажды, немного в PD>другой упаковке. Решить не смогли, и до сих пор решения я не знаю.
PD>Есть N строк разной длины. PD>Сформировать строку минимальной длины, в которой присутствовали бы все PD>эти N строк в качестве подстрок.
PD>Поясню на примерах PD>1. Строки abc xyz abcxyz PD>Очевидно, достаточно взять последнюю строку PD>2. Строки bc xy abcdwxyz PD>Тоже достаточно взять последнюю строку PD>3. Строки abcd xyz abcxyz PD>Придется конкатенировать первую и третью в любом порядке. PD>4. Строки abc xyz bcxy cxyz PD>Конкатенация первых двух даст результат abcxyz PD>5. Строки abc xyz abcx bcxyz cx z fgh yzfgh PD>Конкатенируем первые две и предпоследнюю.
На мой взгляд, делать надо так:
Составляем таблицу такого типа: что бывает после чего и потом задача сводится к поиску замкнутых цепочек.
Рассмотрим 4-й случай "abc xyz bcxy cxyz"
"abc": a->b b->c
"xyz": x->y y->z
"bcxy": c->x (остальное в таблице уже присутствует)
"cxyz":
ничего, все комбинации уже есть.
Остаётся теперь составить все возможные цепочки.
Ищем элементы, на которые никто не ссылается. У нас это будет только 'a'.
Получаем однозначный результат a->b->c->x->y->z.
PK Sly wrote: > > Остаётся теперь составить все возможные цепочки. > Ищем элементы, на которые никто не ссылается. У нас это будет только 'a'. > Получаем однозначный результат a->b->c->x->y->z.
Ты воспользовался тем, что в этом примере каждый может иметь в качестве
следующего только один-единственный символ.
bazh wrote: > > Вот набросал примерный код на паскале.
<skipped>
Я вот такую замену провел, а твоя программа ее замечать не хочет .
str[7]:='aaa';
--
With best regards,
Pavel Dvorkin
Posted via RSDN NNTP Server 1.7 "Bedlam"
With best regards
Pavel Dvorkin
Re: суммарная строка
От:
Аноним
Дата:
10.03.04 09:32
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Приветсвую, Олл!
PD>Решил и я предложить одну задачу. Возникла она у нас однажды, немного в PD>другой упаковке. Решить не смогли, и до сих пор решения я не знаю.
PD>Есть N строк разной длины. PD>Сформировать строку минимальной длины, в которой присутствовали бы все PD>эти N строк в качестве подстрок.
Копни в сторону суффиксных деревьев, используются для поиска вхождения образца в текст, представленный в виде такого дерева (в отл от известных алг-ов а-ля Кнута-Морриса-Пратта, обрабатывающих сам образец).
шаг1 — сформировать дерево для первой строки.
шаг2 — для очередной строки если она содержится в текущем дереве как поддерево — welcome to the club. Нет — добавляем ее туда.
шаг3 — результирующее дерево есть искомое.
Unknown wrote: > Копни в сторону суффиксных деревьев, используются для поиска вхождения образца в текст, представленный в виде такого дерева (в отл от известных алг-ов а-ля Кнута-Морриса-Пратта, обрабатывающих сам образец). > > шаг1 — сформировать дерево для первой строки.
А с чего ты решил, что первая строка туда обязательно войдет ?
abc
ab
bcd
и не нужна мне первая строка.
--
With best regards,
Pavel Dvorkin
Posted via RSDN NNTP Server 1.7 "Bedlam"
With best regards
Pavel Dvorkin
Re[3]: суммарная строка
От:
Аноним
Дата:
10.03.04 14:00
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:
>> шаг1 — сформировать дерево для первой строки.
PD>А с чего ты решил, что первая строка туда обязательно войдет ?
PD>abc PD>ab PD>bcd
PD>и не нужна мне первая строка.
1) Правильно ли я понял, что результатом приведенной последовательности должна быть
abcd?
2) на первом шаге будет дерево для первой строки, а не сама она. Сам процесс его построения _уже_ формирует решение для первой строки. — т.е. для ababa результатом будет ab.
Здравствуйте, Pavel Dvorkin, Вы писали:
PD>Приветсвую, Олл!
PD>Решил и я предложить одну задачу. Возникла она у нас однажды, немного в PD>другой упаковке. Решить не смогли, и до сих пор решения я не знаю.
PD>Есть N строк разной длины. PD>Сформировать строку минимальной длины, в которой присутствовали бы все PD>эти N строк в качестве подстрок.
Добрый день!
Вынужден Вас огорчить, но данная задача NP-трудна.
NP-трудность здесь означает, что на данный моемнт не известно не переборных ( по временной сложности) алгоритмов ее решения, и что врядли они существуют.
Для поиска приближенных решений (достаточно хороших) сообщеая, что Ваша задача является частных случаем задачи поиска максимального гамильтонова пути в графе.