Combinaciones, permutaciones y otras diversiones

By Ariel Ortiz

Elevator Pitch

Cuando se estudia probabilidad es común hablar de ciertas agrupaciones conocidas como combinaciones y permutaciones. En esta plática mostraré el poder y la elegancia de las listas por comprensión con el fin de diseñar e implementar funciones en Python que permitan generar este tipo de agrupaciones.

Description

Supongamos que tenemos los siguientes dos problemas:

  • Estoy en una heladería y quiero comprar un cono con dos bolas de helado de sabores distintos. La heladería cuenta con los siguientes sabores de helado: chocolate, fresa, nuez y vainilla. ¿De qué maneras diferentes puedo escoger los dos sabores de mi cono?
  • Tenemos las siguientes tres letras: i, o, r. ¿Qué palabras podemos formar usando solamente esas tres letras? Supongamos que no nos importa que algunas de las palabras formadas no existan en el idioma español.

El problema de los helados es un problema de combinaciones: deseamos determinar las formas de agrupar los elementos de un conjunto en donde no importa el orden en que se colocan dichos elementos. Un cono con helado de fresa y chocolate lo consideramos igual a uno con chocolate y fresa. Por otro lado, el problema de las letras es un problema de permutaciones: a diferencia de las combinaciones, aquí el orden sí nos interesa. No es lo mismo “rio” que “oir”.

Tradicionalmente, muchos libros de probabilidad comienzan con una descripción de cómo calcular el número de combinaciones y permutaciones de un cierto conjunto de objetos. No obstante, si lo que nos interesa es obtener un listado con dichas agrupaciones es muy probable que estos libros no expliquen la manera de hacerlo. Python cuenta con el módulo itertools, el cual provee los mecanismos necesarios para generar todo este tipo de agrupaciones. Aún así, resulta muy interesante diseñar e implementar por nuestra cuenta los algoritmos correspondientes, los cuales pueden emplear de manera muy ilustrativa las listas por comprensión (list comprehensions) de Python.

En esta plática se mostrará la manera de diseñar incrementalmente los algoritmos para producir tres diferentes tipos de agrupaciones:

  • Comenzamos con el conjunto potencia: a partir de un conjunto dado, ¿cuáles son todos sus subconjuntos?
  • Luego siguen las combinaciones tomando n objetos a la vez: a partir del resultado del punto anterior, seleccionamos solamente los subconjuntos que sean de tamaño n.
  • Finalmente, calculamos las permutaciones tomando n objetos a la vez: reordenamos de todas las maneras posibles los objetos de cada subconjunto obtenido de las combinaciones de tamaño n del punto anterior.

Al finalizar la plática el público asistente tendrá una idea general de cómo emplear las listas por comprensión de Python para resolver problemas comunes de matemática combinatoria.

Notes

La plática propuesta está basada en una entrada de blog escrita por el mismo autor y con el mismo título: Combinaciones, permutaciones y otras diversiones.

Algunos datos relevantes sobre el autor:

  • Es profesor de tiempo completo del Tecnológico de Monterrey, México, en donde imparte diversas materias de programación, tanto en idioma español como en inglés, para alumnos de la carrera de Ingeniero en Sistemas Computacionales.
  • Ha estado usando Python desde el año 2001, tanto para sus clases como para sus proyectos personales.
  • Es autor de EduPython, uno de los blogs más populares en español sobre el uso de Python en la educación.
  • Ha sido ponente de diferentes talleres, artículos y pósteres en los congresos del Grupo de Interés Especial de la ACM en Educación en Ciencia de la Computación (SIGCSE) desde el año 2001 (ver perfil de autor ACM).
  • En los últimos veinte años ha presentado pláticas en distintos congresos y conferencias en México y los Estados Unidos. Algunas de sus pláticas más recientes son: