Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Найти самую длинную последовательность

Автор: tishaishii 5.3.2006, 13:59

Матрица вида:

Код

[
[[1], [3], [3]],
[[2], [1], [1]],
[[3, 4], [2, 4, 5], [2, 4]],
[[1], [3], [3]]
]

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

Запутал? Вот ответы для приведённой матрицы:

Код


[[1], [3], [3]],
[[3, 4], [2,4,5], [2,4]]

Код


[[2], [1], [1]],
[[3, 4], [2,4,5], [2,4]]

Нужен алгоритм.

Автор: maxim1000 5.3.2006, 14:19

если

Цитата(tishaishii @ 5.3.2006, 12:59

)

[
[[1], [3], [3]],
[[2], [1], [1]],
[[3, 4], [2, 4, 5], [2, 4]],
[[1], [3], [3]]
]

последовательность строк, то

Цитата(tishaishii @ 5.3.2006, 12:59

)

[[3, 4], [2, 4, 5], [2, 4]]

- строка,
а

Цитата(tishaishii @ 5.3.2006, 12:59

)

[2, 4, 5]

- ее элемент, т.е. он не число, а набор чисел
как такие элементы сравниваются друг с другом?

Автор: tishaishii 5.3.2006, 14:23

Давай, попроще.
Есть список вида:

Код

a=[10, 1, 5, 3, 9, 4]

Надо найти самые длинные последовательности элементов, таких, что a[i+1]<a[i].
Ответ:

Код

v1=[1, 5, 9]
v2=[1, 3, 9]
v3=[1, 3, 4]

Другие варианты короче, а эти самые длинные.

Вот нужен алгоритм.

Автор: maxim1000 5.3.2006, 15:03

хм... вроде помню такую тему на форуме, а не нашел
в общем, схема обычная - динамическое программирование
создаем еще один массив L такой же длины из целых чисел
в i-ю ячейку пишем максимальную длину возрастающей подпоследовательности, которая заканчивается на i-м числе
как это делается:
для чисел, перед которыми нет меньших чисел, просто пишем 1
если есть - выбираем из предшествующих меньших чисел то, для которого L[j]=max и добавляем к нему 1
пример:
a=10, 1, 5, 3, 9, 4
L[0]=1//перед ним вообще нету чисел
L[1]=1//10 не меньше, потому не подходит
L[2]=L[1]+1=2
L[3]=L[1]+1=2
L[4]=L[2]+1=L[3]+1=3 (оба варианта подходят)
L[5]=L[3]+1=3

в конце просто выбираем максимальное значение из L[i]
чтобы упростить поиск самой последовательности (а не только ее длины), можно сделать еще один массив, в котором для каждого элемента записывать, какой элемент в оптимальной последовательности ему предшествует...

Автор: tishaishii 5.3.2006, 15:23

Теперь я хммм.. буду разбираться.
Вот бы пример на каком-нибудь языке программирования вроде Pascal, C, или вообще, не важно на каком.
Добавлено @ 15:27
Я вообще думал, получаются деревья "кто кого меньше", и как-то с учётом последовательности. Потом происходит поиск самых длинных путей в деревьях, а потом опять возвращаемся к той же задаче, но уже с меньшим количество членов в списке и так, пока не дойдём до точки.

Пример хочется.

Автор: tishaishii 5.3.2006, 15:47

Автор: maxim1000 5.3.2006, 15:57

ну, например, так:

Код


void f(int *array,int length)
{
  int *L=new int[length];//массив L, который упоминался в алгоритме
  int *from=new int[length];//from[i] - элемент оптимальной
                            // последовательности, идущий перед i-м
  for(int c=0;c<length;++c)
  {
    int best=-1;
    int max=0;
    for(int i=0;i<c;++i)
      if(array[i]<array[c] && max<L[i])
      {
        best=i;
        max=L[i];
      }
    L[c]=max+1;
    from[c]=best;
  }
  {
    //находим конец самой длинной последовательности
    int last=0;
    for(int c=1;c<length;++c)
      if(L[c]>L[last])
        last=c;
    //выводим последовательность, правда, в обратном порядке,
    //но это - мелочи...
    while(last>=0)
    {
      Print(i);
      last=from[last];
    }
  }
  delete[] L;
  delete[] from;
}

