Найдите мин. операции "присоединиться" для последовательности
Скажем, у нас есть список/массив положительных целых чисел x1, x2,..., xn.
Мы можем выполнить операцию объединения в этой последовательности, что означает, что мы можем заменить два элемента, которые находятся рядом друг с другом с одним элементом, который является суммой этих элементов. Например:
- > массив/список: [1; 2; 3; 4; 5; 6]
- мы можем присоединиться к 2 и 3 и заменить их на 5;
- мы можем присоединиться к 5 и 6 и заменить их на 11;
- мы не можем соединить 2 и 4;
- мы не можем присоединяться к 1 и 3 и т.д.
Основная проблема заключается в том, чтобы найти минимальные операции объединения для данной последовательности, после чего эта последовательность будет сортироваться в порядке возрастания.
Примечание: пустые и одноэлементные последовательности сортируются в порядке возрастания.
Основные примеры:
Я ищу, это алгоритм, который решает эту проблему. Это может быть в псевдокоде, C, С++, PHP, OCaml или аналогичном (я имею в виду: я бы понял решение, если вы написали решение на одном из этих языков).
Ответы
Ответ 1
Это идеальная проблема для решения проблемы с использованием динамического программирования, и повторяемость, описанная @lijie, - это точно правильный подход, с несколькими незначительными изменениями, чтобы обеспечить рассмотрение всех возможностей. Существует два ключевых наблюдения: (a) Любая последовательность операций объединения приводит к набору непересекающихся суммированных подпоследовательностей исходного вектора и (b) для оптимальной последовательности присоединения, если мы смотрим справа от любой суммированной подпоследовательности (m... n) эта часть является оптимальным решением проблемы: "найдите оптимальную последовательность присоединения для подвектора (n + 1)... N так, чтобы итоговая конечная последовательность была отсортирована, и все элементы >= sum (m... n).
Реализация повторения напрямую, конечно, приведет к экспоненциальному алгоритму времени, но простая настройка с использованием динамического программирования делает его O (N ^ 2), потому что по существу все пары (m, n) рассматриваются один раз. Простой способ реализации повторения с использованием динамического программирования состоит в том, чтобы индексировать структуру данных (m, n), которая хранит результаты f (m, n) после их вычисления, так что в следующий раз мы вызываем f (m, n), мы можем найти ранее сохраненные результаты. Следующий код делает это с использованием языка программирования R. Я использую формулировку, в которой мы хотим найти минимальное число объединений, чтобы получить неубывающую последовательность. Для тех, кто не знаком с R, чтобы проверить этот код, просто загрузите R из любого зеркала (Google "R Project" ), запустите его и вставьте в консоль два определения функций (f и решите), а затем разрешите любой вектор, используя "solve (c (...))", как в приведенных ниже примерах.
f <- function(m,n) {
name <- paste(m,n)
nCalls <<- nCalls + 1
# use <<- for global assignment
if( !is.null( Saved[[ name ]] ) ) {
# the solution for (m,n) has been cached, look it up
nCached <<- nCached + 1
return( Saved[[ name ]] )
}
N <- length(vec) # vec is global to this function
sum.mn <- -Inf
if(m >= 1)
sum.mn <- sum( vec[m:n] )
if(n == N) { # boundary case: the (m,n) range includes the last number
result <- list( num = 0, joins = list(), seq = c())
} else
{
bestNum <- Inf
bestJoins <- list()
bestSeq <- c()
for( k in (n+1):N ) {
sum.nk <- sum( vec[ (n+1):k ] )
if( sum.nk < sum.mn ) next
joinRest <- f( n+1, k )
numJoins <- joinRest$num + k-n-1
if( numJoins < bestNum ) {
bestNum <- numJoins
if( k == n+1 )
bestJoins <- joinRest$joins else
bestJoins <- c( list(c(n+1,k)), joinRest$joins )
bestSeq <- c( sum.nk, joinRest$seq)
}
}
result <- list( num = bestNum, joins = bestJoins, seq = bestSeq )
}
Saved[[ name ]] <<- result
result
}
solve <- function(input) {
vec <<- input
nCalls <<- 0
nCached <<- 0
Saved <<- c()
result <- f(0,0)
cat( 'Num calls to f = ', nCalls, ', Cached = ', nCached, '\n')
cat( 'Min joins = ', result$num, '\n')
cat( 'Opt summed subsequences: ')
cat( do.call( paste,
lapply(result$joins,
function(pair) paste(pair[1], pair[2], sep=':' ))),
'\n')
cat( 'Final Sequence: ', result$seq, '\n' )
}
Вот несколько примеров:
> solve(c(2,8,2,2,9,12))
Num calls to f = 22 , Cached = 4
Min joins = 2
Opt summed subsequences: 2:3 4:5
Final Sequence: 2 10 11 12
> solve(c(1,1,1,1,1))
Num calls to f = 19 , Cached = 3
Min joins = 0
Opt summed subsequences:
Final Sequence: 1 1 1 1 1
> solve(c(4,3,10,11))
Num calls to f = 10 , Cached = 0
Min joins = 1
Opt summed subsequences: 1:2
Final Sequence: 7 10 11
> solve(c (2, 8, 2, 2, 8, 3, 8, 9, 9, 2, 9, 8, 8, 7, 4, 2, 7, 5, 9, 4, 6, 7, 4, 7, 3, 4, 7, 9, 1, 2, 5, 1, 8, 7, 3, 3, 6, 3, 8, 5, 6, 5))
Num calls to f = 3982 , Cached = 3225
Min joins = 30
Opt summed subsequences: 2:3 4:5 6:7 8:9 10:12 13:16 17:19 20:23 24:27 28:33 34:42
Final Sequence: 2 10 10 11 18 19 21 21 21 21 26 46
Обратите внимание, что минимальное число объединений для последовательности, рассматриваемой @kotlinski, 30, а не 32 или 33.
Ответ 2
Жадный алгоритм!
import Data.List (inits)
joinSequence :: (Num a, Ord a) => [a] -> Int
joinSequence (x:xs) = joinWithMin 0 x xs
where joinWithMin k _ [] = k
joinWithMin k x xs =
case dropWhile ((< x) . snd) $ zip [0..] $ scanl1 (+) xs
of (l, y):_ -> joinWithMin (k + l) y $ drop (l+1) xs
_ -> k + length xs
joinSequence _ = 0
На каждом шаге возьмите больше элементов, пока их сумма не будет меньше последней. Если у вас заканчиваются элементы, просто присоедините все те, которые остаются в предыдущей группе.
Это было неправильно.
Комбинаторный взрыв!
joinSequence :: (Num a, Ord a) => [a] -> Int
joinSequence = joinWithMin 0 0
where joinWithMin k _ [] = k
joinWithMin k m xs =
case dropWhile ((< m) . snd) $ zip [0..] $ scanl1 (+) xs
of [] -> k + length xs
ys -> minimum [ joinWithMin (k+l) y $ drop (l+1) xs
| (l, y) <- ys ]
Просто попробуйте все возможные соединения и возьмите минимум. Я не мог придумать умную эвристику, чтобы ограничить возврат, но это должно быть O (n²) с динамическим программированием и O (2 n), как написано.
Ответ 3
Подход к динамическому программированию:
Пусть исходный массив a[i], 0 <= i < N.
Определите f(m, n) как минимальное количество соединений, необходимых для сортировки a[n..N-1], так что все элементы в отсортированном подсписке > (или >=, если требуется другой вариант) сумма a[m..n-1] (пусть сумма пустого списка будет -inf).
Базовый регистр f(m, N) = 0 (подвыбор пуст).
Рекурсия f(m, n) = min_{n < k <= N s.t. sum(a[n..k-1]) > sum(a[m..n-1])} f(n, k) + k-n-1. Если никакие значения k не подходят, то пусть f(m, n) = inf (все >= N также будет работать, потому что не более чем N-1 присоединяется).
Рассчитайте f(m,n) в порядке убывания m и n.
Тогда требуемый ответ f(0,0).
ИЗМЕНИТЬ
К сожалению, это, по-моему, в основном эфемерный второй ответ, хотя я недостаточно знаком с Haskell, чтобы точно знать, что он делает.
Ответ 4
Некоторые коды Haskell:
sortJoin (a:b:c:xs)
| a <= b = a : sortJoin (b:c:xs)
| a+b <= c = a+b : sortJoin (c:xs)
| otherwise = sortJoin (a:b+c:xs)
sortJoin (a:b:[]) = if a <= b then [a,b] else [a+b]
sortJoin [email protected]_ = a
edits xs = length xs - length (sortJoin xs)
ОБНОВЛЕНИЕ: Сделал эту работу с тестом = [2, 8, 2, 2, 8, 3, 8, 9, 9, 2, 9, 8, 8, 7, 4, 2, 7, 5, 9, 4, 6, 7, 4, 7, 3, 4, 7, 9, 1, 2, 5, 1, 8, 7, 3, 3, 6, 3, 8, 5, 6, 5]
... теперь получим:
> sortJoin test
[2,8,12,20,20,23,27,28,31,55]
> edits test
32
Ответ 5
Надеюсь, это просто. Здесь некоторый псевдокод, экспоненциальное время.
Function "join" (list, max-join-count, join-count) ->
Fail if join-count is greater than max-join-count.
If the list looks sorted return join-count.
For Each number In List
Recur (list with current and next number joined, max-join-count, join-count + 1)
Function "best-join" (list) ->
max-join-count = 0
while not join (list, max-join-count++)
Здесь реализация на Clojure:
(defn join-ahead [f i v]
(concat (take i v)
[(f (nth v i) (nth v (inc i)))]
(drop (+ 2 i) v)))
(defn sort-by-joining
"Sort a list by joining neighboring elements with `+'"
([v max-join-count join-count]
(if (or (nil? max-join-count)
(<= join-count max-join-count))
(if (or (empty? v)
(= v (sort v)))
{:vector v :join-count join-count}
(loop [i 0]
(when (< (inc i) (count v))
(let [r (sort-by-joining (join-ahead + i v)
max-join-count
(inc join-count))]
(or r (recur (inc i)))))))))
([v max-join-count]
(sort-by-joining v max-join-count 0))
([v]
(sort-by-joining v nil 0)))
(defn fewest-joins [v]
(loop [i 0]
(if (sort-by-joining v i)
i
(recur (inc i)))))
(deftest test-fewest-joins
(is (= 0 (fewest-joins nil)))
(is (= 1 (fewest-joins [4 6 5 3 9])))
(is (= 6 (fewest-joins [1 9 22 90 1 1 1 32 78 13 1]))))
Ответ 6
Это код pchalasani в F # с некоторыми изменениями. Мемуаризация аналогична, я добавил генератор функции sumRange для сумм в O (1) раз и переместил начальную позицию в f 1 0, чтобы пропустить проверку для n = 0 в minJoins.
let minJoins (input: int array) =
let length = input.Length
let sum = sumRange input
let rec f = memoize2 (fun m n ->
if n = length then
0
else
let sum_mn = sum m n
{n + 1 .. length}
|> Seq.filter (fun k -> sum (n + 1) k >= sum_mn)
|> Seq.map (fun k -> f (n + 1) k + k-n-1)
|> Seq.append {length .. length}
|> Seq.min
)
f 1 0
Полный код.
open System.Collections.Generic
// standard memoization
let memoize2 f =
let cache = new Dictionary<_, _>()
(fun x1 x2 ->
match cache.TryGetValue((x1, x2)) with
| true, y -> y
| _ ->
let v = f x1 x2
cache.Add((x1, x2), v)
v)
// returns a function that takes two integers n,m and returns sum(array[n:m])
let sumRange (array : int array) =
let forward = Array.create (array.Length + 1) 0
let mutable total = 0
for i in 0 .. array.Length - 1 do
total <- total + array.[i]
forward.[i + 1] <- total
(fun i j -> forward.[j] - forward.[i - 1])
// min joins to sort an array ascending
let minJoins (input: int array) =
let length = input.Length
let sum = sumRange input
let rec f = memoize2 (fun m n ->
if n = length then
0
else
let sum_mn = sum m n
{n + 1 .. length}
|> Seq.filter (fun k -> sum (n + 1) k >= sum_mn)
|> Seq.map (fun k -> f (n + 1) k + k-n-1)
|> Seq.append {length .. length} // if nothing passed the filter return length as the min
|> Seq.min
)
f 1 0
let input = [|2;8;2;2;8;3;8;9;9;2;9;8;8;7;4;2;7;5;9;4;6;7;4;7;3;4;7;9;1;2;5;1;8;7;3;3;6;3;8;5;6;5|]
let output = minJoins input
printfn "%A" output
// outputs 30
