Сначала я собрал бы все отдельные точки (начало и конец каждой локации), отсортировал их и сохранил в списке. В вашем случае это будет:
1,180,193,329,407,651,684,720.
Для каждого интервала в этом списке выясните, сколько сегментов перекрывают его. В вашем случае это будет:
1, 180 -> 1
180, 193 -> 2
193, 329 -> 1
329, 407 -> 2
407, 651 -> 1
651, 684 -> 2
684, 720 -> 1
и зацикливать, у каких сегментов больше 1 (в данном случае их 3). Таким образом, общее количество случаев составляет 2 x 2 x 2 = 8 решений (вы можете выбрать только один сегмент обработки нескольких интервалов в решении).
мы нашли 2, 2, 2 (или 2, 3, 4). Держите их в массиве и начинайте с последнего. Уменьшайте его, пока не достигнете 0. Когда вы достигнете 1, уменьшите предыдущее число и установите для первого числа начальное значение минус 1.
Предположим, что мы пронумеровали начальные сегменты: (в данном случае 1,2,3,4,5,6). Перекрывающиеся сегменты будут иметь следующие сегменты [1,2], [2,3], [3,4]. Итак, у нас есть 3 перекрывающихся сегмента. Теперь мы начинаем рекурсивный процесс выбора / исключения:
На каждом этапе мы смотрим на перекрывающийся сегмент, который имеет несколько сегментов. Мы повторяем выбор и для каждого выбора делаем две вещи: исключаем из каждого последующего перекрывающегося сегмента сегменты, которые мы не выбрали сейчас, и устанавливаем текущий выбор сегмента в каждом последующем перекрывающемся сегменте, у которого этот выбор является возможным. Каждый сегмент, который становится неперекрывающимся, будет рассматриваться как новый выбор. Ищите следующий множественный выбор и повторяйте. Как только мы не можем найти выбор, у нас есть частичное решение. Нам нужно добавить к нему сегменты, которые не участвуют ни в каком перекрытии. Распечатай это.
В этом случае это будет выглядеть так: Первый шаг:
we are here [1,2], [2,3], [3,4]:
chose 1 -> // eliminate 2 from rest and force 1 (3 is a single choice so we do the same)
[1], [3], [3] -> [1, 3] solution
chose 2 -> // eliminate 1 from the rest and force 2 (2 single choice so we do the same).
[2], [2], [4] -> [2, 4] solution
Это должно работать правильно.
Теперь код, реализующий это (это не самый красивый Perl-код, который я предполагаю, но на самом деле я не Perl-парень):
#!/bin/perl
use strict;
use warnings;
use 5.010;
use Data::Dumper;
my $locs = {
loc_1 => {
start => 1,
end => 193,
},
loc_2 => {
start => 180,
end => 407,
},
loc_3 => {
start => 329,
end => 684,
},
loc_4 => {
start => 651,
end => 720,
}
};
my (%starts, %ends);
map {
my ($start, $end) = ($locs->{$_}->{start}, $locs->{$_}->{end});
push @{ $starts{$start} }, $_;
push @{ $ends{$end} }, $_;
} keys %$locs;
my @overlaps, my %tmp;
map {
map { $tmp{$_} = 1 } @{$starts{$_}};
map { delete $tmp{$_} } @{$ends{$_}};
my @segs = keys %tmp;
push @overlaps, \@segs if 1 < @segs
} sort (keys %starts, keys %ends);
sub parse_non_overlapping {
my ($array,$pos)=($_[0], $_[1]);
my @node = @{$array->[$pos]};
foreach my $value ( @node ) {
my @work = map { [@$_] } @$array;
$work[$pos] = [ $value ];
my ($removed, $forced) = ( {}, {$value => 1});
map { $removed->{$_} = 1 if $_ ne $value } @node;
my ($i, $new_pos) = (0, -1);
for ( $i = $pos + 1; $i <= $#work; $i++ ) {
$_ = $work[$i];
#apply map
@$_ = grep { not defined($removed->{$_}) } @$_;
if ( $#$_ == 0 ) { $forced->{@$_[0]} = 1 }
#apply force
my @tmp = grep { defined $forced->{$_} } @$_;
if ( $#tmp == 0 ) {
map { $removed->{$_} = 1 if $tmp[0] ne $_ } @$_;
@$_ = @tmp;
}
if ( $#$_ > 0 && $new_pos == -1 ) {
$new_pos = $i;
}
$work[$i] = $_;
}
if ( $new_pos != -1 ) {
parse_non_overlapping(\@work, $new_pos);
} else {
print Dumper \@work
# @work has the partial solution minux completely non overlapping segments.
}
}
}
parse_non_overlapping(\@overlaps, 0);