給定一個有限的隨機位序列，如何確定產生排序序列所需的最小位切換次數（即任何和所有 0 都在任何和所有 1 之前）？
請注意，同質序列（例如0000000和1111111）被認為是按此定義排序的。
此外，這在技術上不是“排序”序列，因為元素是就地切換的，不限于與其他元素交換，有沒有比“排序”更好的詞來描述這個活動？
uj5u.com熱心網友回復：
令 Z(n) 為將前 n 位全部設定為 0 的成本。
令 X(n) 為“排序”前 n 位的最小成本。
我們有：
Z(0) = 0, X(0) = 0
如果第 i 位為 0：Z(i) = Z(i-1), X(i) = min( Z(i-1), X(i-1) 1 )
如果第 i 位為 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
uj5u.com熱心網友回復：
一個規范的動態程式是在 O(1) 時間和空間中評估每個位的兩種狀態：保持該位相同或切換它的成本，同時將其分配為相關部分的最右邊（也會產生相關成本由于分配而隱含的切換）。
抱歉，以上內容適用于一般問題 - “排序”可能在任一方向。（要選擇一個方向，請從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)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498195.html
下一篇：字串/陣列的列印能力