找出最大長度的子集

 找出列表 a 中的所有遞增子集，並從這些子集裡找出最大長度的子集。以下是程式碼的解釋：

1. 函式 check

def check(sa):
  n = len(sa)
  for i in range(1,n):
    if not(sa[i-1]<sa[i]):
      return False
  return True

這個函式 check 用於檢查給定的列表 sa 是否為嚴格遞增的序列。它逐一檢查每個相鄰的元素，如果前一個元素不小於後一個元素，就回傳 False，否則最後回傳 True，表示列表是嚴格遞增的。

2. 初始化列表 a 和計算其長度

a = [5,10,15,3,6,9,12]
n = len(a)

列表 a 包含一些數字，並計算它的長度 n。

3. 生成所有可能的二進位表示

d = []
for i in range(2**n):
  d.append(f'{i:0{n}b}')
print(d)

這段程式碼生成長度為 n 的所有二進位數字表示，並將這些表示結果儲存在列表 d 中。每個數字的二進位表示長度與列表 a 的長度相同，用來表示哪些元素會被選擇。

例如：如果 a 有 7 個元素，則會生成 128 個 (即 (2^7)) 由 0 和 1 組成的長度為 7 的字串。

4. 遍歷 d 中的每個二進位字串

tt = []
for i in d:
  t = []
  for j in range(n):
    if i[j]=='1':
      t.append(a[j])
  if check(t)==True:
    tt.append(t)  
print(tt)

這段程式碼用於根據每個二進位字串 i 來選擇 a 中的元素並生成子集：

• i[j]=='1' 表示選擇列表 a 的第 j 個元素並加入子集 t。
• 檢查生成的子集 t 是否為遞增序列，若是，則加入 tt 中。

最後，tt 包含所有的遞增子集。

5. 找出長度最長的遞增子集

ttl = [len(i) for i in tt]
maxl = max(ttl)
ttMax = [i for i in tt if len(i)==maxl]
print(ttMax)
print(maxl)

• ttl 是 tt 中每個子集的長度列表。
• maxl 是最長的子集的長度。
• ttMax 是所有長度等於 maxl 的子集，表示所有最大長度的遞增子集。

最後，輸出 ttMax（最大長度的遞增子集）和 maxl（這些子集的長度）。