Parece que desea asegurarse de que el último "fragmento" esté cerrado al final de la lista. Esto debería hacer eso:

 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

Esto es O(n) , verifica cada elemento solo una vez, por lo que no pagará un costo por su start not in lst verificación que es costosa para largas listas de entrada.

Mutar la lista con pop(0) es costoso y no es necesario.

Podría usar index ... esto puede ser particularmente rápido cuando los fragmentos son grandes:

 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

A continuación se muestra una solución recursiva alternativa al problema. Básicamente, solo verifica si el siguiente objetivo está en la lista y salta a ese índice para verificar nuevamente. No soy un experto aquí, pero quería intentar y contribuir de una manera diferente a resolver la pregunta.

 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))

¿Qué tal esto? Crear un iter de la lista y buscar en ese iterador hasta que se encuentre el next elemento coincidente. Tenga en cuenta que esto podría fallar si None puede ser un elemento de la lista; entonces debería definir y comparar con un centinela 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

Dado que en realidad no necesitamos el valor devuelto por next , también podemos usar any en su lugar, al mismo tiempo que solucionamos el problema del elemento default . Como next , any consumirá el iterador hasta el elemento coincidente, si lo hay:

 def is_valid(lst): it = iter(lst) for x in it: if not any(y == x for y in it): return False return True

Esto se puede acortar aún más usando all en lugar del bucle for externo:

 def is_valid(lst): it = iter(lst) return all(any(y == x for y in it) for x in it)

Y esto finalmente se puede reducir a lo igualmente críptico e intrigante:

 def is_valid(lst): it = iter(lst) return all(x in it for x in it)

En todos los sentidos, cada elemento se visita exactamente una vez, la lista original no se cambia, hay poco o ningún espacio adicional y, en mi humilde opinión, es incluso algo fácil de leer y comprender.

Esto nunca se trató de velocidad, pero de todos modos: aquí hay algunos puntos de referencia de las diferentes soluciones (y algunas variaciones más), ejecutando los casos de prueba de la pregunta, así como dos listas aleatorias de 1,000 enteros, uno válido y otro inválido, 10,000 veces, en 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

Por supuesto, todos son O(n). Con las largas listas de 1000 elementos, la solución que usa el index es la más rápida, pero la que tiene una x in it es tan mala. any solución se queda un poco atrás, pero es tan rápida (o lenta) como la next cuando se usa un generador con condition , pero aún más lenta for cuando se usan bucles simples. Con solo las listas de prueba cortas, es un poco diferente: aquí, las soluciones que usan un iterador y for-for-else y for-in son las más rápidas por bastante margen.

Aquí está mi opinión sobre el problema. He optimizado la legibilidad, no la velocidad (manteniéndolo en O (n) por supuesto):

 def is_valid(sequence): iterator = iter(sequence) for element in iterator: for other in iterator: if element == other: break else: return False return True

Cada iteración del bucle exterior corresponde a un fragmento. Cuando nos quedamos sin elementos aquí, terminamos la secuencia en un borde de fragmento y podemos return True . De lo contrario, recorremos el iterador hasta que encontremos un elemento coincidente. Si nos quedamos sin elementos (un bucle for que "naturalmente" termina, sin break , va a su else ) return False .

Y aquí hay otro que usa itertools . No lo preferiría a la solución anterior, principalmente debido al uso arcano de next con un centinela:

 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

La pregunta no explica completamente si necesitamos una solución codiciosa o no.

Considere un ejemplo - [1, 2, 1, 1]

si consideramos un enfoque codicioso, la solución encontrará la primera secuencia como [1, 2, 1] y se quedará con [1] . Y por lo tanto, devolverá Falso.

Pero sin un enfoque codicioso, la solución considerará [1, 2, 1, 1] como una secuencia completa y devolverá True.

Ejecuté la solución proporcionada por usted y devuelve False, por lo que asumo que necesitamos un enfoque codicioso.

Entonces, aquí hay una posible solución:

 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([]))

Un breve intento de crear una solución para esto:

 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)

Si bien no creo que este sea el método más rápido, creo que es un método lo suficientemente interesante como para incluirlo aquí. Además, esto se puede optimizar un poco más eliminando las líneas:

 if firstChar not in input: return False

Y coloque el código en un bloque try/except, así:

 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

ya que este código daría un ValueError si el índice no existe

No he probado la diferencia de velocidad exacta en este momento, pero estoy seguro de que no es el método más rápido, pero debería ser relativamente decente en cuanto a velocidad.