查找串列中存在的給定長度的唯一子串列的最佳方法？

因此，我構建了一個函式，用于查找i給定串列中存在的所有長度的唯一子串列。

例如，如果你有list=[0,1,1,0,1]and i=1，你就會得到[1,0]。如果i=2，你得到[[0,1],[1,1],[1,0]]，但不是[0,0]因為雖然它是 和 的可能組合1，0但它不存在于給定串列中。代碼如下所示。

雖然代碼起作用，但我不認為它是最有效的。它依賴于查找所有可能的子串列并測驗每個子串列的存在，這在i> 4 時變得不切實際（例如串列長度為 100）。我希望我能得到幫助，找到一種更有效的計算方法。

我寫的代碼：

def present_sublists (l,of_length):
    """
    takes a given list of 1s and 0s and returns all the unique sublist of that
    string that are of a certain length
    """
    l_str=[str(int) for int in l]   #converts entries in input to strings
    l_joined="".join(l_str) #joins input into one strings, i.e. "101010"
    sublist_sets=set(list(itertools.combinations(l_joined,of_length)))
    #uses itertools to get all possible combintations of substrings, and then set
    #properties to removes duplicates
    pos_sublists=list(sublist_sets) #returns the set to a list
    sublists1=[]
    for entry in pos_sublists:         #returns the entries to a list
        sublists1.append(list(entry))
    for entry in sublists1:            #returns the "1"s and "0" to 1s and 0s
        for entry2 in entry:
            entry[entry.index(entry2)]=int(entry2)
    present_sublists=[]
    for entry in sublists1:            #tests whether the possible sublist is
                                       #present in the input list
        for x in range(len(l) - len(entry)   1):
            if entry not in present_sublists:
                if l[x: x   len(entry)] == entry:
                    present_sublists.append(entry)
    output=present_sublists
    return output

uj5u.com熱心網友回復：

給定您的代碼和示例，看起來您想要給定輸入的所有唯一連續子序列，如果是這樣，您不需要計算所有組合，也不需要在字串、串列、集合和字串之間移動，更不用說在事物上回圈多次，使用切片表示法足以獲得期望的結果

>>> [0,1,2,3,4][0:2]
[0, 1]
>>> [0,1,2,3,4][1:3]
[1, 2]
>>> [0,1,2,3,4][2:4]
[2, 3]
>>> [0,1,2,3,4][3:5]
[3, 4]
>>> 

適當使用切片中的索引可以讓我們獲得任何給定大小的所有連續子序列（示例中為 2）

現在為了使這更加自動化，我們制作了一個適當的 for 回圈

>>> seq=[0,1,2,3,4]
>>> size=2
>>> for i in range(len(seq)-size 1):
        print(seq[i:i size])

    
[0, 1]
[1, 2]
[2, 3]
[3, 4]
>>> 

現在我們知道如何獲取我們關心的所有子序列，我們專注于只獲取唯一的子序列，因為我們當然使用集合但串列不能在集合中，所以我們需要一些可以，所以一個元組就是答案（它基本上是一個不可變的串列），這就是你需要的一切，讓我們把它們放在一起：

>>> def sub_sequences(seq,size):
        """return a set with all the unique contiguous sub-sequences of the given size of the given input"""
        seq = tuple(seq) #make it into a tuple so it can be used in a set
        if size>len(seq) or size<0: #base/trivial case
            return set() #or raise an exception like ValueError
        return {seq[i:i size] for i in range(len(seq)-size 1)} #a set comprehension version of the previous mentioned loop

>>> sub_sequences([0,1,2,3,4],2)
{(0, 1), (1, 2), (2, 3), (3, 4)}
>>>
>>> #now lets use your sample
>>>
>>> sub_sequences([0,1,1,0,1],2)
{(0, 1), (1, 0), (1, 1)}
>>> sub_sequences([0,1,1,0,1],3)
{(1, 0, 1), (1, 1, 0), (0, 1, 1)}
>>> sub_sequences([0,1,1,0,1],4)
{(1, 1, 0, 1), (0, 1, 1, 0)}
>>> sub_sequences([0,1,1,0,1],5)
{(0, 1, 1, 0, 1)}
>>> 

uj5u.com熱心網友回復：

讓我們標記位 0、1、2、3，......

讓我們還定義一個函式f(len, n)，其中定義為在第一位出現f(len, n)的所有長度字串的集合。lenn

所以

f(0, n) = {''}  since you can always make the empty string
f(len, 0) = set() if len > 0

那么f(len, n)if的值是len > 0 and n > 0多少？它包含 inf(len, n - 1)中的所有內容，加上 in 包含f(len - 1, n - 1)附加l[n-1]到其中的所有內容。

f(of_length, len(l))您現在擁有合理高效地找到所需的一切。

uj5u.com熱心網友回復：

為了堅持你的功能足跡，我建議如下：

1. 遍歷每個子串列并將它們放入 set() 以確保唯一性
2. 子串列需要轉換為元組，因為串列不能被散列，因此不能按原樣放入集合中
3. 將集合中的結果元組轉換回所需的格式。

在創建新串列時，串列推導是最有效和 Pythonic 的選擇方式。

>>> def present_sublists(l,of_length):
...   sublists = set([tuple(l[i:i of_length]) for i in range(0,len(l) 1-of_length)])
...   return [list(sublist) for sublist in sublists]
...
>>> present_sublists([0,1,1,0,1], 1)
[[0], [1]]
>>> present_sublists([0,1,1,0,1], 2)
[[0, 1], [1, 0], [1, 1]]

標籤：Python 列表

上一篇：如何將字母轉換為數字？

下一篇：將串列與輸入進行比較