ROSALIND｜3-Way Partition (PAR3)

發表於 更新於

重新排列一個長度為 n 的數列為三個部分，使得各部分的數字分別小於、等於、大於原數列的首位數字。

Given: A positive integer $n \leq 10^5$ and an array $A[1..n]$ of integers from $-10^5$ to $10^5$.

Return: An array $B[1..n]$ such that it is a permutation of $A$ and there are indices $1 \leq q \leq r \leq n$ such that $B[i] < A[1]$ for all $1 \leq i \leq q-1$, $B[i] = A[1]$ for all $q \leq i \leq r$, and $B[i] > A[1]$ for all $r+1 \leq i \leq n$.

(https://rosalind.info/problems/par3/)

這題是 2-way partition 的延伸，我覺得最直觀的做法還是由左至右檢查輸入數列，再準備三個空數列分別儲存小於、等於、大於基準值的數字。檢查完所有數字後，依序合併這三個數列即完成排列。

1
2
3
4
5
6
7
8
9
10
def par3_build(l: list[int]) -> list[int]:
    left, mid, right = [], [], []  # 新增了 mid 來儲存與基準值相等的數字
    for i in range(1, len(l)):
        if l[i] > l[0]:
            right.append(l[i])
        elif l[i] < l[0]:
            left.append(l[i])
        else:
            mid.append(l[i])
    return left + mid + right

若不在意原數列的順序，可採用指標法重新排列數字。此方法延伸 2-way partition 的概念，使用兩組指標紀錄與基準值相當的數字範圍。實際執行時會進行兩次劃分，第一次劃分會移動right指標，區分大於、小於等於基準值的數字；第二次則會移動 left 指標，進一步區分小於、等於基準值的數字。

以 python 實作時只是添加一個步驟，我覺得非常容易聯想跟記憶。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def par3_nested(l: list[int]) -> list[int]:
    # 等於基準值的數字範圍
    left, right = 1, 1
    for i in range(1, len(l)):
        # 第一輪比較，區分 <= 和 > 基準值的數字
        # 把小於等於基準值的數字放到 right 的左邊
        if l[i] <= l[0]: 
            l[i], l[right] = l[right], l[i]
            # 第二輪比較，區分 < 和 = 基準值的數字
            # 把小於基準值的數字放到 left 的左邊
            if l[right] < l[0]:
                l[left], l[right] = l[right], l[left]
                left = left + 1
            right = right + 1
    l[0], l[left-1] = l[left-1], l[0]
    return l

最後一種則是稱為 dutch national flag (DNF) algorithm 的作法，名稱源自於由三等份色塊組成的荷蘭國旗。同樣使用 left 和 right 兩個指標，遇到小於基準值的數字時，left 向右移動，表示數字進入小於區；遇到大於基準值的數字時，right 向右移動，表示數字進入大於區，最終自然區分出三個區段。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def par3_dnf(l):
    left, right = 1, len(l) - 1
    i = 1
    while i <= right:
        if l[i] < l[0]:
            l[i], l[left] = l[left], l[i]
            left = left + 1
            i = i + 1
        elif l[i] > l[0]:
            l[i], l[right] = l[right], l[i]
            right = right - 1
        else:
            i = i + 1
    l[0], l[left - 1] = l[left - 1], l[0]

後兩種算法會打亂數字原本的順序，不太容易憑空想像測試資料，所以測試時可以從定義著手。假設數列已分成小於、等於和大於基準值的三個區塊，那麼每個區塊內的數字與基準值的關係都是相同的。換句話說，不會出現這個數字小於基準值，但下個數字大於基準值的狀況。

基於這項觀察，可以記錄數值與基準值關係的狀態。假設數值為 x，基準值為 p，則數值位於哪個區塊可以表示為 (x > p) - (x < p)，

  • -1：該數值理應要位於左側
  • 0：該數值理應要位於中央
  • 1：該數值理應要位於右側

在劃分好的數列裡， 左側數字的狀態值永遠小於右側數字的狀態值，所以出現倒序的時候就表示劃分出錯了。

1
2
3
4
5
6
7
8
def check_partition(arr: list[int], p: int) -> bool:
    prev = -1
    for x in arr:
        diff = (x > p) - (x < p) # left, mid, right = -1, 0, 1
        if diff < prev:
            return False
        prev = diff
    return True