找到敏。序列的“联接”操作

Question

比方说，我们有一个list/一个正整数数组x1，x2，…，xn。我们可以对这个序列执行连接操作，这意味着我们可以用一个元素替换相邻的两个元素，即这些元素的和。例如：

->数组/列表: 1;2;3;4;5;6

• 我们可以加入2和3，用5代替；
• 我们可以加入5和6，用11代替；
• 我们不能连接2和4；
• 我们不能连接1和3等。

主要问题是找出给定序列的最小连接操作，然后将该序列按递增顺序排序。

注意：的空元素序列和单元素序列按递增顺序排序。

基本例子：

• 对于4；6；5；3；9解是1(我们加入5和3)
• 对于1；3；6；5解也是1(我们加入了6和5)。

我要找的是一个解决这个问题的算法。它可以是伪代码、C、C++、PHP、OCaml或类似语言(我的意思是:如果您用这些语言之一编写解决方案，我会理解解决方案)。

Answer 1

这是一个用动态规划来解决的理想问题，@lijie所描述的递归问题正是正确的方法，并做了一些小的调整，以确保所有的可能性都得到考虑。有两个关键的观察：(a)连接操作的任何序列都会产生原始向量的一组不重叠的求和子序列；(b)对于最优连接序列，如果我们查看任何相加子序列(m.n)的右侧，则该部分是该问题的最优解：“为子向量(n+1)...N找到一个最佳连接序列，以便对最终序列进行排序，并且所有元素都是>=和(m.n)。

直接实现递推当然会产生指数时间算法，但使用动态规划的简单调整使得它成为O(N^2)，因为本质上所有(m，n)对都是一次考虑的。使用动态规划实现递归的一个简单方法是，有一个由(m，n)索引的数据结构，一旦计算出f(m，n)的结果就会存储，这样下次我们调用f(m，n)时，就可以查找先前保存的结果。下面的代码使用R编程语言实现了这一点。我使用的公式中，我们想要找到连接的最小数，得到一个的非递减序列。对于那些刚到R的，测试这个代码，只需从任何镜像下载R (Google "R“)，启动它，并将两个函数定义(f和解题)粘贴到控制台，然后使用”求解(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.。

Answer 2

动态规划方法：

将原始数组设为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还不太熟悉，不知道它到底在做什么。

Answer 3

一些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)

更新:使用test = 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、3、6、3、8、5、6、5、5、5、5

我们得到的...now：

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