Автор: maxim1000 5.3.2006, 16:23

Цитата(tishaishii @ 5.3.2006, 14:23

)

Я вообще думал, получаются деревья "кто кого меньше"

так тоже можно, получится рекурсия
я сначала и думал написать этот вариант, а потом представить тот, который сейчас, как оптимизацию (обычно, так и получается), но конечный мне даже проще показался

а почему он быстрее - вот ответ:
наше дерево будет необычным - в одну и ту же вершину можно будет добраться несколькими путями
теперь посмотрим, к чему это приведет:
возьмем такой пример
a=10, 2, 6, 1, 5, 3, 9, 4, 6, 7
и посмотрим, какие подпоследовательности есть вообще:
2,5,9
2,5,6,7
2,5,7
1,5,9
1,5,6,7
1,5,7
5,9
5,6,7
5,7
(для примера я выделил только те, которые содержат 5)
можно все их просмотреть и найти самую длинную - по сути, к этому и сводится рекурсивный способ
если мы начнем просматривать последовательности вручную, мы заметим некоторую повторяемость:
слева от 5-ки может стоять 1,2 или пусто
справа от5-ки может стоять 9, 6-7 или 7
они комбинируются всеми возможными способами (т.е. 3*3=9 способов)
и длина последовательности может быть посчитана как (длина левой части)+1+(длина правой части)
т.е. левая часть и правая абсолютно независимы и максимумы можно искать независимо
в некотором приближении это называется свойством марковости (от процессов Маркова)
обычно, это свойство создает хорошие возможности для оптимизации
в нашем случае вместо того, чтобы перебирать 3*3 вариантов можно пойти другим путем:
сначала возьмем самую длинную девую часть (переберем 3 варианта и получим, например, 2)
потом - самую длинную правую часть - тоже 3 варианта - 6,7
а потом просто соединим все это: 2,5,6,7
(именно на этом и построен алгоритм, приведенный выше - до каждого элемента считаем без забегания вперед - т.е. оптимальную левую часть)
что мы получили - вместо 9 вариантов 6
если бы было по 10 вариантов левой и правой частей, получили бы 20 переборов вместо 100
в общем, сделали декомпозицию задач, когда вместо того, чтобы перемножаться сложности складываются, что получается иногда НАМНОГО быстрее...

Автор: tishaishii 5.3.2006, 21:08

Ошибка между 29 и 30й строкой в листинге.
Вообще-то мне нужно найти все максимально-длинные последовательности.
А некоторые я могу найти и так:

Код


my@a=(10, 1, 5, 3, 9, 4);
my@res;

for(my$i=0; $i<@a; $i++) {
    $res[$i]=[$a[$i]];
    last if $i==$#a;
    for(my$j=$i+1; $j<@a; $j++) {
        push @{$res[$i]}, $a[$j] if $res[$i][-1]<$a[$j];
    }
}

Но вот интересно найти все (для моего примера их 3).

Автор: tishaishii 5.3.2006, 23:11

Вот примерно чего я хотел-то этим добиться:

Код

package XLCS;

sub find {
    my($self, $cmp, $array)=(shift, shift, shift);
    my(@L, @from, $best, $max);
    for(my$c=0; $c<@$array; $c++) {
        $best=-1;
        $max=0;
        for(my$i=0; $i<$c; $i++) {
            next unless $cmp->(@$array[$i, $c]) && $max<$L[$i];
            $best=$i;
            $max=$L[$i];
        }
        $L[$c]=$max+1;
        $from[$c]=$best;
    }
    my$last=0;
    my@res;
    for(my$c=1; $c<@$array; $c++) {
        $last=$c if $L[$c]>$L[$last]
    }

    while($last>=0) {
        push @res, $last;
        $last=$from[$last];
    }
    +@res
}

