Поиск индексов последовательных элементов в массиве - PullRequest
Новая
       27

Поиск индексов последовательных элементов в массиве

2 голосов
/ 06 июня 2011

Итак, у меня есть массив my @a = (a,b,c,d,e,f)
И еще один массив my @b = (c,d,e)

Я хочу узнать, есть ли три последовательных элемента в @a, которые соответствуют элементам в @b.Затем, если они есть, я хочу получить индексы, в которых эти элементы живут.

Так что в приведенном выше случае я хочу получить массив, такой как (2,3,4).

Другой пример:
my @a = (1,2,3,4,5)
my @b = (2,3)

Выход: (1,2)

Ответы [ 2 ]

4 голосов
/ 06 июня 2011

Наивный подход: 

@A = 1..5;
@B = 2..3;
A_LOOP:
for my $a_index (0..$#A) {
    for my $b_index (0..$#B) {
        next A_LOOP unless $A[$a_index+$b_index] eq $B[$b_index];
    }
    @results = map $a_index+$_, 0..$#B;
    last;
}

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

2 голосов
/ 06 июня 2011

Вот общее решение.При этом используется функция 'all' из List :: MoreUtils, чтобы уменьшить сравнение до истинного / ложного результата, что немного упрощает логику.

Я помещаю ее в форму подчиненного элемента, которому вы передаетессылка на любые два массива.Первая ссылка на массив, переданная функции, должна быть надмножеством, а вторая ссылка на массив должна ссылаться на массив подмножеств.

Что мне нравится в этом решении, так это то, что оно может применяться к любым двум простым массивам (это ненапример, не ограничен поиском подмножества из двух элементов).Я выбрал сравнение строк элементов (eq), а не числовое (==).Таким образом, это работает, если у вас есть нечисловые элементы.Тем не менее, он будет оценивать '00' и '0' как неравные (потому что они не являются одной и той же строкой).Если вы предпочитаете числовое сравнение, просто найдите 'eq' и измените его на '=='.

Вот код: 

use 5.010_001;
use strict;
use warnings;

use List::MoreUtils qw/all/;

my @array_a = qw/1 2 3 4 5/;
my @array_b = qw/2 3/;

{
    local $, = " ";
    my( @results ) = find_group( \@array_a, \@array_b );
    say "Success at ", @results if @results;
}


sub find_group {
    my( $array_1, $array_2 ) = @_;
    foreach my $array_1_idx ( 0 .. $#{$array_1} ) {
        my $moving_idx = $array_1_idx;
        return $array_1_idx .. ( $moving_idx - 1 ) if 
            all { $_ eq $array_1->[$moving_idx++] } @{$array_2};
    }
    return ();
}
...