The Goal
I would like to get the ranges where values are not None in a list, so for example:
test1 = [None, 0, None]
test2 = [2,1,None]
test3 = [None,None,3]
test4 = [1,0,None,0,0,None,None,1,None,0]
res1 = [[1,1]]
res2 = [[0,1]]
res3 = [[2,2]]
res4 = [[0,1],[3,4],[7,7],[9,9]]
What I have tried
This is my super lengthy implementation, which does not perfectly work...
def get_not_None_ranges(list_):
# Example [0, 2, None, 1, 4] -> [[0, 1], [3, 4]]
r = []
end_i = len(list_)-1
if list_[0] == None:
s = None
else:
s = 0
for i, elem in enumerate(list_):
if s != None:
if elem == None and end_i != i:
r.append([s,i-1])
s = i 1
if end_i == i:
if s > i:
r=r
elif s==i and elem == None:
r=r
else:
r.append([s,i])
else:
if elem != None:
s = i
if end_i == i:
if s > i:
r=r
else:
r.append([s,i])
return r
As you can see the results are sometimes wrong:
print(get_not_None_ranges(test1))
print(get_not_None_ranges(test2))
print(get_not_None_ranges(test3))
print(get_not_None_ranges(test4))
[[1, 2]]
[[0, 2]]
[[2, 2]]
[[0, 1], [3, 4], [6, 5], [7, 7], [9, 9]]
So, I was wondering if you guys know a much better way to achieve this?
CodePudding user response：
Use itertools.groupby:
from itertools import groupby
test1 = [None, 0, None]
test2 = [2, 1, None]
test3 = [None, None, 3]
test4 = [1, 0, None, 0, 0, None, None, 1, None, 0]
def get_not_None_ranges(lst):
result = []
for key, group in groupby(enumerate(lst), key=lambda x: x[1] is not None):
if key:
index, _ = next(group)
result.append([index, index sum(1 for _ in group)])
return result
print(get_not_None_ranges(test1))
print(get_not_None_ranges(test2))
print(get_not_None_ranges(test3))
print(get_not_None_ranges(test4))
Output
[[1, 1]]
[[0, 1]]
[[2, 2]]
[[0, 1], [3, 4], [7, 7], [9, 9]]
CodePudding user response：
A non-groupby solution that doesn't need extra treatment for the last group:
def get_not_None_ranges(lst):
result = []
it = enumerate(lst)
for i, x in it:
if x is not None:
first = last = i
for i, x in it:
if x is None:
break
last = i
result.append([first, last])
return result
Whenever I find the first of a non-None streak, I use an inner loop to right away run to the last of that streak. To allow both loops to use the same iterator, I store it in a variable.
CodePudding user response：
You just need to iterate over the list, and check for two conditions:
- If the previous element is
Noneand the current element is notNone, start a new "range". - If the previous element is not
Noneand the current element isNone, end the currently active range at the previous index.
def gnnr(lst):
all_ranges = []
current_range = []
prev_item = None
for index, item in enumerate(lst):
# Condition 1
if prev_item is None and item is not None:
current_range.append(index)
# Condition 2
elif prev_item is not None and item is None:
current_range.append(index - 1) # Close current range at the previous index
all_ranges.append(current_range) # Add to all_ranges
current_range = [] # Reset current_range
prev_item = item
# If current_range isn't closed, close it at the last index of the list
if current_range:
current_range.append(index)
all_ranges.append(current_range)
return all_ranges
Calling this function with your test cases gives the expected output:
[[1, 1]]
[[0, 1]]
[[2, 2]]
[[0, 1], [3, 4], [7, 7], [9, 9]]
CodePudding user response：
Well, we can solve this by using classic sliding window approach.
Here is the solution which works fine:
def getRanges(nums):
left = right = 0
ranges, n = [], len(nums)
while right < n:
while left < n and nums[left] == None:
left = 1
right = 1
while right < n and nums[right] != None:
right = 1
if right >= n:
break
ranges.append([left, right - 1])
left = right = right 1
return ranges [[left, right - 1]] if right - 1 >= left else ranges
Lets test it:
test = [
[1, 0, None, 0, 0, None, None, 1, None, 0],
[None, None, 3],
[2, 1, None],
[None, 0, None],
]
for i in test:
print(getRanges(i))
Output:
[[0, 1], [3, 4], [7, 7], [9, 9]]
[[2, 2]]
[[0, 1]]
[[1, 1]]
CodePudding user response：
Give it a try. Code uses Type Hint and a named tuple in order to increase readablity.
from typing import NamedTuple,List,Any
class Range(NamedTuple):
left: int
right: int
def get_ranges(lst: List[Any]) -> List[Range]:
ranges : List[Range] = []
left = None
right = None
for i,x in enumerate(lst):
is_none = x is None
if is_none:
if left is not None :
right = right if right is not None else left
ranges.append(Range(left,right))
left = None
right = None
else:
if left is None:
left = i
else:
right = i
if left is not None:
right = right if right is not None else left
ranges.append(Range(left,right))
return ranges
data = [[1,0,None,0,0,None,None,1,None,0],[None,None,3],[2,1,None],[None, 0, None]]
for entry in data:
print(get_ranges(entry))
outut
[Range(left=0, right=1), Range(left=3, right=4), Range(left=7, right=7), Range(left=9, right=9)]
[Range(left=2, right=2)]
[Range(left=0, right=1)]
[Range(left=1, right=1)]
CodePudding user response：
Using first and last of each group of not nones:
from itertools import groupby
def get_not_None_ranges(lst):
result = []
for nones, group in groupby(enumerate(lst), lambda x: x[1] is None):
if not nones:
first = last = next(group)
for last in group:
pass
result.append([first[0], last[0]])
return result
CodePudding user response：
Here's my example. It is definitely NOT the most efficient way, but I think it is more intuitive and you can optimize it later.
def get_not_None_ranges(list_: list):
res = []
start_index = -1
for i in range(len(list_)):
e = list_[i]
if e is not None:
if start_index < 0:
start_index = i
else:
if start_index >= 0:
res.append([start_index, i - 1])
start_index = -1
if start_index >= 0:
res.append([start_index, len(list_) - 1])
return res
The main thought of this function:
- start_index is initialized with -1
- When we meet not None element, set start_index to its index
- When we meet None, save [start_index, i - 1 (since the previous element is the end of the session)]. Then set start_index back to -1.
- When we meet None but start_index is -1, we need to do nothing since we have not met the not None element this turn. For the same reason, do nothing when we meet not None when start_index > 0.
- When the loop end but start_index still larger than 0, it means we haven't record this valid turn. So we need to do that manually.
I think it may be a little bit complex, it may help to paste the code above and debug it line by line in a debugger.
CodePudding user response：
How about:-
test1 = [None, 0, None]
test2 = [2, 1, None]
test3 = [None, None, 3]
test4 = [1, 0, None, 0, 0, None, None, 1, None, 0]
def goal(L):
r = []
_r = None
for i, e in enumerate(L):
if e is not None:
if _r:
_r[1] = i
else:
_r = [i, i]
else:
if _r:
r.append(_r)
_r = None
if _r:
r.append(_r)
return r
for _l in [test1, test2, test3, test4]:
print(goal(_l))