Find min. "join" operations for sequence

Question

Let's say, we have a list/an array of positive integers x1, x2, ... , xn. We can do a join operation on this sequence, that means that we can replace two elements that are next to each other with one element, which is sum of these elements. For example:

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

• we can join 2 and 3, and replace them with 5;
• we can join 5 and 6, and replace them with 11;
• we cannot join 2 and 4;
• we cannot join 1 and 3 etc.

Main problem is to find minimum join operations for given sequence, after which this sequence will be sorted in increasing order.

Note: empty and one-element sequences are sorted in increasing order.

Basic examples:

• for [4; 6; 5; 3; 9] solution is 1 (we join 5 and 3)

• for [1; 3; 6; 5] solution is also 1 (we join 6 and 5)

What I am looking for, is an algorithm that solve this problem. It could be in pseudocode, C, C++, PHP, OCaml or similar (I mean: I would understand solution, if You wrote solution in one of these languages).

Answer 1

This is an ideal problem to solve using Dynamic Programming, and the recurrence described by @lijie is exactly the right approach, with a few minor tweaks to ensure all possibilities are considered. There are two key observations: (a) Any sequence of join operations results in a set of non-overlapping summed subsequences of the original vector, and (b) For the optimal join-sequence, if we look to the right of any summed subsequence (m...n), that portion is an optimal solution to the problem: "find an optimal join-sequence for the sub-vector (n+1)...N such that the resulting final sequence is sorted, and all elements are >= sum(m...n).

Implementing the recurrence directly would of course result in an exponential time algorithm, but a simple tweak using Dynamic Programming makes it O(N^2), because essentially all (m,n) pairs are considered once. An easy way to implement the recurrence using Dynamic Programming is to have a data-structure indexed by (m,n) that stores the results of f(m,n) once they are computed, so that the next time we invoke f(m,n), we can lookup the previously saved results. The following code does this using the R programming language. I am using the formulation where we want to find the min-number of joins to get a non-decreasing sequence. For those new to R, to test this code, simply download R from any mirror (Google "R Project"), fire it up, and paste the two function definitions (f and solve) into the console, and then solve any vector using "solve(c(...))" as in the examples below.

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

Here are some sample runs:

> 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 

Note that the min number of joins for the sequence considered by @kotlinski is 30, not 32 or 33.

Answer 2

Greedy algorithm!

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

At each step, grab more elements until their sum is not less than the last. If you run out of elements, just join all the ones that remain to the prior group.

---

That was wrong.

Combinatorial explosion!

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 ]

Just try every possible joining and take the minimum. I couldn't think of a smart heuristic to limit backtracking, but this should be O(n²) with dynamic programming, and O(2ⁿ) as written.