Permutations

+10

Ricevi una lista nums di interi tutti diversi. Restituisci ogni ordinamento di quei valori, ciascuno come una lista che usa ogni valore esattamente una volta, così che n valori producano n! ordinamenti. Elencali in ordine lessicografico: confronta due ordinamenti posizione per posizione e lascia che sia la prima differenza a decidere. Per [1, 2, 3], questo mette [1, 2, 3] per primo e [3, 2, 1] per ultimo.

Funzione

permute(nums: integer-array) → integer-2d-array

numsinteger-array: i valori, tutti diversi, in qualsiasi ordine
Restituisceinteger-2d-array: ogni ordinamento dei valori, elencato in ordine lessicografico

Vincoli

1 ≤ nums.length ≤ 6
-10 ≤ nums[i] ≤ 10
Tutti i valori in nums sono diversi.
nums può essere in qualsiasi ordine.

Esempi

Input: nums = [3, 1, 2]
Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Spiegazione: Tre valori hanno 3! = 6 ordinamenti. Ordinati, i valori sono 1, 2, 3, quindi vengono prima gli ordinamenti che iniziano con 1 e [1, 2, 3] viene prima di [1, 3, 2] perché 2 è minore di 3 nella seconda posizione. L'ordine dell'input non è importante.

Input: nums = [2, -1]
Output: [[-1, 2], [2, -1]]
Spiegazione: Due valori possono essere scritti in due ordini. [-1, 2] viene prima perché -1 è minore di 2.

+13 test nascosti all’invio

Per approfondire

Data una permutazione, riesci a produrre la successiva in ordine lessicografico direttamente, in O(n) e usando O(1) spazio aggiuntivo?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Un elenco di n valori diversi ha n! ordinamenti, 720 per sei valori, e la risposta deve elencarli tutti, quindi il lavoro è almeno n × n!. La sfida consiste nel costruire ogni ordinamento una sola volta e nell’emetterli in ordine lessicografico. Il backtracking sui valori ordinati, provando sempre per primo il valore inutilizzato più piccolo, fa entrambe le cose contemporaneamente.

Inserisci in ogni spazio, poi ordina

Intuizione

Fai crescere gli ordinamenti un valore alla volta. Senza valori c'è un ordinamento, la lista vuota. Per aggiungere il valore 3 all'ordinamento [1, 2], inseriscilo in ciascuno dei suoi tre spazi: [3, 1, 2], [1, 3, 2] e [1, 2, 3]. Fallo per ogni ordinamento che hai: gli ordinamenti di k valori diventano così gli ordinamenti di k+1 valori.

Ogni ordinamento di k+1 valori viene creato esattamente una volta: togli da esso il valore più recente e ottieni l'unico ordinamento da cui è derivato, mentre la posizione del valore più recente indica lo spazio. Quindi i conteggi sono 1, 2, 6, 24 e n valori danno n! ordinamenti.

Non vengono prodotti nell'ordine richiesto. Per [1, 2, 3] il primo ordinamento creato è [3, 2, 1], quindi alla fine serve un ordinamento che confronti le posizioni una per una. È questo ordinamento la parte costosa: n! ordinamenti richiedono circa n! × log(n!) confronti, e ciascuno legge fino a n valori. Per sei valori sono circa 720 × 9.5 × 6, cioè circa 41.000 letture. Inoltre, mentre crea la generazione successiva, il metodo mantiene in memoria un'intera generazione di ordinamenti.

Algoritmo

Inizia con un elenco che contiene un ordinamento vuoto.
Per ogni valore in nums, crea un nuovo elenco: per ogni ordinamento ottenuto finora e per ogni posizione da 0 alla sua lunghezza, copia l’ordinamento inserendo il valore in quella posizione.
Sostituisci il vecchio elenco con quello nuovo.
Ordina gli ordinamenti posizione per posizione e restituiscili.

def permute(nums):
    perms = [[]]
    for value in nums:
        grown = []
        for perm in perms:
            # Put value into every gap of perm, both ends included.
            for gap in range(len(perm) + 1):
                grown.append(perm[:gap] + [value] + perm[gap:])
        perms = grown
    # Insertion order is not lexicographic, so sort at the end.
    perms.sort()
    return perms

Backtracking con un array di elementi usati

Intuizione

Riempi n posizioni da sinistra a destra. La prima posizione ha n candidati, la seconda n-1 e così via: ecco da dove viene n!. Rappresenta queste scelte come un albero: la radice è un percorso vuoto, ogni arco aggiunge un valore e ogni foglia, alla profondità n, rappresenta un ordinamento completo. Per i valori ordinati 1, 2, 3, la radice ha come figli [1], [2] e [3]; [1] ha come figli [1, 2] e [1, 3]; ciascuno di questi ha una foglia.

