Prueba de subconjuntos ordenados

Quiero probar si un conjunto ordenado es un subconjunto de un conjunto ordenado más grande. itertools.combinations tuplas e itertools.combinations :

 def subset_test(a, b): return a in itertools.combinations(b, len(a)) 

Por ejemplo,

 >>> subset_test((0, 1, 2), (0, 3, 1, 4, 2)) True >>> subset_test((0, 1, 2), (0, 3, 2, 4, 1)) False 

Funciona, pero es lento cuando pruebo tuplas grandes.

Simplemente puede usar un iterador para realizar un seguimiento de la posición en B

 >>> A = (0, 1, 2) >>> B = (0, 3, 1, 4, 2) >>> b_iter = iter(B) >>> all(a in b_iter for a in A) True 

Forma simple de hacer esto

 >>> a = (0, 1, 2) >>> b = (0, 3, 1, 4, 2) >>> filter(set(a).__contains__, b) == a True 

Para una mayor eficiencia de uso itertools

 >>> from itertools import ifilter, imap >>> from operator import eq >>> all(imap(eq, ifilter(set(a).__contains__, b), a)) True 

Esto debería empezar

 >>> A = (0, 1, 2) >>> B = (0, 3, 1, 4, 2) >>> b_idxs = {v:k for k,v in enumerate(B)} >>> idxs = [b_idxs[i] for i in A] >>> idxs == sorted(idxs) True 

Si la comprensión de la lista arroja un KeyError , entonces obviamente la respuesta también es False

Aquí hay un enfoque de tiempo lineal (en el conjunto más largo) que no requiere ningún hash. Aprovecha el hecho de que, dado que ambos conjuntos están ordenados, no es necesario volver a comprobar los elementos anteriores del conjunto:

 >>> def subset_test(a, b): ... b = iter(b) ... try: ... for i in a: ... j = b.next() ... while j != i: ... j = b.next() ... except StopIteration: ... return False ... return True ... 

Algunas pruebas:

 >>> subset_test((0, 1, 2), (0, 3, 1, 4, 2)) True >>> subset_test((0, 2, 1), (0, 3, 1, 4, 2)) False >>> subset_test((0, 1, 5), (0, 3, 1, 4, 2)) False >>> subset_test((0, 1, 4), (0, 3, 1, 4, 2)) True 

Estoy bastante seguro de que esto es correcto, avíseme si ve algún problema.

Esto debería ser bastante rápido, pero tengo uno más rápido en mente, espero tenerlo pronto:

 def is_sorted_subset(A, B): try: subset = [B.index(a) for a in A] return subset == sorted(subset) except ValueError: return False 

Actualización: aquí está el más rápido que prometí.

 def is_sorted_subset(A, B): max_idx = -1 try: for val in A: idx = B[max_idx + 1:].index(val) if max(idx, max_idx) == max_idx: return False max_idx = idx except ValueError: return False return True 

Que hay de esto

 >>> a = (0, 1, 2) >>> b = (0, 3, 1, 4, 2) >>> set(a).issubset(set(b)) True 

En este ejemplo, a y b tienen elementos ordenados y únicos y verifica si a es un subconjunto de b. ¿Esto es lo que quieres?

EDITAR:

Según @Marcos da Silva Sampaio: “Quiero probar si A es un subconjunto del conjunto B ordenado”.

No sería el caso de:

 >>> a = (2, 0, 1) >>> b = (0, 3, 1, 4, 2) >>> set(b).issuperset(a) True 

En este caso, el orden de un no importa.