爲什麼我的for循環不工作？ （Python）

Question

是的，這是作業。我只是想明白爲什麼這似乎不起作用。

我試圖找到字母順序的字符串中最長的子字符串。我做了一個隨機字母的列表，並說長度是19.當我運行我的代碼時，它打印出索引0到17.（我知道這是因爲我從範圍中減去1）然而，當我離開時 - 1，它告訴我「字符串索引超出範圍」。爲什麼會發生？

s = 'cntniymrmbhfinjttbiuqhib' 
sub = '' 
longest = [] 

for i in range(len(s) - 1): 
    if s[i] <= s[i+1]: 
     sub += s[i] 
     longest.append(sub) 
    elif s[i-1] <= s[i]: 
     sub += s[i] 
     longest.append(sub) 
     sub = ' ' 
    else: 
     sub = ' ' 
print(longest) 
print ('Longest substring in alphabetical order is: ' + max(longest, key=len)) 

我也嘗試了一些其他的方法

如果我只是說：

for i in s: 

它拋出一個錯誤，說「字符串的索引必須是整數，不能海峽。 「這似乎是迭代字符串的一種更簡單的方法，但是如何以這種方式比較單個字母呢？

這是Python 2.7的方式。

編輯：我確定我的if/elif語句可以改進，但這是我能想到的第一件事。如果需要，我可以稍後回來。

Answer 1

我敢肯定，我的if/elif的語句可以改進，但是這是第 件事我能想到的。如果需要，我可以稍後回來。

@ or1426的解決方案會創建一個當前最長的已排序序列的列表，並在發現較長序列時將其複製到longest。這會在每次找到更長的序列時創建一個新列表，並附加到每個字符的列表中。這在Python中實際上非常快，但請參見下文。

@ Deej的解決方案將當前最長的已排序序列保留在字符串變量中，並且每當找到更長的子字符串（即使它是當前序列的延續）時，子字符串都會保存到列表中。該列表最後有全部排序的原始字符串的子字符串，最長的是通過調用max找到的。

這裏是一個更快的解決方案，只跟蹤當前最大序列的指數，當它發現一個字符不按排序順序只是更改最長：

def bjorn4(s): 
    # we start out with s[0] being the longest sorted substring (LSS) 
    longest = (0, 1) # the slice-indices of the longest sorted substring 
    longlen = 1   # the length of longest 
    cur_start = 0  # the slice-indices of the *current* LSS 
    cur_stop = 1 

    for ch in s[1:]:  # skip the first ch since we handled it above 
     end = cur_stop-1 # cur_stop is a slice index, subtract one to get the last ch in the LSS 
     if ch >= s[end]: # if ch >= then we're still in sorted order.. 
      cur_stop += 1 # just extend the current LSS by one 
     else: 
      # we found a ch that is not in sorted order 
      if longlen < (cur_stop-cur_start): 
       # if the current LSS is longer than longest, then.. 
       longest = (cur_start, cur_stop) # store current in longest 
       longlen = longest[1] - longest[0] # precompute longlen 

      # since we can't add ch to the current LSS we must create a new current around ch 
      cur_start, cur_stop = cur_stop, cur_stop+1 

    # if the LSS is at the end, then we'll not enter the else part above, so 
    # check for it after the for loop 
    if longlen < (cur_stop - cur_start): 
     longest = (cur_start, cur_stop) 

    return s[longest[0]:longest[1]] 

有多快？它幾乎是orl1426的兩倍，比deej快三倍。一如既往，取決於您的輸入。存在的排序子串的塊越多，上述算法與其他算法相比就越快。例如。上長度含有交替的100個隨機字符和100按順序字符100000的輸入字符串，我得到：

bjorn4: 2.4350001812 
or1426: 3.84699988365 
deej : 7.13800001144 

如果我將其更改爲交替的1000個隨機字符和1000排序字符，然後我得到：

bjorn4: 23.129999876 
or1426: 38.8380000591 
deej : MemoryError 

更新： 這裏是我的算法的進一步優化版本，與比較代碼：

import random, string 
from itertools import izip_longest 
import timeit 

def _randstr(n): 
    ls = [] 
    for i in range(n): 
     ls.append(random.choice(string.lowercase)) 
    return ''.join(ls) 

def _sortstr(n): 
    return ''.join(sorted(_randstr(n))) 

def badstr(nish): 
    res = "" 
    for i in range(nish): 
     res += _sortstr(i) 
     if len(res) >= nish: 
      break 
    return res 

def achampion(s): 
    start = end = longest = 0 
    best = "" 
    for c1, c2 in izip_longest(s, s[1:]): 
     end += 1 
     if c2 and c1 <= c2: 
      continue 
     if (end-start) > longest: 
      longest = end - start 
      best = s[start:end] 
     start = end 
    return best 

def bjorn(s): 
    cur_start = 0 
    cur_stop = 1 
    long_start = cur_start 
    long_end = cur_stop 

    for ch in s[1:]:  
     if ch < s[cur_stop-1]: 
      if (long_end-long_start) < (cur_stop-cur_start): 
       long_start = cur_start 
       long_end = cur_stop 
      cur_start = cur_stop 
     cur_stop += 1 

    if (long_end-long_start) < (cur_stop-cur_start): 
     return s[cur_start:cur_stop] 
    return s[long_start:long_end] 


def or1426(s): 
    longest = [s[0]] 
    current = [s[0]] 
    for char in s[1:]: 
     if char >= current[-1]: # current[-1] == current[len(current)-1] 
      current.append(char) 
     else:    
      current=[char] 
     if len(longest) < len(current): 
      longest = current 
    return ''.join(longest) 

