Алгоритм - выбрать три самых длинных возрастающих подпоследовательности
1,00
р.
Дан линейный массив большой длины. Очевидно, что из него можно выбрать возрастающую подпоследовательность элементов. Мне нужно выбрать три таких подпоследовательности, чтобы их суммарная длина была наибольшей из возможных.
Как это сделать?
Жадные алгоритмы можно предлагать с обоснованием правильности. Для массива (1, 5, 9, 13, 17, 2, 6, 10, 3, 7, 11, 4, 8, 12) "тупой" жадный алгоритм даст выбор 5+4+3=12 элементов, в то время как на самом деле можно выбрать и 13. Точное нахождение максимального количества критично. Если есть несколько вариантов с одинаковым максимумом, можно брать любой из них.
Правила выбора последовательностей: выбранные три последовательности не должны пересекаться между собой никакими элементами.
Ответ
Между прочим, жадный алгоритм действительно работает (по крайней мере на этом массиве), если за "жадный" алгоритм принимать "найти наибольшую возрастающую подпоследовательность, выкинуть её из массива, повторить трижды". Результат:
(1, 2, 3, 4, 8, 12), (5, 6, 7 ,11), (9, 13, 17)
13 элементов. 14 сделать нельзя. Код на Powershell:
function liss ([int64[]] $x) { $m=new-object int64[] ($x.length) # хэш-таблица затеяла сбоить даже при приведении типов. # То ли где-то переменная не того типа оказалась, то ли ещё что - заменил в лоб на массивы $p=new-object int64[] (1+$x.length) $l=0 $xl=$x.length foreach ($i in 0..($xl-1)) { $lo=1 $hi=$l while ($lo -le $hi) { $mid=[Math]::Ceiling(($lo+$hi)/2) if ($x[[int]$m[$mid]] -le $x[$i]) { # заменить -le на -lt если возрастание строгое $lo=$mid+1 } else { $hi=$mid-1 } } $newL=$lo $p[$i]=$m[$newl-1] $m[$newL]=$i if ($newL -gt $l) { $l = $newL } } $s=@() $k=[int]$m[$l] foreach ($i in ($l-1)..0) { $args=@{} $args["index"]=$k $args["value"]=$x[$k] $o=new-object psobject -prop $args
$s=@($o)+$s $k=[int]$p[$k] } return $s }
function cutfrom ([int64[]] $x, [Object[]] $seq) { $a=@() $vs=$seq | select -expand index foreach ($i in 0..($x.length-1)) { if ($i -notin $vs) { $a+=$x[$i] } } return $a }
function liss3 ([int64[]] $x) { $seq1=liss $x $x1=cutfrom $x $seq1 $seq2=liss $x1 $x2=cutfrom $x1 $seq2 $seq3=liss $x2 write-debug "LISS3 remainder: $((cutfrom $x2 $seq3).length)" # не всегда 0 $res=@($seq1.value)+@($seq2.value)+@($seq3.value) return $res } liss3 @(1, 5, 9, 13, 17, 2, 6, 10, 3, 7, 11, 4, 8, 12)
liss переписан с вики (там код на питоне), cutfrom принимает индексы и возвращает массив, в котором данные индексы выколоты (короче).
Не исключено, что на реальном массиве алгоритм не сработает, однако было бы неплохо такой массив найти.
Апдейт: А я был неправ, "жадный" алгоритм работает далеко не всегда. (Обидно) Код для проверки:
function shuffle ([int64[][]] $x) { if ($x.length -eq 1) { return $x[0] } # one array, wrapped. Nothing to shuffle $m=new-object int64[] ($x.length) $max=1 $thesum=[int]0 foreach ($a in ($x.length-1)..0) { $m[$a]=$x[$a].length $thesum+=$m[$a] if ($m[$a] -gt $max) { $max=$m[$a] } } if ($max -eq 1) { return $x } # one array, nothing to shuffle $al=new-object system.collections.arraylist $rng=new-object system.random while ($thesum -gt 0) { $d=$rng.next($thesum) $i=[int]0 while (($m[$i]) -le $d -and $i -le $m.length) { $d-=$m[$i] $i+=1 } $m[$i] -= 1 $null=$al.add($x[$i][$m[$i]]) $thesum-=1 } $al.reverse() return [object[]]$al }
function test () { $b=1000 $rng=new-object system.random foreach ($a in 1..100) {$a1+=@($b) $b+=$rng.next(2,14) } $b=100 foreach ($a in 1..100) {$a2+=@($b) $b+=$rng.next(2,28) } $b=1111 foreach ($a in 1..100) {$a3+=@($b) $b+=$rng.next(3,16) } $ad=shuffle $a1,$a2,$a3 return $ad }
Здесь в лоб создается массив, состоящий из трех возрастающих подпоследовательностей длиной 100 каждая, перемешанных случайным образом. После чего натравление LISS3 на массив не всегда выдает результат длиной 300.
То есть задача мало того что непроста, но решение "в лоб" имеет приличную погрешность.
Как это сделать?
Жадные алгоритмы можно предлагать с обоснованием правильности. Для массива (1, 5, 9, 13, 17, 2, 6, 10, 3, 7, 11, 4, 8, 12) "тупой" жадный алгоритм даст выбор 5+4+3=12 элементов, в то время как на самом деле можно выбрать и 13. Точное нахождение максимального количества критично. Если есть несколько вариантов с одинаковым максимумом, можно брать любой из них.
Правила выбора последовательностей: выбранные три последовательности не должны пересекаться между собой никакими элементами.
Ответ
Между прочим, жадный алгоритм действительно работает (по крайней мере на этом массиве), если за "жадный" алгоритм принимать "найти наибольшую возрастающую подпоследовательность, выкинуть её из массива, повторить трижды". Результат:
(1, 2, 3, 4, 8, 12), (5, 6, 7 ,11), (9, 13, 17)
13 элементов. 14 сделать нельзя. Код на Powershell:
function liss ([int64[]] $x) { $m=new-object int64[] ($x.length) # хэш-таблица затеяла сбоить даже при приведении типов. # То ли где-то переменная не того типа оказалась, то ли ещё что - заменил в лоб на массивы $p=new-object int64[] (1+$x.length) $l=0 $xl=$x.length foreach ($i in 0..($xl-1)) { $lo=1 $hi=$l while ($lo -le $hi) { $mid=[Math]::Ceiling(($lo+$hi)/2) if ($x[[int]$m[$mid]] -le $x[$i]) { # заменить -le на -lt если возрастание строгое $lo=$mid+1 } else { $hi=$mid-1 } } $newL=$lo $p[$i]=$m[$newl-1] $m[$newL]=$i if ($newL -gt $l) { $l = $newL } } $s=@() $k=[int]$m[$l] foreach ($i in ($l-1)..0) { $args=@{} $args["index"]=$k $args["value"]=$x[$k] $o=new-object psobject -prop $args
$s=@($o)+$s $k=[int]$p[$k] } return $s }
function cutfrom ([int64[]] $x, [Object[]] $seq) { $a=@() $vs=$seq | select -expand index foreach ($i in 0..($x.length-1)) { if ($i -notin $vs) { $a+=$x[$i] } } return $a }
function liss3 ([int64[]] $x) { $seq1=liss $x $x1=cutfrom $x $seq1 $seq2=liss $x1 $x2=cutfrom $x1 $seq2 $seq3=liss $x2 write-debug "LISS3 remainder: $((cutfrom $x2 $seq3).length)" # не всегда 0 $res=@($seq1.value)+@($seq2.value)+@($seq3.value) return $res } liss3 @(1, 5, 9, 13, 17, 2, 6, 10, 3, 7, 11, 4, 8, 12)
liss переписан с вики (там код на питоне), cutfrom принимает индексы и возвращает массив, в котором данные индексы выколоты (короче).
Не исключено, что на реальном массиве алгоритм не сработает, однако было бы неплохо такой массив найти.
Апдейт: А я был неправ, "жадный" алгоритм работает далеко не всегда. (Обидно) Код для проверки:
function shuffle ([int64[][]] $x) { if ($x.length -eq 1) { return $x[0] } # one array, wrapped. Nothing to shuffle $m=new-object int64[] ($x.length) $max=1 $thesum=[int]0 foreach ($a in ($x.length-1)..0) { $m[$a]=$x[$a].length $thesum+=$m[$a] if ($m[$a] -gt $max) { $max=$m[$a] } } if ($max -eq 1) { return $x } # one array, nothing to shuffle $al=new-object system.collections.arraylist $rng=new-object system.random while ($thesum -gt 0) { $d=$rng.next($thesum) $i=[int]0 while (($m[$i]) -le $d -and $i -le $m.length) { $d-=$m[$i] $i+=1 } $m[$i] -= 1 $null=$al.add($x[$i][$m[$i]]) $thesum-=1 } $al.reverse() return [object[]]$al }
function test () { $b=1000 $rng=new-object system.random foreach ($a in 1..100) {$a1+=@($b) $b+=$rng.next(2,14) } $b=100 foreach ($a in 1..100) {$a2+=@($b) $b+=$rng.next(2,28) } $b=1111 foreach ($a in 1..100) {$a3+=@($b) $b+=$rng.next(3,16) } $ad=shuffle $a1,$a2,$a3 return $ad }
Здесь в лоб создается массив, состоящий из трех возрастающих подпоследовательностей длиной 100 каждая, перемешанных случайным образом. После чего натравление LISS3 на массив не всегда выдает результат длиной 300.
То есть задача мало того что непроста, но решение "в лоб" имеет приличную погрешность.
