algorithm - complexity - Encontrar min. Operaciones de "unión" para secuencia

sorting algorithms complexity

Question

Digamos que tenemos una lista / una matriz de enteros positivos x1, x2, ..., xn. Podemos hacer una operación de unión en esta secuencia, lo que significa que podemos reemplazar dos elementos que están uno al lado del otro con un elemento, que es la suma de estos elementos. Por ejemplo:

-> array / list: [1; 2; 3; 4; 5; 6]

• Podemos unir 2 y 3, y reemplazarlos con 5;
• Podemos unir 5 y 6, y reemplazarlos con 11;
• no podemos unir 2 y 4;
• no podemos unir 1 y 3 etc.

El principal problema es encontrar operaciones de unión mínimas para una secuencia dada, después de lo cual esta secuencia se ordenará en orden creciente.

Nota: las secuencias vacías y de un elemento se ordenan en orden creciente.

Ejemplos básicos:

• para 4; 6; 5; 3; 9] la solución es 1 ( unimos 5 y 3)

• para 1; 3; 6; 5] solución es también 1 ( unimos 6 y 5)

Lo que estoy buscando es un algoritmo que resuelva este problema. Podría estar en pseudocódigo, C, C ++, PHP, OCaml o similar (quiero decir: entendería la solución si escribiera la solución en uno de estos idiomas).

Answer 1

Algún código 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 a@_ = a

edits xs = length xs - length (sortJoin xs)

ACTUALIZACIÓN: Hecho este trabajo con la prueba = [2, 8, 2, 2, 8, 3, 8, 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]

... ahora tenemos:

> sortJoin test
[2,8,12,20,20,23,27,28,31,55]
> edits test
32

Answer 2

Esperemos que sea sencillo. Aquí hay un pseudocódigo que es tiempo exponencial.

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++)

Aquí hay una implementación en 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]))))

Answer 3

Este es el código pchalasani en F # con algunas modificaciones. La memoria es similar, agregué un generador de función sumRange para sumas en tiempo O (1) y moví la posición de inicio a f 1 0 para omitir la comprobación de n = 0 en 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

Código completo.

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

Answer 4

Este es un problema ideal para resolver utilizando la Programación Dinámica, y la recurrencia descrita por @lijie es exactamente el enfoque correcto, con algunos ajustes menores para garantizar que se consideren todas las posibilidades. Hay dos observaciones clave: (a) Cualquier secuencia de operaciones de unión da como resultado un conjunto de subsecuencias sumadas no superpuestas del vector original, y (b) Para la secuencia de unión óptima, si miramos a la derecha de cualquier subsecuencia sumada (m ... n), esa parte es una solución óptima para el problema: "encuentre una secuencia de unión óptima para el vector secundario (n + 1) ... N tal que la secuencia final resultante esté ordenada, y todo los elementos son> = suma (m ... n).

Por supuesto, implementar la recurrencia directamente resultaría en un algoritmo de tiempo exponencial, pero un simple ajuste con la Programación Dinámica hace que sea O (N ^ 2), porque esencialmente todos los pares (m, n) se consideran una sola vez. Una forma fácil de implementar la recurrencia utilizando la Programación Dinámica es tener una estructura de datos indexada por (m, n) que almacena los resultados de f (m, n) una vez que se calculan, de modo que la próxima vez que invocamos f (m) , n), podemos buscar los resultados guardados anteriormente. El siguiente código lo hace usando el lenguaje de programación R. Estoy usando la formulación en la que queremos encontrar el número mínimo de combinaciones para obtener una secuencia no decreciente. Para aquellos que son nuevos en R, para probar este código, simplemente descargue R desde cualquier espejo ("Proyecto R" de Google), enciéndalo y pegue las dos definiciones de función (f y resolver) en la consola, y luego resuelva cualquier vector usando "resolver (c (...))" como en los ejemplos a continuación.

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'' )
}

Aquí hay algunos ejemplos de ejecuciones:

> 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 

Tenga en cuenta que el número mínimo de uniones para la secuencia considerada por @kotlinski es 30, no 32 o 33.

Answer 5

Un enfoque de programación dinámica:

Deje que la matriz original sea a[i], 0 <= i < N .

Defina f(m, n) como el número mínimo de combinaciones necesarias para hacer a[n..N-1] ordenada, de modo que todos los elementos en la lista secundaria ordenada sean > (o >= , si se desea otra variante) la suma de a[m..n-1] (deje que la suma de una lista vacía sea -inf ).

El caso base es f(m, N) = 0 (la lista secundaria está vacía).

La recursión es f(m, n) = min_{n < k <= N st sum(a[n..k-1]) > sum(a[m..n-1])} f(n, k) + kn-1 . Si no son adecuados los valores de k, entonces f(m, n) = inf (cualquier cosa >= N también funcionará, porque hay un máximo N-1 uniones N-1 ).

Calcule f(m,n) en orden decreciente de m y n .

Entonces, la respuesta deseada es f(0,0) .

EDITAR

Vaya, esta es básicamente la segunda respuesta de efímero, creo, aunque no estoy lo suficientemente familiarizado con Haskell para saber exactamente lo que está haciendo.

Answer 6

Algoritmo codicioso !

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

En cada paso, toma más elementos hasta que su suma no sea menor que la anterior. Si te quedas sin elementos, simplemente une todos los que permanecen en el grupo anterior.

Eso estuvo mal.

¡ Explosión combinatoria !

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 ]

Simplemente intente cada posible unión y tome el mínimo. No podría pensar en una heurística inteligente para limitar el retroceso, pero esto debería ser O (n²) con programación dinámica y O (2 ⁿ ) como está escrito.