17.2.1: Iteradores Python
- Page ID
- 117348
Todos los lenguajes de programación permiten el bucle. Una forma común de bucle es aquella en la que se ejecutan una serie de instrucciones para cada valor de alguna variable de índice, comúnmente para valores entre dos enteros. Python permite un poco más de generalidad al tener estructuras llamadas “iteradores” sobre las cuales se puede hacer un bucle. Un iterador puede ser tan simple como una lista, como [0,1,2,3]
, pero también puede ser un conjunto de potencia de un conjunto finito, como vemos a continuación, o las claves en un diccionario, que se describe en la siguiente sección.
Conteo de subconjuntos
Supongamos que queremos contar el número de subconjuntos de\(\{0,1,2,...,9\}\) que no contienen elementos adyacentes. Primero, definiremos nuestro universo y su conjunto de poder. El plan será definir una función que determine si un subconjunto es “válido” en el sentido de que no contiene elementos adyacentes. Después iteraremos sobre los subconjuntos, contando los válidos. Sabemos que el número de todos los subconjuntos será de 2 elevado al número de elementos en los\(U\text{,}\) que estaría\(2^{10}=1024\text{,}\) pero vamos a comprobar.
U=Set(range(10)) power_set=U.subsets() len(power_set)
El chequeo de validez en este caso es muy sencillo. Para cada elemento,\(k\text{,}\) de un conjunto,\(B\text{,}\) nos preguntamos si su sucesor, también\(k+1\text{,}\) está en el conjunto. Si nunca obtenemos una respuesta de “Verdadero” entonces consideramos válido el conjunto. Esta función podría editarse para definir la validez de otras formas para responder diferentes preguntas de conteo. Siempre es una buena idea probar tus funciones, así que probamos dos pruebas, una con un conjunto válido y otra con una inválida.
def valid(B): v=true for k in B: if k+1 in B: v=false break return v [valid(Set([1,3,5,9])),valid(Set([1,2,4,9]))]
Finalmente hacemos el conteo sobre nuestro conjunto de potencia, incrementando la variable de conteo con cada conjunto válido.
count=0 for B in power_set: if valid(B): count+=1 count