Сортировка массивов парных номеров и удаление дубликатов или совпадений? - PullRequest
Новая
       4

Сортировка массивов парных номеров и удаление дубликатов или совпадений?

2 голосов
/ 10 августа 2010

Как мне отсортировать два массива координат в числовом порядке по начальным координатам, например, 

my @starts = (100,100,200,300,400,500,525);
my @ends   = (150,125,250,350,450,550,550);

но выберите самую большую разницу, если в списке начала или конца есть два совпадения? Э.Г. 

my @uniq_starts = (100,200,300,400,500);
my @unique_ends = (150,250,350,450,550);

Любая помощь с благодарностью!

Кроме того, как насчет того, чтобы списки были такими? 

my @starts = (100,125,200,300,400,500,525);
my @ends   = (150,175,250,350,450,550,550);

Это даст мне следующее значение между значениями: 

-25, 25, 50, 50, 50, -25

Мне понадобится следующий вывод: 

my @uniq_starts = (100,200,300,400,500);
my @unique_ends = (175,250,350,450,550);

Итак, мои промежуточные значения: 

25, 50, 50, 50

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

Ответы [ 3 ]

2 голосов
/ 10 августа 2010

Как насчет использования Set :: IntSpan ? 

use Set::IntSpan;

my @starts = (100,100,200,300,400,500,525);
my @ends = (150,125,250,350,450,550,550);
my @spec = map { "$starts[$_]-$ends[$_]" } 0..$#starts;
my $p = Set::IntSpan->new(@spec);
print "$p\n";
1 голос
/ 10 августа 2010

Используя Set :: IntSpan : 

use Set::IntSpan;

my @starts = (100,100,200,300,400,500,525);
my @ends   = (150,125,250,350,450,550,550);

my (@uniq_starts, @unique_ends);

for my $s (Set::IntSpan->new([map [$starts[$_], $ends[$_]], 0 .. $#starts])->spans) {
  push @uniq_starts, $s->[0];
  push @uniq_ends, $s->[1];
}

print join(",", @uniq_starts), "\n";
print join(",", @uniq_ends), "\n";

Или решение бедного человека: 

sub spans {
  my @s = sort {$a->[0] <=> $b->[0] or $a->[1] <=> $b->[1]} @_;
  my @res;
  while (@s > 1) {
    if ($s[0][1] >= $s[1][0]) {
      splice @s, 0, 2, [$s[0][0], $s[1][1]];
    } else {
      push @res, shift @s;
    }
  }
  push @res, @s;
  return @res;
}

my @starts = (100,100,200,300,400,500,525);
my @ends   = (150,125,250,350,450,550,550);

my (@uniq_starts, @unique_ends);

for my $s (spans(map [$starts[$_], $ends[$_]], 0 .. $#starts)) {
  push @uniq_starts, $s->[0];
  push @uniq_ends, $s->[1];
}

print join(",", @uniq_starts), "\n";
print join(",", @uniq_ends), "\n";

Вы можете проверить, что оно работает безупречно.

Более функциональный spans версия: 

sub spans {
  return spans_(sort {$a->[0] <=> $b->[0] or $a->[1] <=> $b->[1]} @_);
}

sub spans_ {
  if (@_ > 1 and $_[0][1] >= $_[1][0]) {
    splice @_, 0, 2, [$_[0][0], $_[1][1]];
    goto &spans_;
  } elsif (@_) {
    return shift, spans_(@_);
  } else {
    return;
  }
}

PS: Если кто-то думает, что Perl является лаконичным языком, сравните ту же функцию алгоритма spans в erlang.Я даже не знаю, как это будет выглядеть в APL или J: 

spans(L) -> spans_(lists:sort(L)).

spans_([{A, B}, {C, D}|T]) when B >= C ->
  spans_([{A, D}|T]);
spans_([H|T]) -> [H|spans_(T)];
spans_([]) -> [].
0 голосов
/ 10 августа 2010

Используйте некоторые преобразования списка: 

my @starts = (100,100,200,300,400,500,525);
my @ends   = (150,125,250,350,450,550,550);

my (%starts_seen, %ends_seen);
my @ar = sort { $a->[0] <=> $b->[0] }   # result in ascending sort order of @starts
         grep ! $starts_seen{$_->[0]}++,
         sort { $b->[0] <=> $a->[0] }   # descending sort b -> a
         grep ! $ends_seen{$_->[1]}++,
         sort { $b->[1] <=> $b->[1] }   # descending sort b -> a
         map  [ $starts[$_],$ends[$_] ],
         0 .. $#starts;

print "($_->[0],$_->[1]) " for @ar;

это приводит к: 

(100,150) (200,250) (300,350) (400,450) (500,550)

С уважением

rbo

Редактировать: измененный код для отраженияпорядок сортировки сортов

...