Combinazioni di una lista in Python

Usa itertools.combinations() per selezionare un numero fisso di elementi senza riutilizzare una posizione dell’input. Se una posizione può essere scelta più di una volta, usa itertools.combinations_with_replacement(). Entrambe le funzioni producono combinazioni: l’ordine di selezione non crea un risultato distinto; nelle permutazioni, invece, ordini diversi sono considerati risultati distinti.

Scegliere il tipo di combinazione più adatto

Scegli una dimensione fissa per la selezione con combinations(), consenti di ripetere una posizione con combinations_with_replacement() oppure genera ogni sottoinsieme con una funzione powerset(). Le funzioni della libreria standard restituiscono iteratori di tuple. L’input viene elaborato in base alle posizioni, quindi valori ripetuti in posizioni diverse possono produrre tuple apparentemente duplicate. L’ordine dei risultati segue quello delle posizioni nell’input; i valori all’interno di ciascuna tupla non vengono ordinati automaticamente. Se ti serve una regola personalizzata, la ricorsione può rendere esplicito il processo di selezione.

Usare itertools.combinations() per selezioni senza ripetizioni

itertools.combinations(iterable, r) produce tuple di lunghezza r senza riutilizzare una posizione. L’iterabile viene consumato nell’ordine dell’input. Converti l’iteratore in una lista se vuoi salvare o esaminare tutti i risultati in una volta; altrimenti, puoi iterarci direttamente.

Esegui questo esempio:

Il codice e le etichette o gli output visibili in questa sezione restano in inglese.

from itertools import combinations

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

Nei risultati con due elementi, ogni posizione viene usata al massimo una volta. Per ottenere singoli elementi, imposta r a 1; per ottenere l’intero input in un’unica tupla, impostalo al numero di posizioni dell’input. Se r supera il numero di posizioni, l’iteratore non produce risultati.

Usare itertools.combinations_with_replacement() quando le selezioni possono ripetersi

Usa itertools.combinations_with_replacement(iterable, r) quando è consentito selezionare più volte la stessa posizione dell’input. Anche questa funzione produce tuple di lunghezza r e segue la stessa regola di ordinamento basata sulle posizioni. Per esempio, scegliendo coppie da ["red", "blue"] si ottengono anche ("red", "red") e ("blue", "blue"), che combinations() escluderebbe. È utile quando ripetere una scelta ha senso, per esempio quando si scelgono due palline di gelato e possono essere dello stesso gusto. L’argomento r determina comunque la lunghezza di ogni tupla.

Usare la ricorsione o un generatore per un’implementazione personalizzata

Una funzione ricorsiva con backtracking può raccogliere i risultati in una lista. A ogni passaggio aggiunge un valore, richiama la funzione dalla posizione successiva e poi rimuove quel valore, così il ciclo può provare un’altra scelta. Un generatore segue la stessa logica di selezione, ma produce ciascun risultato man mano che lo trova. Evita di conservare l’intera raccolta dei risultati, a meno che il chiamante non la converta esplicitamente in una lista; questo non lo rende intrinsecamente più veloce.

Entrambe le funzioni personalizzate qui sotto richiedono che r sia un intero non negativo e, in caso contrario, sollevano ValueError. Con r = 0, ciascuna restituisce l’unica tupla vuota; se r è positivo ma supera il numero di posizioni dell’input, nessuna delle due produce risultati. Il generatore controlla l’argomento quando inizia l’iterazione, perché il corpo di una funzione generatrice viene eseguito in modo differito.

Il codice e le etichette o gli output visibili in questa sezione restano in inglese.

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

Per una versione personalizzata che produce risultati in modo differito, usa yield quando viene raggiunta una selezione completa. In entrambe le implementazioni, imposta la posizione della chiamata ricorsiva successiva su index + 1 per evitare di riutilizzare una posizione. Se l’input contiene valori duplicati, i risultati possono apparire identici anche se derivano da posizioni diverse.

Generare ogni sottoinsieme con una funzione powerset()

Un insieme delle parti contiene sottoinsiemi di ogni dimensione, compresi la tupla vuota e l’intero input. Questa implementazione combina i risultati per ogni dimensione possibile. chain.from_iterable() restituisce un iteratore: racchiudilo in list() solo quando devi materializzare tutti i sottoinsiemi.

Il codice e le etichette o gli output visibili in questa sezione restano in inglese.

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)

Con n posizioni nell’input, un insieme delle parti contiene 2**n sottoinsiemi. Il numero cresce rapidamente, quindi preferisci un iteratore di combinazioni a dimensione fissa quando ti servono selezioni di una sola dimensione. Usa l’insieme delle parti quando il risultato deve davvero includere sottoinsiemi di tutte le dimensioni.