如何提高增加子序列算法以合併未排序的數組？

Question

我一直在努力解決增加的子序列問題。我提出的算法目前只解決了排序後的數組。我在python 3.5中編寫我的代碼。此問題在Leetcode上託管。

在遞增子問題，我給定一個整數數組，任務是找到給定陣列的所有不同的可能增加子序列，和增加的子序列的長度應至少爲2

實施例：

輸入 - [4,6,7,7]

輸出 - [[4,6]，[4,7]，[4,6,7]，[4,6,7， 7]，[6,7]，[6,7,7]，[7,7]，[4,7,7]]

這是我的解決這個問題的工作代碼：

array = [4,6,7,7] 

def incrSubseq(array): #Only works for sorted arrays. 
    res = [[]] 
    ans = [] 
    for num in array: 
     res += [item + [num] for item in res if (item+[num] not in res)] 
    for values in res: 
     if len(values)>1: 
      ans = ans + [values] 
    print(ans) 
incrSubseq(array) 

此代碼是如何工作的？

1. 它開始通過初始化一個結果變量res（列表的列表） 其通過一個空列表初始化。
2. 然後，我遍歷給定的整數數組array，它按照排序順序，將每個元素添加到列表中，從而找到可以形成的所有子集。列表理解中的if語句過濾掉重複的項目，因此只保留列表的一個副本。
3. 然後我過濾所有其具有的長度大於1

因此，解決該問題的陣列。

現在，我在這裏失蹤的是解決未排序數組的方法。據我的理解，我需要檢查的方式，當我試圖添加一個元素到res它應該大於或等於它之前的項目。

res += [item + [num] for item in res if (item+[num] not in res) and (item <= num)]它在空列表中給出。

關於改進代碼的任何建議？

Answer 1

您的想法完全正確！只需檢查item中的最後一個元素是否比之前更小（可能允許相等，具體取決於定義的增量如何）。

所以你添加檢查item[-1] <= num（用-1你得到了Python中數組的最後一個元素）。

現在還有一個問題。 item可能爲空，您會收到錯誤消息。所以你只想要<=檢查，如果item中至少有一個元素。 下面是一個使用布爾操作短路的奇特解決方案，其中(len(item) == 0 or item[-1] <= num)在沒有元素的情況下爲真（然後第二個檢查是不是執行），或者item中至少有一個元素，並且檢查它是否較小或相等。

array = [4,6,3,7] 

def incrSubseq(array): # Works for sorted arrays too :) 
    res = [[]] 

    for num in array: 
     res += [item + [num] for item in res if (item + [num] not in res 
               and (len(item) == 0 or item[-1] <= num))] 

    return [values for values in res if len(values) > 1] 

print(incrSubseq(array)) 

---

Short circuiting意味着一個布爾表達式僅被評估，直到可確定其最終值。例如False and 1/0因爲and是False如果它的兩個參數的任何是False不會引發異常。所以當評估從左到右時，它不會計算出1/0。

略偏verbously上述算法的內部部分可以被寫爲：

for num in array: 
    for item in res: 
     if item + [num] not in res: 
      if len(item) == 0: 
       # item is empty. 
       res += [num] 
      else: 
       # item is not empty so we check its last element. 
       if item[-1] <= num: 
        res += item + [num] 
       else: 
        # We got something increasing here. Do not add. 
        pass 

---

的複雜算法的可以如隨後進行計算。假設最壞情況輸入爲[1, 2, ..., n]。然後，在各步驟所得的子序列的數量加倍，從而導致O(2^n)子序列和O(n * 2^n)的輸出大小。每一種算法至少需要這麼長時間（如果你真的有興趣輸出每一個序列 - 如果你想要生成所有的函數式語言和懶惰的函數式語言評估風格，這並不重要）。

這種算法雖然花費更長的時間。我們必須爲輸出中的每個子序列做的主要工作是檢查它是否是重複的，並且天真item + [num] not in res。比較長度爲m的兩個列表需要O(m)最壞的情況。考慮到最後的num需要超過總運行時間的一半，我們只是在這裏用它作爲一個很好的近似值。這意味着檢查最後2^(n-1)創建的子序列需要O(2^(n-1) * 2^(n-1) * n) = O(n * 4^n)，因爲您檢查每個舊的每個新序列。隨着prefix tree爲數據結構由此可以減少到只有O(2^n)，因爲這檢查是否有新的序列是有效的只是需要O(1)。遍歷樹實際寫下所有解決方案需要再次O(2^n * n)。

旁註：如果你喜歡在Python函數式編程退房syntax_sugar_python，