r 序列问题 - 给定序列中的最大变化次数

Question

有人可以帮助我理解 CS 问题。

问题是 New York Time Rollercoaster problem .

我有一个队列:

queue <- seq(from = 1, to = 5)
 1 2 3 4 5

一个人可以贿赂排在他们前面的另一个人，但最多只能贿赂 2 次。因此，队列序列可能如下所示:

Ride: 1, 2, 3, 4, 5  # Original queue
Ride: 1, 2, 3, 5, 4  # 5 bribes number 4
Ride: 1, 2, 5, 3, 4  # 5 bribes number 3 and thus runs out of bribes and cannot move further (it does not state in the problem if 3 can "re-bribe" 5 so I assume they cannot).
Ride: 2, 1, 5, 3, 4  # 2 bribes number 1

所以给定输入 c(1, 2, 3, 4, 5) swaps的最小数量是多少需要得到最终输出 c(2, 1, 5, 3, 4) .

来自 here 的 Python 代码:

def minimumBribes(q):
    moves = 0
    for pos, val in enumerate(q):
        if (val-1) - pos > 2:
            return "Too chaotic"
        for j in xrange(max(0,val-2), pos):
            if q[j] > val:
                moves+=1
    return moves

我正在尝试在 R 中重新创建它并了解解决方案。

Answer 1

这是我认为的一种方式-

minimumBribes <- function(final_q) {
  change <- final_q - seq_along(final_q)
  if(any(change > 2)) return("Too chaotic!")
  sum(change[change > 0])
}

minimumBribes(q = c(2, 1, 5, 3, 4))
[1] 3

说明-

initial_q <- 1:5
final_q <- c(2, 1, 5, 3, 4)

# calculate change in position; +ve is gain and -ve is loss
change <- final_q - initial_q

[1]  1 -1  2 -1 -1
# it is clear that if some gained x posn combined then other(s) lost x posn combined
# i.e. sum of posn gains and losses will always be 0

# therefore, to get min total swaps, simply add either gains or losses
# which in a way implies the most direct path from initial_q to final_q
sum(change[change > 0])

[1] 3