sub trim {
    my($self, $words)=(shift, shift);
    my($j, $cword);
    foreach(my$i=0; $i<@$words; $i++) {
        $cword=quotemeta $$words[$i];
        foreach($j=0; $j<@$words; $j++) {
            $$words[$j]=~s{[^$cword]}{}gis unless $i==$j
        }
    }
    +$words
}

sub transpose {
    my($self, $matrix)=(shift, shift);
    my($cols, $len, $i, $j, @result)=-1;

    for($i=0; $i<@$matrix; $i++) {
        $len=scalar @{$$matrix[$i]};
        $cols=$len if $cols<$len;
    }

    for($i=0; $i<$cols; $i++) {
        for($j=0; $j<@{$$matrix[$i]}; $j++) {
            $result[$j][$i]=$$matrix[$i][$j];
        }
    }

    +\@result
}

sub array_le {
    my($a, $b)=(shift, shift);
    my($i, $j, $k, $n, $found);
    l0:for($i=0; $i<@$a; $i++) {
        for($j=0; $j<@$b; $j++) {
            $found;
            for($k=0; $k<@{$a->[$i]}; $k++) {
                for($n=0; $n<@{$b->[$j]}; $n++) {
                    next unless $a->[$i][$k]<$b->[$j][$n];
                    $found=1;
                    next l0
                }
                return undef
            }
        }
    }
    +1
}

sub build_rx {
    my($self, $words)=(shift, shift);
    my($i, $j, $k, $cword, @matrix, $wl, $letter);

    $self->trim($words);

    my@letter=map quotemeta, shift(@$words)=~m{(.)}gos;

    for($i=0; $i<@$words; $i++) {
        $cword=\$$words[$i];
        $wl=length $$cword;
        $matrix[$i]=[];
        for($j=0; $j<$wl && $j<@letter; $j++) {
            $matrix[$i][$j]=[];
            pos($$cword)=0;
            push @{$matrix[$i][$j]}, pos $$cword while $$cword=~m{$letter[$j]}gcsi;
        }
    }

    my@res=$self->find(\&array_le, $self->transpose(\@matrix));

    my@result=\$letter[$res[-1]];
    for(my$i=$#res-1; $i>=0; $i--) {
        push @result, '(.*?)' if $res[$i]-$res[$i+1]>1;
        push @result, \$letter[$res[$i]]
    }
    +\@result
}

sub rx2str {
    my$res=join undef, map{
        if(ref) {
            $$_=~s{\\[ \r\t\n]+}{\\s+}gos;
            +$$_
        } else {
            +$_
        }
    }@{$_[1]};
    $res=~s{(?:\\s\+)+}{\\s+}go;
    +$res
}

package main;

my@words=(<<'.', <<'.', <<'.', <<'.');

sub rx2str {
    join undef, map{
        if(ref) {
            $$_=~s{\\[ ntr]}{\\s+}gos;
            +$$_
        } else {
            +$_
        }
    }@{$_[1]}
}

