Permutazioni e idea delle N regine
Posizionare gli elementi e tornare indietro in caso di conflitto
Permutazioni e idea delle N regine è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Dai sottoinsiemi agli ordinamenti
Una permutazione è un ordinamento di tutti gli elementi in una certa sequenza. Generarle è la competenza di backtracking successiva ai sottoinsiemi. 🔀
Quante permutazioni
Esistono n fattoriale permutazioni di n elementi, perché la prima posizione ha n scelte, la successiva n meno uno, e così via. Cresce rapidamente.
Posizioni un elemento alla volta
La ricorsione riempie le posizioni da sinistra a destra. A ogni passo scelga un elemento non utilizzato, lo posizioni ed esegua la ricorsione sui rimanenti.
Tenga traccia degli elementi utilizzati
Un array booleano degli elementi utilizzati indica quali elementi sono già stati posizionati, così ognuno compare esattamente una volta in ogni permutazione.
Le permutazioni nel codice
Questo backtracking posiziona un valore non utilizzato, esegue la ricorsione, poi lo libera per il ramo successivo.
def perm(cur):
if len(cur) == n:
out.append(cur[:]); return
for x in a:
if x not in cur:
perm(cur + [x])Usi itertools quando è consentito
Nelle gare rapide, itertools.permutations di Python fornisce ogni ordinamento senza dover scrivere personalmente la ricorsione.
from itertools import permutations
for p in permutations(a):
print(p)Il problema delle N-Queens
N-Queens le chiede di posizionare n regine su una scacchiera n per n in modo che nessuna possa attaccare le altre. È il classico rompicapo di backtracking. 👑
Una regina per riga
Poiché due regine non condividono una riga, posizioni esattamente una regina per riga e scelga solo la colonna. In questo modo lo spazio di ricerca si riduce enormemente.
Controlli i tre conflitti
Prima di posizionare una regina, rifiuti qualsiasi colonna o diagonale già occupata. Tenga traccia delle colonne utilizzate e delle due direzioni diagonali in appositi insiemi.
if c in cols or r-c in d1 or r+c in d2:
continueFaccia backtracking in caso di vicolo cieco
Se in una riga nessuna colonna funziona, il ramo fallisce. Torni indietro, rimuova l'ultima regina e provi l'opzione successiva.
Lo schema comune
Permutazioni e N-Queens condividono una stessa struttura: scelga, esegua la ricorsione, annulli. Una volta riconosciuta, la maggior parte dei problemi di posizionamento segue lo stesso schema.
Verifica rapida
Perché N-Queens posiziona una sola regina per riga?
Riepilogo: scelga, esegua la ricorsione, annulli
Ha generato le permutazioni posizionando elementi non utilizzati e ha imparato che N-Queens usa lo stesso schema scegli-ricorri-annulla, con controlli sui conflitti. 🎯
Domande Frequenti
La lezione «Permutazioni e idea delle N regine» è gratuita?
Sì — il testo completo di «Permutazioni e idea delle N regine» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Permutazioni e idea delle N regine»?
Posizionare gli elementi e tornare indietro in caso di conflitto Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Permutazioni e idea delle N regine»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Pensare ricorsivamente: caso base e ricorsione
- Generare tutti i sottoinsiemi
- Permutazioni e idea delle N regine
- Potare per superare il limite di tempo