Il backtracking attraversa questo albero con un unico path condiviso e un flag used per ogni valore. In ogni nodo scorre i valori e salta quelli già usati. Per ogni valore libero, lo sceglie (lo contrassegna come usato e lo aggiunge), lo esplora (ricorre un livello più in profondità), poi annulla la scelta (lo rimuove e lo contrassegna come libero). Il passaggio che annulla la scelta ripristina esattamente lo stato che il ciclo aveva prima, così il valore successivo viene provato a partire dallo stesso nodo. Un percorso di lunghezza n è una foglia: registrane una copia e termina.

L’ordine si ottiene automaticamente. Il ciclo prova per primo il valore libero più piccolo e l’attraversamento completa tutti gli ordinamenti che iniziano con un determinato prefisso prima di modificarlo. Quindi tutti gli ordinamenti che iniziano con 1 vengono prima di quelli che iniziano con 2 e, tra i primi, [1, 2, ...] viene prima di [1, 3, ...]. Questo è l’ordine lessicografico. Ecco anche perché prima ordini nums: il ciclo procede per indice, quindi gli indici devono seguire l’ordine dei valori.

L’albero ha circa e × n! nodi (e è circa 2.72) e ognuno esegue un ciclo di n elementi; quindi il tempo è O(n × n!), lo stesso ordine di grandezza della dimensione della risposta. Oltre all’output, il percorso, i flag e lo stack delle chiamate contengono ciascuno al massimo n elementi.

Algoritmo

Ordina i valori e crea un array used di n flag impostati su false.
Scrivi explore(). Se path contiene n valori, aggiungi una copia al risultato e restituisci.
Altrimenti, per ogni indice i da 0 a n-1 il cui valore è libero: contrassegnalo come usato e aggiungi values[i] (scegli), chiama explore() (esplora), poi rimuovilo e contrassegnalo come libero (annulla la scelta).
Chiama explore() una volta e restituisci il risultato.

def permute(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    path = []
    used = [False] * n

    def explore():
        # A full path is a leaf of the decision tree: one finished ordering.
        if len(path) == n:
            result.append(path[:])
            return
        # Smallest unused value first, so the leaves come out in lexicographic order.
        for i in range(n):
            if used[i]:
                continue
            used[i] = True
            path.append(values[i])  # choose
            explore()               # explore
            path.pop()              # un-choose
            used[i] = False

    explore()
    return result

Trappole e casi limite

I bug di backtracking dipendono quasi sempre da uno stato che non viene ripristinato oppure da uno stato condiviso per errore.

Registrare path invece di una sua copia. Tutte le n! voci finiscono per essere la stessa lista, che risulta vuota una volta terminata l'esplorazione.
Annullare solo metà di una scelta. Se rimuovi il valore ma lasci impostato used[i], quel valore non comparirà più in un ramo successivo e restituirai meno di n! ordinamenti.
Non ordinare prima nums. L'esplorazione trova comunque tutti gli ordinamenti, ma li segue nell'ordine dell'input, quindi l'input [3, 1, 2] verrebbe elencato per primo.
Usare il metodo dello scambio (scambiare nums[start] con ogni posizione successiva, ricorrere, scambiare di nuovo) senza un ordinamento finale. Trova tutti gli n! ordinamenti, ma per [1, 2, 3] elenca [3, 2, 1] prima di [3, 1, 2].
Controllare se un valore è già stato usato cercandolo in path. Funziona qui solo perché i valori sono diversi e costa n a ogni passaggio. Un flag per indice richiede O(1) e funziona anche quando i valori si ripetono.

Domande frequenti4

Quante permutazioni ha una lista di n elementi distinti?

n!, si legge n fattoriale: n possibilità per la prima posizione, n-1 per la seconda, fino a una per l’ultima, moltiplicate tra loro. Tre valori danno 6 ordinamenti, sei ne danno 720 e già dieci ne danno 3,628,800, motivo per cui i problemi di permutazione mantengono n piccolo.

Qual è la complessità temporale della generazione di tutte le permutazioni?

O(n × n!). Ci sono n! ordinamenti e scrivere ciascuno richiede n passaggi, quindi nessun metodo può fare di meglio quando deve restituirli tutti. Il backtracking raggiunge questo limite e, oltre all'output, richiede O(n) spazio per il percorso corrente, i flag degli elementi utilizzati e la ricorsione.

Perché il backtracking produce permutazioni in ordine lessicografico?

È una visita in profondità che prova per primo il valore disponibile più piccolo. Completa ogni ordinamento che inizia con un determinato prefisso prima di passare al prefisso successivo, e prova i prefissi dal più piccolo al più grande. Questo corrisponde al modo in cui un dizionario ordina le parole, purché l'input venga ordinato prima di iniziare la visita.

Come si generano le permutazioni quando l'input contiene duplicati?

Ordina i valori e, in ogni posizione, salta un valore uguale a quello precedente quando quella copia precedente non è in uso: i > 0, values[i] == values[i-1] e !used[i-1]. In questo modo i valori uguali vengono disposti nell’ordine originale, così ogni ordinamento distinto viene generato una sola volta.

Python

def permute(nums):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

nums = [3, 1, 2]

Atteso

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]