Combinaciones de una lista en Python

Use itertools.combinations() para seleccionar una cantidad fija de elementos sin reutilizar una posición de entrada. Si se puede seleccionar una posición más de una vez, use itertools.combinations_with_replacement(). Ambas funciones generan combinaciones, en las que cambiar el orden de selección no produce un resultado nuevo; en las permutaciones, los órdenes distintos sí cuentan como resultados diferentes.

Elija el tipo de combinación adecuado

Elija un tamaño fijo para la selección con combinations(), permita repetir una posición con combinations_with_replacement() o genere todos los subconjuntos con una función powerset(). Las funciones de la biblioteca estándar devuelven iteradores de tuplas. Como procesan la entrada por posición, los valores repetidos en distintas posiciones pueden producir tuplas que parecen duplicadas. El orden de los resultados sigue el de las posiciones de entrada; los valores de cada tupla no se ordenan automáticamente. Si necesita una regla personalizada, la recursión permite hacer explícito el proceso de selección.

Use itertools.combinations() para selecciones sin reemplazo

itertools.combinations(iterable, r) produce tuplas de longitud r y no reutiliza ninguna posición. El iterable se procesa en el orden de entrada. Convierta el iterador en una lista si necesita guardar o revisar todos los resultados a la vez; de lo contrario, recórralo directamente.

Ejecute este ejemplo:

El código y las etiquetas o salidas visibles de esta sección se mantienen en inglés.

from itertools import combinations

items = ["red", "blue", "green"]
for pair in combinations(items, 2):
    print(pair)

Los resultados de dos elementos usan cada posición como máximo una vez. Para obtener elementos individuales, establezca r en 1; para obtener toda la entrada como una sola tupla, establézcalo en la cantidad de posiciones de entrada. Si r supera esa cantidad, el iterador no produce resultados.

Use itertools.combinations_with_replacement() cuando se permita repetir selecciones

Use itertools.combinations_with_replacement(iterable, r) cuando se permita seleccionar la misma posición de entrada más de una vez. También produce tuplas de longitud r y sigue la misma regla de orden por posición. Por ejemplo, al elegir parejas de ["red", "blue"], se incluyen ("red", "red") y ("blue", "blue"); combinations() omitiría esas parejas. Esto resulta útil cuando tiene sentido repetir una elección, como al elegir dos bolas de helado que pueden ser del mismo sabor. El argumento r sigue determinando la longitud de cada tupla.

Use recursión o un generador para una implementación personalizada

Una función recursiva de retroceso puede reunir los resultados en una lista. En cada paso, añade un valor, continúa la recursión desde la posición siguiente y luego elimina ese valor para que el bucle pueda probar otra opción. Un generador sigue la misma lógica de selección, pero produce cada resultado a medida que lo encuentra. Así evita conservar todos los resultados, salvo que quien lo llama los convierta explícitamente en una lista; esto no lo hace inherentemente más rápido.

Las dos funciones personalizadas de abajo requieren que r sea un entero no negativo y, en caso contrario, generan ValueError. Con r = 0, cada una devuelve la única tupla vacía; si r es positivo y supera la cantidad de posiciones de entrada, ninguna produce resultados. El generador comprueba el argumento cuando comienza la iteración, porque el cuerpo de una función generadora se ejecuta de forma diferida.

El código y las etiquetas o salidas visibles de esta sección se mantienen en inglés.

def get_combinations(items, r):
    if not isinstance(r, int) or isinstance(r, bool) or r < 0:
        raise ValueError("r must be a nonnegative integer")

    results = []

    def backtrack(start, chosen):
        if len(chosen) == r:
            results.append(tuple(chosen))
            return
        for index in range(start, len(items)):
            chosen.append(items[index])
            backtrack(index + 1, chosen)
            chosen.pop()

    backtrack(0, [])
    return results


def generate_combinations(items, r):
    if not isinstance(r, int) or isinstance(r, bool) or r < 0:
        raise ValueError("r must be a nonnegative integer")
    if r == 0:
        yield ()
        return
    for index in range(len(items)):
        for suffix in generate_combinations(items[index + 1 :], r - 1):
            yield (items[index],) + suffix


items = ["red", "blue", "green"]
print(get_combinations(items, 2))
print(list(generate_combinations(items, 2)))

Para una versión personalizada diferida, use yield cuando se complete una selección. En ambas implementaciones, avance la siguiente llamada recursiva a index + 1 para evitar reutilizar una posición. Si hay valores duplicados, los resultados pueden parecer idénticos aunque provengan de posiciones distintas.

Genere todos los subconjuntos con una función powerset()

Un conjunto potencia contiene subconjuntos de todos los tamaños, incluida la tupla vacía y la entrada completa. Esta implementación combina los resultados de cada tamaño posible. chain.from_iterable() devuelve un iterador, así que use list() solo si necesita materializar todos los subconjuntos.

El código y las etiquetas o salidas visibles de esta sección se mantienen en inglés.

from itertools import chain, combinations


def powerset(items):
    values = list(items)
    return chain.from_iterable(
        combinations(values, size) for size in range(len(values) + 1)
    )


for subset in powerset(["red", "blue"]):
    print(subset)

Para n posiciones de entrada, un conjunto potencia tiene 2**n subconjuntos. Esta cantidad crece rápidamente; por eso, si la tarea solo requiere selecciones de un tamaño, es preferible usar un iterador de combinaciones de tamaño fijo. Use el conjunto potencia cuando el resultado realmente deba incluir subconjuntos de todos los tamaños.