суммарная строка
От: Pavel Dvorkin Россия  
Дата: 02.03.04 06:47
Оценка:
Приветсвую, Олл!

Решил и я предложить одну задачу. Возникла она у нас однажды, немного в
другой упаковке. Решить не смогли, и до сих пор решения я не знаю.

Есть N строк разной длины.
Сформировать строку минимальной длины, в которой присутствовали бы все
эти N строк в качестве подстрок.

Поясню на примерах

1. Строки abc xyz abcxyz

Очевидно, достаточно взять последнюю строку

2. Строки bc xy abcdwxyz

Тоже достаточно взять последнюю строку

3. Строки abcd xyz abcxyz

Придется конкатенировать первую и третью в любом порядке.

4. Строки abc xyz bcxy cxyz

Конкатенация первых двух даст результат abcxyz

5. Строки abc xyz abcx bcxyz cx z fgh yzfgh

Конкатенируем первые две и предпоследнюю.


--
With best regards,
Pavel Dvorkin
Posted via RSDN NNTP Server 1.7 "Bedlam"
With best regards
Pavel Dvorkin
Re: суммарная строка
От: Курилка Россия http://kirya.narod.ru/
Дата: 02.03.04 06:59
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Приветсвую, Олл!


PD>Решил и я предложить одну задачу. Возникла она у нас однажды, немного в

PD>другой упаковке. Решить не смогли, и до сих пор решения я не знаю.

Так вы её решили хоть как-нибудь? Типа тупым перебором?

PD>Есть N строк разной длины.

PD>Сформировать строку минимальной длины, в которой присутствовали бы все
PD>эти N строк в качестве подстрок.

Самое примитивное — сложить все эти N строк, затем убирать более однократные вхождения. Тут можно построить лес вхождения строк в строки, т.е. напр. для строк аб и абц будет достаточно вхождения строки абц. Но на этом останавливаться глупо, т.к. ещё результат может зависеть от порядка конкатенации...
Примерно такие пока первые мысли...
Re: суммарная строка
От: Tan4ik Россия  
Дата: 02.03.04 07:24
Оценка: 5 (1)
Здравствуйте, 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. Я думаю, такая задача хорошо изучена. Дальше предлагается решать методом ветвей и границ или генетическим алгоритмом.
---
С уважением,
Лазарев Андрей
Re[2]: суммарная строка
От: Pavel Dvorkin Россия  
Дата: 02.03.04 07:43
Оценка:
Привет!

Курилка wrote:
>
> Здравствуйте, Pavel Dvorkin, Вы писали:
>
> PD>Приветсвую, Олл!
>
> PD>Решил и я предложить одну задачу. Возникла она у нас однажды, немного в
> PD>другой упаковке. Решить не смогли, и до сих пор решения я не знаю.
>
> Так вы её решили хоть как-нибудь? Типа тупым перебором?

Нет. Изменили алгоритм, так, что решать не потребовалось.

>

> PD>Есть N строк разной длины.
> PD>Сформировать строку минимальной длины, в которой присутствовали бы все
> PD>эти N строк в качестве подстрок.
>
> Самое примитивное — сложить все эти N строк

Во всех комбинациях ? n! ?


--
With best regards,
Pavel Dvorkin
Posted via RSDN NNTP Server 1.7 "Bedlam"
With best regards
Pavel Dvorkin
Re[3]: суммарная строка
От: Курилка Россия http://kirya.narod.ru/
Дата: 02.03.04 09:09
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Привет!


PD>Курилка wrote:

>>
>>
>> Самое примитивное — сложить все эти N строк

PD>Во всех комбинациях ? n! ?


Да нет — это уже будет лишнее если все сложить, то комбинации тут никчему, хотя если тупым перебором и поиском минимума, то будет так, хотя можно проверять вхождение сложив k строк (т.е. < n) и если в результате какую-то из строк можно выкинуть, то она уже не будет включаться и увеличивать число комбинаций, хотя я не думаю, что это радикально уменьшит число комбинаций...
Re[2]: суммарная строка
От: Кодт Россия  
Дата: 02.03.04 10:00
Оценка: 4 (1)
Здравствуйте, 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,
при этом смежность будет соблюдена, но ни одну из строк мы не породим.

Я не знаю, как навязать правильные пути, за исключением дублирования состояний (как это делается при преобразовании НДКА в ДКА). Но тогда встанет вопрос об избыточности. То есть, даже найдя гамильтонов путь, мы необязательно получим минимальное решение.
Хотя... если после детерминирования КА мы его ещё и минимизируем...
Перекуём баги на фичи!
Re[3]: суммарная строка
От: Pavel Dvorkin Россия  
Дата: 02.03.04 12:13
Оценка:
Привет!