if __name__ == "__main__": 
    print 'achampion:', round(min(timeit.Timer(
     "achampion(rstr)", 
     setup="gc.enable();from __main__ import achampion, badstr; rstr=badstr(30000)" 
    ).repeat(15, 50)), 3) 

    print 'bjorn:', round(min(timeit.Timer(
     "bjorn(rstr)", 
     setup="gc.enable();from __main__ import bjorn, badstr; rstr=badstr(30000)" 
    ).repeat(15, 50)), 3) 

    print 'or1426:', round(min(timeit.Timer(
     "or1426(rstr)", 
     setup="gc.enable();from __main__ import or1426, badstr; rstr=badstr(30000)" 
    ).repeat(15, 50)), 3) 

隨着輸出：

achampion: 0.274 
bjorn: 0.253 
or1426: 0.486 

改變數據是隨機的：

achampion: 0.350 
bjorn: 0.337 
or1426: 0.565 

和分類：

achampion: 0.262 
bjorn: 0.245 
or1426: 0.503 

「不，不，它不是死的，它是靜止狀態」

Answer 2

問題是行if s[i] <= s[i+1]:。如果i=18（你的循環的最終迭代沒有-1）。然後i+1=19超出界限。

請注意，行elif s[i-1] <= s[i]:也可能沒有做你想做的。當i=0我們有i-1 = -1。 Python允許負指數意味着從索引對象的後面開始計數，所以s[-1]是最近的列表中的字符（s [-2]將是倒數第二等）。

更簡單的方法來獲得一個和下一個字符是用zip同時切片串分別從第一和第二個字符計數。

zip是這樣的，如果你還沒有看到它之前：

>>> for char, x in zip(['a','b','c'], [1,2,3,4]): 
>>> print char, x 
'a' 1 
'b' 2 
'c' 3 

所以，你可以這樣做：

for previous_char, char, next_char in zip(string, string[1:], string[2:]): 

要重複的字符在所有的三元組，無需在搞亂結束。

但是有一個更簡單的方法來做到這一點。相反，在字符串中當前字符的字符串中的其他字符比較你應該alphabetised字符例如當前字符串中的最後一個字符進行比較：

s = "abcdabcdefa" 
longest = [s[0]] 
current = [s[0]] 
for char in s[1:]: 
    if char >= current[-1]: # current[-1] == current[len(current)-1] 
     current.append(char) 
    else:    
     current=[char] 
    if len(longest) < len(current): 
     longest = current 
print longest 

這樣就不必做任何花哨的索引。

Answer 3

好的，所以在閱讀你的回答並嘗試各種不同的東西之後，我終於想出了一個解決方案，它可以得到我需要的東西。這不是最漂亮的代碼，但它的工作原理。我敢肯定，提到的解決方案也會起作用，但我無法弄清楚。下面是我所做的：

s = 'inaciaebganawfiaefc' 
sub = '' 
longest = [] 
for i in range(len(s)): 
    if (i+1) < len(s) and s[i] <= s[i+1]: 
     sub += s[i] 
     longest.append(sub) 
    elif i >= 0 and s[i-1] <= s[i]: 
     sub += s[i] 
     longest.append(sub) 
     sub = '' 
    else: 
     sub = '' 
print ('Longest substring in alphabetical order is: ' + max(longest, key=len)) 

Answer 4

現在Deej有一個答案，我覺得在家庭作業發佈答案更舒服。
只是重新排序@迪吉的邏輯一點，你就可以簡化爲：

sub = '' 
longest = [] 
for i in range(len(s)-1): # -1 simplifies the if condition 
    sub += s[i] 
    if s[i] <= s[i+1]: 
     continue   # Keep adding to sub until condition fails 
    longest.append(sub) # Only add to longest when condition fails 
    sub = '' 

max(longest, key=len) 

但正如@thebjorn提到這個具有保持在列表中的每個分區上升（在內存中）的問題。您可以通過使用發電機解決這個問題，我只把其餘的在這裏爲教學目的：

def alpha_partition(s): 
    sub = '' 
    for i in range(len(s)-1): 
     sub += s[i] 
     if s[i] <= s[i+1]: 
      continue 
     yield sub 
     sub = '' 

max(alpha_partition(s), key=len) 

這當然不會是最快的解決方法（串建設和索引），但它是相當簡單的改變，使用zip包避免索引到字符串和索引，以避免串建設和加法：

from itertools import izip_longest # For py3.X use zip_longest 
def alpha_partition(s): 
    start = end = 0 
    for c1, c2 in izip_longest(s, s[1:]): 
     end += 1 
     if c2 and c1 <= c2: 
      continue 
     yield s[start:end] 
     start = end 

max(alpha_partition(s), key=len) 

這應該是由於發電機開銷非常有效地運作，是隻比從@thebjorn迭代索引方法稍微慢一些。

使用S * 100
alpha_partition()：1000個循環，最好的3：每循環448微秒
@thebjorn：1000個循環，最好的3：每次循環

389微秒作爲參考轉動發電機成迭代函數：

from itertools import izip_longest # For py3.X use zip_longest 
def best_alpha_partition(s): 
    start = end = longest = 0 
    best = "" 
    for c1, c2 in izip_longest(s, s[1:]): 
     end += 1 
     if c2 and c1 <= c2: 
      continue 
     if (end-start) > longest: 
      longest = end - start 
      best = s[start:end] 
     start = end 
    return best 
best_alpha_partition(s) 

best_alpha_partition()：1000個循環，最好的3：每圈306微秒

我個人比較喜歡的根因爲您可以使用完全相同的生成器來查找最小值，前5個等等，可重複使用，而迭代函數只能做一件事。