“排序”的最快方法通过切换位来序列

Question

给定有有限的随机序列，如何确定排序序列（即所有0和全部1）所需的最小位切换数量？

请注意，均质序列（例如0000000和1111111）被视为该定义分类。

另外，从技术上讲，这不是“排序”序列，因为元素被定位为原位，而不仅限于与其他元素交换，还有比“排序”更好地描述此活动的词？

Answer 1

令z（n）为设置第一个n位全部0的成本

。令x（n）为“排序”第一n位的最低成本成本。

我们有：

z（0）= 0，x（0）= 0，

如果位点为0：z（i）= z（i-1），x（i）= min（z（i-1），x），x （i-1）+1）

如果位是1：z（i）= z（i-1）+1，x（i）= x（i-1），

答案为x（n）。

代码更容易：

z=0
x=0
for bit in sequence:
    if bit == 0:
       x = min(z,x+1)
    else:
       z = z+1
return x

Answer 2

一个规范的动态程序是在o（1）时间和空间中评估两个状态：保持位相同或切换的成本，同时将其分配为相关部分的最右边（也会产生相关的成本由于作业而引起的隐含切换）。

抱歉，以上内容适用于一般问题 - “排序”可以朝任何方向。 （要选择一个方向，请从下面的最佳变量分配中选择相关的方向。）

Python代码：

def f(bits):
  set_bits = sum(bits)
  left_ones = 0
  best = len(bits)

  for i, bit in enumerate(bits):
    right_ones = set_bits - left_ones - bit
    left_zeros = i - left_ones
    right_zeros = len(bits) - i - 1 - right_ones

    # As rightmost 0
    best = min(best, bit + left_ones + right_zeros)
    # As rightmost 1
    best = min(best, (bit ^ 1) + left_zeros + right_ones)
    
    left_ones += bit

  return best

输出：

bit_sets = [
  [1,0,0,1,1], # 1
  [1,0,0,1,0,1], # 2
  [0,1,1,0,1,0], # 2
  [1,1,1,1], # 0
  [0,0,1,1], # 0
  [0,1,0,0,0], # 1
  [1,0,1,1,1] # 1
]

for bits in bit_sets:
  print(f(bits), bits)