.
    $$_=~s{\\[ \r\t\n]}{\\s+}gos;
            +$$_
        } else {
            +$_
.
                
package main;

my@words=(<<'.', <<'.', <<'.', <<'.');

sub rx2str {
    join undef, map{
.
    
sub rx2str {
    join undef, map{
.
my$rx=XLCS->build_rx(\@words);
print XLCS->rx2str($rx);

Вывод:

Код

\s+s\s+(.*?)s(.*?)\s+\{\s+o(.*?)\s+(.*?)e\s+\{\s+re\s+\{\s+

Ну ещё надо оптимизировать, но цель уже почти достигнута.
Добавлено @ 23:13
Я раньше пытался пользоваться для этих целей алгоритмом LCS, но сумел его приладить только для работы с 2мя строками. Пришлось придумать свой алгоритм.
Добавлено @ 23:15
Вот этот алгоритм (вложение).

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

Автор: maxim1000 6.3.2006, 03:20

Цитата(tishaishii @ 5.3.2006, 20:08

)

Ошибка между 29 и 30й строкой в листинге.
Вообще-то мне нужно найти все максимально-длинные последовательности.

ну так это совсем несложно:
упраздняем массив from (в принципе, можно было бы сделать его массивом массивов, но можно и без этого)
а дальше выводим так (функция принимает на вход массив L, который был вычислен):

Код


void PrintSequences(int *a,int *L,int length,int *tail,int taillength,int last)
{
  if(L[last]==1)//достигли конца (т.е.начала последовательности)
  {//просто выводим последовательность
    for(int c=0;c<length;++c)
      Print(tail[c]);
  }
  else
  {
    //находим всевозможные продолжения максимальной
    //последовательности, добавляем их в хвост по очереди
    //и вызываем эту же функцию
    int max=0;
    for(int c=0;c<last;++c)//находим самую большую длину
      if(a[c]<a[last] && max<L[c])
        max=L[c];
    //вызываем функцию для всевозможных последовательностей
    //этой длины
    for(int c=0;c<last;++c)
      if(a[c]<a[last] && max==L[c])
      {
        tail[taillength]=a[c];
        PrintSequences(a,L,length,tail,taillength+1,c);
      }
  }
}
void PrintAllMaxSequences(int *a,int *L,int length)
{//выводит все максимальные последовательности
  int *tail=new int[length];
  PrintSequences(L,length,tail,0,length);
}

а вот с Perl'ом у меня, к сожалению, проблемы smile

Автор: Dov 7.3.2006, 15:28

Цитата(tishaishii @ 5.3.2006, 13:23

)

Есть список вида:
Без подсветки
1: a=[10, 1, 5, 3, 9, 4]

Надо найти самые длинные последовательности элементов, таких, что a[i+1]<a[i].
Ответ:
Без подсветки
1: v1=[1, 5, 9]
2: v2=[1, 3, 9]
3: v3=[1, 3, 4]

Другие варианты короче, а эти самые длинные.

1. Видимо здесь a[i+1]<a[i] имеется ввиду a[i+1]>a[i].
2.Лирическое отступление:

Цитата

Препод : Что такое возрастающая последовательность ?
Студентка : Это когда каждый следующий член больше предыдущего.
Препод : Об этом можете только мечтать.

Это я к тому, что в этом примере возрастающая последовательность это:

Код

1, 5

Код

3, 9

т.е. последовательность подряд идущих по возрастанию элементов. Короче, нужно разобраться. smile

Автор: Dov 7.3.2006, 15:50

Из учебника по мат.анализу

Цитата

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

И ещё добавлю, что в такой последовательности должно быть более одного элемента.

Автор: tishaishii 7.3.2006, 22:06

Прошу, не надо запутывать.

Автор: Dov 7.3.2006, 23:20

Цитата(tishaishii @ 7.3.2006, 21:06

)

Прошу, не надо запутывать.

tishaishii, я хочу тебе помочь, а ты мне рот затыкаешь. Посмотри ещё раз на свой пример:

Код

Надо найти самые длинные последовательности элементов, таких, что a[i+1]<a[i].
Ответ:
1: v1=[1, 5, 9] 
2: v2=[1, 3, 9] 
3: v3=[1, 3, 4]

a[i+1]<a[i] - это значит, что каждый последующий элемент меньше текущего, а в твоём ответе всё наоборот. То же касается и этого

Код

 1: a=[10, 1, 5, 3, 9, 4]

. Говоришь, что a[i+1]<a[i], т.е. каждый последующий элемент , а сам прыгаешь через один.

Цитата

v3=[10, 1, 5, 3, 9, 4]

Так кто из нас запутывает? smile

Автор: maxim1000 8.3.2006, 01:56

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

P.S.
действительно были некоторые неточности с примерами, на них указали и хватит об этом

Автор: Dov 8.3.2006, 02:16

Всё, проехали. Подождём что автор скажет. smile

Автор: tishaishii 11.3.2006, 23:18

А что, дайте тому, кто больше всех работал "+". Мне нравится. У менья правов нету.