窮舉+判斷函數求Lis

窮舉+判斷函數求Lis

---

程式碼

def is_increasing(subset):
    """判斷子集是否為遞增"""
    return all(subset[i] < subset[i + 1] for i in range(len(subset) - 1))

def all_increasing_subsets(arr):
    n = len(arr)
    subsets = []

    # 透過位元表示法窮舉所有子集
    for i in range(2**n):
        subset = []
        for j in range(n):
            if i & (1 << j):  # 檢查第 j 位是否為 1
                subset.append(arr[j])
        # 僅保留遞增子集
        if is_increasing(subset):
            subsets.append(subset)

    return subsets

# 測試輸入
arr = [2, 4, 6, 5, 3, 1]

# 計算所有遞增子集
increasing_subsets = all_increasing_subsets(arr)

# 輸出結果
print("所有遞增子集:")
for subset in increasing_subsets:
    print(subset)

---

程式邏輯

1. 判斷函數 is_increasing：

   • 接收子集作為輸入。
   • 使用 all() 函數檢查子集中每對相鄰元素是否滿足遞增條件 subset[i] < subset[i + 1]。
   • 如果所有條件都滿足，則返回 True，否則返回 False。

2. 修改子集生成邏輯：

   • 在原先生成所有子集的基礎上，加入對 is_increasing 的檢查。
   • 僅保留符合遞增條件的子集。

3. 結果存儲：

   • 將所有遞增子集存入 subsets，最後返回。

---

範例輸出

對於輸入 arr = [2, 4, 6, 5, 3, 1]：

所有遞增子集:
[]
[2]
[4]
[6]
[2, 4]
[2, 6]
[4, 6]

---

關鍵點

1. 效率考量：

   • 總共生成 (2^n) 個子集，對每個子集進行遞增檢查，總時間複雜度為 (O(n \cdot 2^n))。

2. 可擴展性：

   • 判斷函數 is_increasing 可修改為其他條件（如遞減、相等等），滿足不同需求。

3. 適用場景：

   • 適合處理需要過濾特定條件的子集問題。