Кодт wrote:
>
> Здравствуйте, Tan4ik, Вы писали:
>
> T>Для N>2 боюсь все намного мрачнее.
>
> Без особой потери общности, мы можем представить строки цепочками "наименьших общих слагаемых".
> Например, abcde, cdefg, efghi = (ab)(cd)(e) (cd)(e)(f)(g) (e)(f)(g)(hi)

Алгортим ? И какой у него будет временная зависимость ?

--
With best regards,
Pavel Dvorkin
Posted via RSDN NNTP Server 1.7 "Bedlam"
With best regards
Pavel Dvorkin
Re[2]: суммарная строка
От: LCR Россия lj://_lcr_
Дата: 04.03.04 11:15
Оценка:
Здравствуйте, Tan4ik, Вы писали:

T>Пусть у нас

T>
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>


Так, вот здесь хочется подробнее. Что значит "как далеко ее левый конец уходит в нашу строку"? Приведи пример, пожалуйста.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
Re[3]: суммарная строка
От: Tan4ik Россия  
Дата: 05.03.04 07:39
Оценка:
Здравствуйте, 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>Так, вот здесь хочется подробнее. Что значит "как далеко ее левый конец уходит в нашу строку"? Приведи пример, пожалуйста.


строки

cabab - 0
ababd - 1
ababab - 2


Несколько примеров
p = 0,1,2
l = 0,0,0
S = cababababdababab


p = 0,1,2
l = 0,2,0
S = cabababdababab


p = 0,1,2
l = 0,4,0
S = cababdababab


p = 0,2,1
l = 0,0,0
S = cabababababababd


p = 0,2,1
l = 0,2,2
S = cabababababd


оптимальный вариант
p = 0,2,1
l = 0,4,4
S = cabababd
---
С уважением,
Лазарев Андрей
Re: суммарная строка
От: bazh  
Дата: 06.03.04 00:10
Оценка:
Вот набросал примерный код на паскале.

Идея такова:

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.
Re: суммарная строка
От: PK Sly http://www.vocord.ru/
Дата: 09.03.04 09:16
Оценка:
Здравствуйте, 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.
VAX/VMS rulez!
Re[2]: суммарная строка
От: Pavel Dvorkin Россия  
Дата: 09.03.04 11:56
Оценка:
Привет!

PK Sly wrote:
>
> Остаётся теперь составить все возможные цепочки.
> Ищем элементы, на которые никто не ссылается. У нас это будет только 'a'.
> Получаем однозначный результат a->b->c->x->y->z.

Ты воспользовался тем, что в этом примере каждый может иметь в качестве
следующего только один-единственный символ.

Попробуй

abc xyz bcxy cxyz ayx bzx

И у тебч вместо списка будет дерево или граф.



--
With best regards,
Pavel Dvorkin
Posted via RSDN NNTP Server 1.7 "Bedlam"
With best regards
Pavel Dvorkin
Re[2]: суммарная строка
От: Pavel Dvorkin Россия  
Дата: 09.03.04 12:04
Оценка:
Привет!

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 — результирующее дерево есть искомое.
Re[2]: суммарная строка
От: Pavel Dvorkin Россия  
Дата: 10.03.04 12:08
Оценка:
Привет!

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.
Re: суммарная строка
От: Grelkin  
Дата: 19.03.04 06:56
Оценка:
Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Приветсвую, Олл!


PD>Решил и я предложить одну задачу. Возникла она у нас однажды, немного в

PD>другой упаковке. Решить не смогли, и до сих пор решения я не знаю.

PD>Есть N строк разной длины.

PD>Сформировать строку минимальной длины, в которой присутствовали бы все
PD>эти N строк в качестве подстрок.

Я вот что-то придумал....
зацените :
http://www.cdilab.com/task.phtml
Re[2]: суммарная строка
От: Grelkin  
Дата: 19.03.04 07:42
Оценка:
Здравствуйте, Grelkin, Вы писали:

G>Я вот что-то придумал....

G>зацените :
G>http://www.cdilab.com/task.phtml

Нда-а-а...
можете не смотреть )))

Требует некоторой доработки...
Re: суммарная строка
От: alebab Россия http://ababurin.narod.ru
Дата: 19.03.04 09:06
Оценка:
Добрый день!
Вынужден Вас огорчить, но данная задача NP-трудна.

NP-трудность здесь означает, что на данный моемнт не известно не переборных ( по временной сложности) алгоритмов ее решения, и что врядли они существуют.

Для поиска приближенных решений (достаточно хороших) сообщеая, что Ваша задача является частных случаем задачи поиска максимального гамильтонова пути в графе.

С уважением, Алексей
Re[2]: суммарная строка
От: Tan4ik Россия  
Дата: 19.03.04 09:37
Оценка:
Здравствуйте, alebab, Вы писали:

A>Добрый день!

A>Вынужден Вас огорчить, но данная задача NP-трудна.

Я бы сказал NP-полна. NP-трудности я в ней не вижу.
---
С уважением,
Лазарев Андрей
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.