間隔のリストを重複しないサブ間隔に分割しようとしています。たとえば、私の入力が
[1,5],[4,9],[6,12],[11,17]
出力を
[1,4], [4,5], [5,6], [6,9], [9,11], [11,12], [12,17]
出力を、元の間隔のリストと同じユニオンを持つ間隔のリストにする必要がありますが、複数の異なるサブ間隔の重複するサブ間隔はすべて異なる間隔になります。
私の最初の考えは、すべての間隔を最初の要素でソートし、重複がある場合は新しい間隔を作成する必要があるということですが、これを機能させるのに苦労しています。これは多くの区間問題とは本質的に異なるように思われるので、どんな提案でも素晴らしいでしょう!
@ user2566092 の回答に触発されて、別の方法を思いつきました。
まず、「穴」の例を次に示します。
[1.3]
[6..9]
[8...12]
これにより、次のようになります。
[1.3]
[6,8]
[8,9]
[9..12]
これを取得するには、最初に一意のエンドポイントのセットを決定し、順序付けます。
1, 3, 6, 8, 9, 12
次に、連続するペアによって形成されるすべての可能なサブ区間 AB を反復します。
[1,3]
[3,6]
[6,8]
[8,9]
[9,12]
各間隔 AB について、AB と交差する元の間隔 XY を見つけようとします。これは、次の場合に当てはまります。
(B > X) && (Y > A)
例えば：
[A=1, B=3] is included because of [X=1, Y=3]
[A=3, B=6] is excluded, interval [X=1, Y=3] is excluded because Y=A,
the other original intervals are excluded because B<X
編集: これは Java の実装です。
import java.util.*;
public class Main {
public static void main(final String[] args) {
determineSubIntervals(new Interval[] { new Interval(1, 5), new Interval(4, 9), new Interval(6, 12), new Interval(11, 17) });
determineSubIntervals(new Interval[] { new Interval(1, 3), new Interval(6, 9), new Interval(8, 12) });
}
private static List<Interval> determineSubIntervals(final Interval[] originals) {
System.out.println("Originals: " + Arrays.toString(originals));
final Set<Integer> endpoints = extractOrderedUniqueEndpoints(originals);
final List<Interval> candidates = createConsecutiveIntervals(endpoints);
final List<Interval> subIntervals = removeDisjunct(candidates, originals);
System.out.println("Sub intervals: " + subIntervals);
return subIntervals;
}
private static Set<Integer> extractOrderedUniqueEndpoints(final Interval[] intervals) {
final Set<Integer> endpoints = new TreeSet<Integer>();
for (final Interval interval : intervals) {
endpoints.add(interval.getStart());
endpoints.add(interval.getEnd());
}
return endpoints;
}
private static List<Interval> createConsecutiveIntervals(final Set<Integer> endpoints) {
final List<Interval> intervals = new ArrayList<Interval>();
final Iterator<Integer> it = endpoints.iterator();
Integer start = null;
while (it.hasNext()) {
final Integer end = it.next();
if (start != null) {
final Interval candidate = new Interval(start, end);
intervals.add(candidate);
}
start = end;
}
return intervals;
}
private static List<Interval> removeDisjunct(final List<Interval> candidates, final Interval[] intervals) {
final Iterator<Interval> it = candidates.iterator();
while (it.hasNext()) {
final Interval candidate = it.next();
if (isDisjunct(candidate, intervals)) {
it.remove();
}
}
return candidates;
}
private static boolean isDisjunct(final Interval candidate, final Interval[] intervals) {
final int a = candidate.getStart();
final int b = candidate.getEnd();
for (final Interval interval : intervals) {
final int x = interval.getStart();
final int y = interval.getEnd();
if ((b > x) && (y > a)) {
return false;
}
}
return true;
}
}
間隔クラス:
public class Interval {
private final int start;
private final int end;
public Interval(final int start, final int end) {
this.start = start;
this.end = end;
}
public int getStart() {
return start;
}
public int getEnd() {
return end;
}
@Override
public String toString() {
return String.format("[%s,%s]", start, end);
}
}
出力：
Originals: [[1,5], [4,9], [6,12], [11,17]]
Sub intervals: [[1,4], [4,5], [5,6], [6,9], [9,11], [11,12], [12,17]]
Originals: [[1,3], [6,9], [8,12]]
Sub intervals: [[1,3], [6,8], [8,9], [9,12]]
下の図は、入力と目的の出力を示しています。5 つの間隔があります (穴のケースをカバーするために、元の間隔に 1 つ追加しました)。
これらの間隔 (ラベル 1..5) を重複しないサブ間隔 (ラベル A..I) に分解します。したがって、たとえば、間隔 1はサブ間隔 Aと B[1,5]に分解できます。[1,4][4,5]
まず、データを設定します。次に、一意のエンドポイントを取得して並べ替え、隣接する数値から新しい間隔を作成します。
# setup data and start decomposition
input <- c(1,5,4,9,6,12,11,17, 18,20)
intervals <- data.table(matrix(input,ncol=2,byrow=TRUE))
endpoints <- sort(unique(input))
decomp <- data.table(matrix(c(head(endpoints, -1), endpoints[-1]), ncol=2))
最後に、これらの新しいサブインターバルをオリジナルに結合する必要があります。これは、穴を除外するために使用できます。また、どのプライマリ インターバルを構築するためにどのサブ インターバルが必要かを識別するためにも使用できます。ここでは、二分探索ベースの区間結合が使用されます (foverlaps)。
# align decomposition to segs
intervals[, intid := seq_len(length(input)/2)]
decomp[, subid := LETTERS[seq_len(length(endpoints)-1)]]
setkeyv(decomp, c('V1','V2'))
setkeyv(intervals, c('V1','V2'))
relations <- foverlaps(decomp, intervals, type='within', nomatch=0)
多対多の関係テーブルから、どの間隔 ID (intid) がどのサブ間隔 ID (subid) に一致するかがわかります。たとえば、intid 1 は subid A および subid B に一致します。サブインターバル H はホールであるため、このテーブルには存在しないことに注意してください。
> relations
V1 V2 intid i.V1 i.V2 subid
1: 1 5 1 1 4 A
2: 1 5 1 4 5 B
3: 4 9 2 4 5 B
4: 4 9 2 5 6 C
5: 4 9 2 6 9 D
6: 6 12 3 6 9 D
7: 6 12 3 9 11 E
8: 6 12 3 11 12 F
9: 11 17 4 11 12 F
10: 11 17 4 12 17 G
11: 18 20 5 18 20 I
注意、私はmultiplot functionを使用しています。
# problem
p1 <- ggplot(intervals, aes(x=V1,xend=V2,y=intid,yend=intid))+geom_segment()+geom_vline(xintercept=endpoints, linetype=3)+xlab('')+ylab('')+ggtitle('Input')
# solution
p2 <- ggplot(relations)+
geom_segment(aes(x=i.V1, xend=i.V2, y=intid,yend=intid, color=as.factor(subid)))+
geom_vline(xintercept=endpoints, linetype=3)+
geom_text(aes(x=(i.V1+i.V2)/2, y=intid+0.2, label=subid), color='black')+
geom_segment(data=decomp, aes(x=V1, xend=V2, y=0, yend=0, color=as.factor(subid)))+
geom_text(data=decomp, aes(x=(V1+V2)/2, y=0+0.2, label=subid), color='black')+
geom_hline(yintercept=0.5)+guides(color='none')+xlab('')+ylab('')+ggtitle('Output')
multiplot(p1,p2)
私が正しく理解しているかどうかはわかりませんが、間隔のリストに穴がない限り、次のように動作するはずです。
間隔のすべての端点のリストを作成する
1, 5, 4, 9, 6, 12, 11, 17
そのリストをソートする
1, 4, 5, 6, 9, 11, 12, 17
新しい間隔のエンドポイントとして常に隣接する番号を使用して、新しい間隔を作成します
[1,4] [4,5] [5,6] [6,9] [9,11] [11,12] [12,17]
間隔のリストにいくつかの穴がある場合は、新しく作成された各間隔がソース間隔の 1 つと重複しているかどうかを確認する必要があります。