检查列表是否是有效的块序列
Check if list is valid sequence of chunks
我想检查一个列表是否是一个有效的块序列，其中每个块都以某个值开头并以相同值的下一次出现结束。例如，这是三个块的有效序列：
lst = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]
\___________/ \_____/ \_______________________/
而这是无效的：
lst = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]
\___________/ \_____/ \_____ ... missing the 2 to end the chunk
我有一个解决方案，但它很糟糕。你看到更好的东西了吗？
def is_valid(lst):
while lst:
start = lst.pop(0)
if start not in lst:
return False
while lst[0] != start:
lst.pop(0)
lst.remove(start)
return True
# Tests, should print: True, False, True, False, True
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]))
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]))
print(is_valid(['I', 'N', 'O', 'A', 'I', 'L', 'L', 'T', 'R', 'X', 'I', 'I', 'N', 'X', 'F', 'T']))
print(is_valid(['T', 'I', 'N', 'I', 'X', 'R', 'O', 'F', 'T', 'I', 'N', 'I', 'X', 'L', 'L', 'A']))
print(is_valid([]))
您似乎想确保最后一个“块”在列表末尾关闭。这应该这样做：
def is_valid(lst):
search = None
paired = True
for item in lst:
if paired:
search = item
paired = False
elif search == item:
paired = True
return paired
这是 O(n)，每个元素只检查一次，因此您不会为长输入列表昂贵的 start not in lst 检查支付费用。
用 pop(0) 改变列表代价高昂且不需要。
您可以使用 index...当块很大时，这可能会特别快：
def is_valid(lst):
i = 0
n = len(list)
while i < n:
try:
i = lst.index(lst[i], i + 1) + 1
except:
return False
return True
下面是该问题的替代递归解决方案。基本上只是检查下一个目标是否在列表中，然后跳到该索引再次检查。我不是这里的专家，但想尝试并贡献一种不同的方式来解决这个问题。
def is_valid(
input_list: list,
target_index: int = 0):
# If we have only one element remaining, or if an empty list is passed initially, there cannot be a pair.
if len(input_list) <= 1:
return False
target = input_list[target_index]
search_range = input_list[target_index + 1 :]
# print(f"target index: {target_index}")
# print(f"target: {target}")
# print(f"search range: {search_range}")
# print("-------------------------------")
if target in search_range:
found_target_sublist_index = search_range.index(target)
# Plus 2: two indexes start at 0 -> off by two
next_target_index = target_index + found_target_sublist_index + 2
if next_target_index == len(input_list):
return True
return is_valid(input_list, next_target_index)
else:
return False
test_one = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]
test_two = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]
test_three = ['I', 'N', 'O', 'A', 'I', 'L', 'L', 'T', 'R', 'X', 'I', 'I', 'N', 'X', 'F', 'T']
test_four = ['T', 'I', 'N', 'I', 'X', 'R', 'O', 'F', 'T', 'I', 'N', 'I', 'X', 'L', 'L', 'A']
print(is_valid(test_one))
print(is_valid(test_two))
print(is_valid(test_three))
print(is_valid(test_four))
怎么样，从列表中创建一个 iter 并在该迭代器上向前搜索，直到找到 next 匹配元素。请注意，这可能会失败，因为 None 可以是列表的一个元素；那么您应该定义并与哨兵进行比较 obj = object().
def is_valid(lst):
it = iter(lst)
for x in it:
if next((y for y in it if y == x), None) is None:
return False
return True
由于我们实际上不需要next返回的值，所以我们也可以直接使用any代替，同时解决了default元素的问题。像 next 一样，any 将消耗迭代器直到匹配元素（如果有的话）：
def is_valid(lst):
it = iter(lst)
for x in it:
if not any(y == x for y in it):
return False
return True
这可以使用 all 而不是外部 for 循环进一步缩短：
def is_valid(lst):
it = iter(lst)
return all(any(y == x for y in it) for x in it)
而这个最终可以简化为同样神秘和有趣的：
def is_valid(lst):
it = iter(lst)
return all(x in it for x in it)
每种方式，每个元素只被访问一次，原始列表没有改变，几乎没有额外的东西 space，恕我直言，它甚至有点容易阅读和理解。
这与速度无关，但无论如何：这里有一些不同解决方案的基准（以及更多变体），运行问题中的测试用例以及两个 1,000 个整数的随机列表，一有效一无效，10,000 次，于 Python 3.8.10:
# with long lists # only short test lists
1.52 is_valid_index 0.22 is_valid_index
3.28 is_valid_next 0.30 is_valid_next
2.78 is_valid_for_for_else 0.13 is_valid_for_for_else
5.26 is_valid_for_any 0.32 is_valid_for_any
5.29 is_valid_all_any 0.38 is_valid_all_any
3.42 is_valid_all_any_if 0.36 is_valid_all_any_if
2.02 is_valid_all_in 0.18 is_valid_all_in
1.97 is_valid_all_in_if 0.17 is_valid_all_in_if
1.87 is_valid_for_in 0.11 is_valid_for_in
当然都是O(n)。对于包含 1000 个元素的长列表，使用 index 的解决方案最快，但使用 x in it 的解决方案也不错。 any 解决方案有些落后，但在使用 时与 next 一样快（或慢），但仍然比使用普通 for 循环时慢。
只有简短的测试列表，它有点不同：在这里，使用一个迭代器和 for-for-else 和 for-in 的解决方案是最快的。
这是我对这个问题的看法。我优化了可读性，而不是速度（当然，同时将其保持在 O(n) 中）：
def is_valid(sequence):
iterator = iter(sequence)
for element in iterator:
for other in iterator:
if element == other:
break
else:
return False
return True
外循环的每次迭代对应一个块。当我们在这里没有元素时，我们在块边界处结束序列，我们可以 return True。否则，我们循环遍历迭代器，直到找到匹配的元素。如果我们 运行 没有元素（一个“自然”终止的 for 循环，没有 break，进入它的 else）我们 return False.
这是另一个使用 itertools 的方法。我不喜欢上面的解决方案，主要是因为 next 与哨兵的神秘用法：
from itertools import dropwhile
def is_valid(iterable):
iterator = iter(iterable)
sentinel = object()
for element in iterator:
if next(dropwhile(lambda x: x != element, iterator), sentinel) is sentinel:
return False
return True
这个问题没有完全解释我们是否需要贪婪的解决方案。
考虑一个例子 - [1, 2, 1, 1]
如果我们考虑贪婪的方法，解决方案将找到第一个序列为 [1, 2, 1] 并且将留下 [1] 。因此，将 return False.
但如果没有贪婪的方法，解决方案会将 [1, 2, 1, 1] 视为完整序列，并且 return 为真。
我 运行 你提供的解决方案 return 是错误的，所以我假设我们需要一个贪婪的方法。
因此，这是一种可能的解决方案：
def is_valid(lst):
to_find = None
for value in lst:
if to_find is None:
to_find = value
continue
if to_find is value:
to_find = None
return to_find is None
# Tests, should print: True, False, True, False, True
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]))
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]))
print(is_valid(['I', 'N', 'O', 'A', 'I', 'L', 'L', 'T', 'R', 'X', 'I', 'I', 'N', 'X', 'F', 'T']))
print(is_valid(['T', 'I', 'N', 'I', 'X', 'R', 'O', 'F', 'T', 'I', 'N', 'I', 'X', 'L', 'L', 'A']))
print(is_valid([]))
为此创建解决方案的简短尝试：
def isValid(input):
if len(input) == 0:
return True
firstChar = input.pop(0)
if firstChar not in input:
return False
input = input[input.index(firstChar)+1:]
isValid(input)
虽然我认为这不是最快的方法，但我认为这是一个足够有趣的方法，可以包含在此处。此外，可以通过删除以下行进一步优化：
if firstChar not in input:
return False
并将代码放在 try/except 块中，如下所示：
def isValid(input):
if len(input) == 0:
return True
firstChar = input.pop(0)
try:
input = input[input.index(firstChar)+1:]
isValid(input)
except:
return False
因为如果索引不存在，此代码将给出 ValueError
目前我还没有测试过确切的速度差异，但我敢肯定这不是最快的方法，但在速度方面应该是相对不错的。
我想检查一个列表是否是一个有效的块序列，其中每个块都以某个值开头并以相同值的下一次出现结束。例如，这是三个块的有效序列：
lst = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]
\___________/ \_____/ \_______________________/
而这是无效的：
lst = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]
\___________/ \_____/ \_____ ... missing the 2 to end the chunk
我有一个解决方案，但它很糟糕。你看到更好的东西了吗？
def is_valid(lst):
while lst:
start = lst.pop(0)
if start not in lst:
return False
while lst[0] != start:
lst.pop(0)
lst.remove(start)
return True
# Tests, should print: True, False, True, False, True
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]))
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]))
print(is_valid(['I', 'N', 'O', 'A', 'I', 'L', 'L', 'T', 'R', 'X', 'I', 'I', 'N', 'X', 'F', 'T']))
print(is_valid(['T', 'I', 'N', 'I', 'X', 'R', 'O', 'F', 'T', 'I', 'N', 'I', 'X', 'L', 'L', 'A']))
print(is_valid([]))
您似乎想确保最后一个“块”在列表末尾关闭。这应该这样做：
def is_valid(lst):
search = None
paired = True
for item in lst:
if paired:
search = item
paired = False
elif search == item:
paired = True
return paired
这是 O(n)，每个元素只检查一次，因此您不会为长输入列表昂贵的 start not in lst 检查支付费用。
用 pop(0) 改变列表代价高昂且不需要。
您可以使用 index...当块很大时，这可能会特别快：
def is_valid(lst):
i = 0
n = len(list)
while i < n:
try:
i = lst.index(lst[i], i + 1) + 1
except:
return False
return True
下面是该问题的替代递归解决方案。基本上只是检查下一个目标是否在列表中，然后跳到该索引再次检查。我不是这里的专家，但想尝试并贡献一种不同的方式来解决这个问题。
def is_valid(
input_list: list,
target_index: int = 0):
# If we have only one element remaining, or if an empty list is passed initially, there cannot be a pair.
if len(input_list) <= 1:
return False
target = input_list[target_index]
search_range = input_list[target_index + 1 :]
# print(f"target index: {target_index}")
# print(f"target: {target}")
# print(f"search range: {search_range}")
# print("-------------------------------")
if target in search_range:
found_target_sublist_index = search_range.index(target)
# Plus 2: two indexes start at 0 -> off by two
next_target_index = target_index + found_target_sublist_index + 2
if next_target_index == len(input_list):
return True
return is_valid(input_list, next_target_index)
else:
return False
test_one = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]
test_two = [2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]
test_three = ['I', 'N', 'O', 'A', 'I', 'L', 'L', 'T', 'R', 'X', 'I', 'I', 'N', 'X', 'F', 'T']
test_four = ['T', 'I', 'N', 'I', 'X', 'R', 'O', 'F', 'T', 'I', 'N', 'I', 'X', 'L', 'L', 'A']
print(is_valid(test_one))
print(is_valid(test_two))
print(is_valid(test_three))
print(is_valid(test_four))
怎么样，从列表中创建一个 iter 并在该迭代器上向前搜索，直到找到 next 匹配元素。请注意，这可能会失败，因为 None 可以是列表的一个元素；那么您应该定义并与哨兵进行比较 obj = object().
def is_valid(lst):
it = iter(lst)
for x in it:
if next((y for y in it if y == x), None) is None:
return False
return True
由于我们实际上不需要next返回的值，所以我们也可以直接使用any代替，同时解决了default元素的问题。像 next 一样，any 将消耗迭代器直到匹配元素（如果有的话）：
def is_valid(lst):
it = iter(lst)
for x in it:
if not any(y == x for y in it):
return False
return True
这可以使用 all 而不是外部 for 循环进一步缩短：
def is_valid(lst):
it = iter(lst)
return all(any(y == x for y in it) for x in it)
而这个最终可以简化为同样神秘和有趣的：
def is_valid(lst):
it = iter(lst)
return all(x in it for x in it)
每种方式，每个元素只被访问一次，原始列表没有改变，几乎没有额外的东西 space，恕我直言，它甚至有点容易阅读和理解。
这与速度无关，但无论如何：这里有一些不同解决方案的基准（以及更多变体），运行问题中的测试用例以及两个 1,000 个整数的随机列表，一有效一无效，10,000 次，于 Python 3.8.10:
# with long lists # only short test lists
1.52 is_valid_index 0.22 is_valid_index
3.28 is_valid_next 0.30 is_valid_next
2.78 is_valid_for_for_else 0.13 is_valid_for_for_else
5.26 is_valid_for_any 0.32 is_valid_for_any
5.29 is_valid_all_any 0.38 is_valid_all_any
3.42 is_valid_all_any_if 0.36 is_valid_all_any_if
2.02 is_valid_all_in 0.18 is_valid_all_in
1.97 is_valid_all_in_if 0.17 is_valid_all_in_if
1.87 is_valid_for_in 0.11 is_valid_for_in
当然都是O(n)。对于包含 1000 个元素的长列表，使用 index 的解决方案最快，但使用 x in it 的解决方案也不错。 any 解决方案有些落后，但在使用 next 一样快（或慢），但仍然比使用普通 for 循环时慢。
只有简短的测试列表，它有点不同：在这里，使用一个迭代器和 for-for-else 和 for-in 的解决方案是最快的。
这是我对这个问题的看法。我优化了可读性，而不是速度（当然，同时将其保持在 O(n) 中）：
def is_valid(sequence):
iterator = iter(sequence)
for element in iterator:
for other in iterator:
if element == other:
break
else:
return False
return True
外循环的每次迭代对应一个块。当我们在这里没有元素时，我们在块边界处结束序列，我们可以 return True。否则，我们循环遍历迭代器，直到找到匹配的元素。如果我们 运行 没有元素（一个“自然”终止的 for 循环，没有 break，进入它的 else）我们 return False.
这是另一个使用 itertools 的方法。我不喜欢上面的解决方案，主要是因为 next 与哨兵的神秘用法：
from itertools import dropwhile
def is_valid(iterable):
iterator = iter(iterable)
sentinel = object()
for element in iterator:
if next(dropwhile(lambda x: x != element, iterator), sentinel) is sentinel:
return False
return True
这个问题没有完全解释我们是否需要贪婪的解决方案。
考虑一个例子 - [1, 2, 1, 1]
如果我们考虑贪婪的方法，解决方案将找到第一个序列为 [1, 2, 1] 并且将留下 [1] 。因此，将 return False.
但如果没有贪婪的方法，解决方案会将 [1, 2, 1, 1] 视为完整序列，并且 return 为真。
我 运行 你提供的解决方案 return 是错误的，所以我假设我们需要一个贪婪的方法。
因此，这是一种可能的解决方案：
def is_valid(lst):
to_find = None
for value in lst:
if to_find is None:
to_find = value
continue
if to_find is value:
to_find = None
return to_find is None
# Tests, should print: True, False, True, False, True
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4, 5, 2]))
print(is_valid([2, 7, 1, 8, 2, 8, 1, 8, 2, 8, 4, 5, 9, 0, 4]))
print(is_valid(['I', 'N', 'O', 'A', 'I', 'L', 'L', 'T', 'R', 'X', 'I', 'I', 'N', 'X', 'F', 'T']))
print(is_valid(['T', 'I', 'N', 'I', 'X', 'R', 'O', 'F', 'T', 'I', 'N', 'I', 'X', 'L', 'L', 'A']))
print(is_valid([]))
为此创建解决方案的简短尝试：
def isValid(input):
if len(input) == 0:
return True
firstChar = input.pop(0)
if firstChar not in input:
return False
input = input[input.index(firstChar)+1:]
isValid(input)
虽然我认为这不是最快的方法，但我认为这是一个足够有趣的方法，可以包含在此处。此外，可以通过删除以下行进一步优化：
if firstChar not in input:
return False
并将代码放在 try/except 块中，如下所示：
def isValid(input):
if len(input) == 0:
return True
firstChar = input.pop(0)
try:
input = input[input.index(firstChar)+1:]
isValid(input)
except:
return False
因为如果索引不存在，此代码将给出 ValueError
目前我还没有测试过确切的速度差异，但我敢肯定这不是最快的方法，但在速度方面应该是相对不错的。