すべての最長増加サブシーケンスの数を見つける
最長増加サブシーケンスの長さだけでなく、そのような長さのサブシーケンスの数も検出する、改良された LIS アルゴリズムの完全な Java コードを以下に示します。私はジェネリックを使用して、整数だけでなく、同等の型を許可することを好みます。
@Test
public void testLisNumberAndLength() {
List<Integer> input = Arrays.asList(16, 5, 8, 6, 1, 10, 5, 2, 15, 3, 2, 4, 1);
int[] result = lisNumberAndlength(input);
System.out.println(String.format(
"This sequence has %s longest increasing subsequenses of length %s",
result[0], result[1]
));
}
/**
* Body of improved LIS algorithm
*/
public <T extends Comparable<T>> int[] lisNumberAndLength(List<T> input) {
if (input.size() == 0)
return new int[] {0, 0};
List<List<Sub<T>>> subs = new ArrayList<>();
List<Sub<T>> tails = new ArrayList<>();
for (T e : input) {
int pos = search(tails, new Sub<>(e, 0), false); // row for a new sub to be placed
int sum = 1;
if (pos > 0) {
List<Sub<T>> pRow = subs.get(pos - 1); // previous row
int index = search(pRow, new Sub<T>(e, 0), true); // index of most left element that <= e
if (pRow.get(index).value.compareTo(e) < 0) {
index--;
}
sum = pRow.get(pRow.size() - 1).sum; // sum of tail element in previous row
if (index >= 0) {
sum -= pRow.get(index).sum;
}
}
if (pos >= subs.size()) { // add a new row
List<Sub<T>> row = new ArrayList<>();
row.add(new Sub<>(e, sum));
subs.add(row);
tails.add(new Sub<>(e, 0));
} else { // add sub to existing row
List<Sub<T>> row = subs.get(pos);
Sub<T> tail = row.get(row.size() - 1);
if (tail.value.equals(e)) {
tail.sum += sum;
} else {
row.add(new Sub<>(e, tail.sum + sum));
tails.set(pos, new Sub<>(e, 0));
}
}
}
List<Sub<T>> lastRow = subs.get(subs.size() - 1);
Sub<T> last = lastRow.get(lastRow.size() - 1);
return new int[]{last.sum, subs.size()};
}
/**
* Implementation of binary search in a sorted list
*/
public <T> int search(List<? extends Comparable<T>> a, T v, boolean reversed) {
if (a.size() == 0)
return 0;
int sign = reversed ? -1 : 1;
int right = a.size() - 1;
Comparable<T> vRight = a.get(right);
if (vRight.compareTo(v) * sign < 0)
return right + 1;
int left = 0;
int pos = 0;
Comparable<T> vPos;
Comparable<T> vLeft = a.get(left);
for(;;) {
if (right - left <= 1) {
if (vRight.compareTo(v) * sign >= 0 && vLeft.compareTo(v) * sign < 0)
return right;
else
return left;
}
pos = (left + right) >>> 1;
vPos = a.get(pos);
if (vPos.equals(v)) {
return pos;
} else if (vPos.compareTo(v) * sign > 0) {
right = pos;
vRight = vPos;
} else {
left = pos;
vLeft = vPos;
}
}
}
/**
* Class for 'sub' pairs
*/
public static class Sub<T extends Comparable<T>> implements Comparable<Sub<T>> {
T value;
int sum;
public Sub(T value, int sum) {
this.value = value;
this.sum = sum;
}
@Override public String toString() {
return String.format("(%s, %s)", value, sum);
}
@Override public int compareTo(Sub<T> another) {
return this.value.compareTo(another.value);
}
}
説明
説明が長くなりそうなので、最初のシーケンスを「seq」、それ以降のシーケンスを「sub」と呼びます。したがって、タスクは、seq から取得できる最長増加サブの数を計算することです。
前に述べたように、アイデアは、前のステップで取得されたすべての可能な最長のサブのカウントを保持することです。行の番号付きリストを作成しましょう。ここで、各行の数は、この行に格納されているサブルーチンの長さに等しくなります。そして、サブを数値のペア (v, c) として保存しましょう。ここで、"v" は終了要素の "値" であり、"c" は"v" で終わる指定された長さのサブの "カウント"です。例えば：
1: (16, 1) // that means that so far we have 1 sub of length 1 which ends by 16.
このようなリストを段階的に作成し、最初のシーケンスから要素を順番に取得します。すべてのステップで、この要素を追加して変更を記録できる最長のサブに追加しようとします。
リストの作成
可能なすべてのオプションがあるため、例のシーケンスを使用してリストを作成しましょう。
16 5 8 6 1 10 5 2 15 3 2 4 1
まず、要素16を取ります。ここまでのリストは空なので、ペアを 1 つだけ入れます。
1: (16, 1) <= one sub that ends by 16
次は5です。これは 16 で終わるサブに追加できないため、長さが 1 の新しいサブを作成します。ペア (5, 1) を作成し、それを 1 行目に入れます。
1: (16, 1)(5, 1)
次はエレメント8です。長さ 2 のサブ [16, 8] は作成できませんが、サブ [5, 8] は作成できます。だから、これがアルゴリズムの出番です。まず、最後のペアの「値」を見て、リストの行を上下逆に繰り返します。要素がすべての行のすべての最後の要素の値よりも大きい場合、それを既存のサブ要素に追加して、その長さを 1 増やすことができます。したがって、値 8 はリストの新しい行を作成します。これは、これまでにリストに存在するすべての最後の要素の値よりも大きい (つまり > 5) ためです。
1: (16, 1)(5, 1)
2: (8, ?) <=== need to resolve how many longest subs ending by 8 can be obtained
要素 8 は 5 を続けることができますが、16 を続けることはできません。そのため、前の行を最後から検索し、「値」が 8 未満であるペアの「カウント」の合計を計算する必要があります。
(16, 1)(5, 1)^ // sum = 0
(16, 1)^(5, 1) // sum = 1
^(16, 1)(5, 1) // value 16 >= 8: stop. count = sum = 1, so write 1 in pair next to 8
1: (16, 1)(5, 1)
2: (8, 1) <=== so far we have 1 sub of length 2 which ends by 8.
値 8 を長さ 1 のサブルーチン (最初の行) に格納しないのはなぜですか? 可能な限り最大の長さのサブが必要であり、8 は以前のサブをいくつか継続できるためです。したがって、次の 8 より大きいすべての数値もそのようなサブを継続し、8 を可能な限り短い長さのサブとして保持する必要はありません。
次。6 . 行の最後の「値」で逆さまに検索する:
1: (16, 1)(5, 1) <=== 5 < 6, go next
2: (8, 1)
1: (16, 1)(5, 1)
2: (8, 1 ) <=== 8 >= 6, so 6 should be put here
6 の部屋が見つかりました。カウントを計算する必要があります。
take previous line
(16, 1)(5, 1)^ // sum = 0
(16, 1)^(5, 1) // 5 < 6: sum = 1
^(16, 1)(5, 1) // 16 >= 6: stop, write count = sum = 1
1: (16, 1)(5, 1)
2: (8, 1)(6, 1)
処理後1 :
1: (16, 1)(5, 1)(1, 1) <===
2: (8, 1)(6, 1)
処理後10 :
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)
3: (10, 2) <=== count is 2 because both "values" 8 and 6 from previous row are less than 10, so we summarized their "counts": 1 + 1
処理後5 :
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1) <===
3: (10, 2)
処理後2 :
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 1) <===
3: (10, 2)
処理後15 :
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 1)
3: (10, 2)
4: (15, 2) <===
処理後3 :
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 1)
3: (10, 2)(3, 1) <===
4: (15, 2)
処理後2 :
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 2) <===
3: (10, 2)(3, 1)
4: (15, 2)
最後の要素で行を検索するときに等しい要素が見つかった場合、前の行に基づいてその「カウント」を再度計算し、既存の「カウント」に追加します。
処理後4 :
1: (16, 1)(5, 1)(1, 1)
2: (8, 1)(6, 1)(5, 1)(2, 2)
3: (10, 2)(3, 1)
4: (15, 2)(4, 1) <===
処理後1 :
1: (16, 1)(5, 1)(1, 2) <===
2: (8, 1)(6, 1)(5, 1)(2, 2)
3: (10, 2)(3, 1)
4: (15, 2)(4, 1)
では、すべての初期シーケンスを処理した後、何が得られるでしょうか? 最後の行を見ると、3 つの最長のサブがあり、それぞれが 4 つの要素で構成されていることがわかります。2 つは 15 で終わり、1 は 4 で終わります。
複雑さはどうですか？
反復ごとに、最初のシーケンスから次の要素を取得するときに、2 つのループを作成します。1 つ目は、行を反復して次の要素のためのスペースを見つけるとき、2 つ目は前の行のカウントを要約するときです。したがって、要素ごとに最大n回の反復を行います (最悪の場合: 初期 seq が昇順の要素で構成されている場合、すべての行に 1 つのペアを持つ n 行のリストが取得されます。seq が降順でソートされている場合は、 n 個の要素を持つ 1 行のリスト)。ところで、O(n 2 )の複雑さは私たちが望むものではありません。
まず、これは明らかです。すべての中間状態で、行は最後の「値」の昇順でソートされます。したがって、ブルート ループの代わりに、バイナリ検索を実行できます。その複雑さは O(log n) です。
2 つ目は、行要素を毎回ループしてサブの「カウント」を要約する必要がないことです。次のように、新しいペアが行に追加されると、処理中にそれらを要約できます。
1: (16, 1)(5, 2) <=== instead of 1, put 1 + "count" of previous element in the row
したがって、2 番目の数値は、最後に指定された値で取得できる最長のサブの数ではなく、ペアの「値」以上の任意の要素で終了するすべての最長のサブの合計数を示します。
したがって、「カウント」は「合計」に置き換えられます。そして、前の行の要素を反復する代わりに、バイナリ検索を実行し (任意の行のペアは常に「値」によって順序付けられるため可能です)、新しいペアの「合計」を前の行の最後の要素の「合計」として取得します。左の要素から前の行の見つかった位置までの「合計」を引いた値に、現在の行の前の要素の「合計」を加えたもの。
したがって、4を処理する場合:
1: (16, 1)(5, 2)(1, 3)
2: (8, 1)(6, 2)(5, 3)(2, 5)
3: (10, 2)(3, 3)
4: (15, 2) <=== room for (4, ?)
search in row 3 by "values" < 4:
3: (10, 2)^(3, 3)
4 は (3-2+2) とペアになります: (前の行の最後のペアからの「合計」) - (左のペアから前の行の見つかった位置までの「合計」) + (現在の前のペアからの「合計」行）：
4: (15, 2)(4, 3)
この場合、すべての最長サブの最終カウントは、リストの最後の行の最後のペアの「合計」、つまり 3 + 2 ではなく 3 になります。
したがって、行検索と合計検索の両方に対して二分検索を実行すると、O(n*log n) の複雑さが生じます。
消費されるメモリについてはどうですか。すべての配列を処理した後、最大 n ペアを取得するため、動的配列の場合のメモリ消費は O(n) になります。また、動的配列またはコレクションを使用する場合、それらの割り当てとサイズ変更に追加の時間が必要ですが、処理中に並べ替えや再配置を行わないため、ほとんどの操作は O(1) 時間で行われます。したがって、複雑さの見積もりは最終的なようです。