通过切换位"sort"位序列的最快方法

Question

给定一个有限随机的位序列，如何才能确定产生排序序列(即任何和所有0都在任何和所有1之前)所需的最小位切换数?

注意，齐次序列(如0000000和1111111)被认为是按此定义排序的。

而且，这不是技术上的"排序"。由于元素是就地切换的，并不局限于与其他元素交换，所以还有比"排序"更好的词来描述这个活动吗?

Answer 1

设Z(n)为前n位全为0的代价

设X(n)为"排序"的最小代价;前n位

我们:

Z(0) = 0 X(0) = 0

如果第i = 0: Z Z(张),(我)= X (i) = min (Z(张),X(张)+ 1)

如果第i个比特是1:Z (i) = Z(张)+ 1,X (i) = X(张)

答案是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)时间和空间内计算每个位的两种状态:保持位不变或将其切换，同时将其赋值为相关部分的最右侧的成本(也会产生由于赋值而隐含的切换的相关成本)。

对不起，上面的内容适用于一般的问题——其中"sorted"两个方向都有可能。(要选择方向，请从下面的best变量赋值中选择相关方向)

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)