Reputation: 31
For example, the initial list L=["by","article","circle","for","line","dance","effort"], and I want to take out the["article","circle","for","line"] as the result. Because the first alpha in L is (b,a,c,f,l,d,e) and the consequence of (a,c,f,l)is the longer than (d,e), so the result is ["article","circle","for","line"]. How to fix my code? I'm new so I'm so confusing with sorted() and nested loop.
def find_longest_consisting(test_case):
if not test_case:
return []
result = []
for i in range(len(test_case)):
for j in range(i + len(result) + 1):
substring = test_case[i:j]
if len(substring) != (j - i):
break
if sorted(substring) == list(substring):
result = substring
return result
test_cases = ["by","article","circle","for","line","dance","effort"]
test_result = find_longest_consisting(test_cases)
print(test_result)
Upvotes: 3
Views: 94
Reputation: 71574
A simple alternative to doing your own nested loop to check different subsets is to use itertools.combinations
:
from itertools import combinations
def longest_group(lst):
return max((
lst[a:b]
for a, b in combinations(range(len(lst)+1), 2)
if sorted(lst[a:b]) == lst[a:b]
), key=len) if lst else lst
If speed is more important than simplicity, the blazing-fast version would be to iterate over the list and track the range that corresponds to the longest sorted slice:
def longest_group(lst):
a, b, i = 0, 0, 0
for j, e in enumerate(lst[1:]):
if e < lst[j]:
if j - i > b - a:
a, b = i, j
i = j + 1
if len(lst) - i > b - a + 1:
a, b = i, len(lst)
return lst[a:b+1]
Upvotes: 2
Reputation: 147286
The fastest way to do this is by maintaining a "longest" list and comparing it's length to the current sublist when a change in ordering is encountered, assigning the current sublist to the longest if it is longer. This only requires one iteration over the list to get the result.
def longest_group(lst):
longest = []
current = lst[:1]
for i in range(1, len(lst)):
if lst[i][0] <= lst[i-1][0]:
if len(current) > len(longest):
longest = current
current = [lst[i]]
else:
current.append(lst[i])
if len(current) > len(longest):
longest = current
return longest
print(longest_group(["by","article","circle","for","line","dance","effort"]))
print(longest_group(["zoo","slack","egg"]))
Output:
['article', 'circle', 'for', 'line']
['zoo']
For your ["by","article","circle","for","line","dance","effort"]
list this is 10x faster than sorting all the combinations from the list. See https://rextester.com/JEJOAE73859 for a demo.
Upvotes: 3