为什么我的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个等等，可重复使用，而迭代函数只能做一件事。