找分钟.序列的"加入"操作

Question

比方说,我们有一个列表/正整数数组x1,x2,...,xn.我们可以对这个序列进行连接操作,这意味着我们可以用一个元素替换两个彼此相邻的元素,这是这些元素的总和.例如:

- > array/list:[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的最佳连接序列,以便对得到的最终序列进行排序,并且所有元素是> = sum(m ... n).

直接实现递归当然会导致指数时间算法,但使用动态编程的简单调整使其成为O(N ^ 2),因为基本上所有(m,n)对都被认为是一次.使用动态编程实现递归的一种简单方法是使(m,n)索引的数据结构在计算后存储f(m,n)的结果,以便下次调用f(m)时,n),我们可以查找以前保存的结果.以下代码使用R编程语言执行此操作.我正在使用我们想要找到最小连接数的公式来获得非递减序列.对于那些刚接触R的人来测试这段代码,只需从任何镜像(Google"R Project")下载R,将其激活,然后将两个函数定义(f和solve)粘贴到控制台中,然后使用任何向量求解"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.

Answer 2

一些哈斯克尔代码：

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, 6, 3, 8, 5, 6, 5]

...现在我们得到：

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