Permutations et idée des N reines
Placer les éléments et revenir en arrière en cas de conflit
Permutations et idée des N reines est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Des sous-ensembles aux permutations
Une permutation est un arrangement de tous les éléments dans un certain ordre. Les générer est la compétence de retour sur trace qui suit les sous-ensembles. 🔀
Combien existe-t-il de permutations
Il existe n factorielle permutations de n éléments, car le premier emplacement offre n choix, le suivant n moins un, et ainsi de suite. Le nombre augmente rapidement.
Placez un élément à la fois
La récursivité remplit les positions de gauche à droite. À chaque étape, vous choisissez un élément inutilisé, vous le placez, puis vous poursuivez la récursivité sur le reste.
Suivez les éléments utilisés
Un tableau des éléments utilisés booléen indique quels éléments sont déjà placés, afin que chacun apparaisse exactement une fois dans chaque permutation.
Les permutations en code
Ce retour sur trace place une valeur inutilisée, poursuit la récursivité, puis la libère pour la branche suivante.
def perm(cur):
if len(cur) == n:
out.append(cur[:]); return
for x in a:
if x not in cur:
perm(cur + [x])Utilisez itertools si c'est autorisé
Pour les concours rapides, les itertools.permutations de Python fournissent tous les ordres sans que vous ayez à écrire vous-même la récursivité.
from itertools import permutations
for p in permutations(a):
print(p)Le problème des n reines
Le problème des n reines vous demande de placer n reines sur un échiquier de n par n, de sorte qu'aucune ne puisse en attaquer une autre. C'est le problème classique du retour sur trace. 👑
Une reine par ligne
Puisque deux reines ne partagent jamais une ligne, vous placez exactement une reine par ligne et vous choisissez uniquement sa colonne. Cela réduit considérablement la recherche.
Vérifiez les trois conflits
Avant de placer une reine, refusez toute colonne ou diagonale déjà occupée. Suivez les colonnes utilisées et les deux directions diagonales dans des ensembles.
if c in cols or r-c in d1 or r+c in d2:
continueRevenez en arrière dans une impasse
Si aucune colonne ne convient sur une ligne, la branche échoue. Vous effectuez un retour sur trace, retirez la dernière reine et essayez son option suivante.
Le schéma commun
Les permutations et le problème des n reines ont la même structure : choisir, poursuivre la récursivité, annuler. Une fois que vous l'avez comprise, la plupart des problèmes de placement suivent le même modèle.
Vérification rapide
Pourquoi le problème des n reines place-t-il une seule reine par ligne ?
Récapitulatif : choisir, poursuivre, annuler
Vous avez généré des permutations en plaçant des éléments inutilisés et appris que le problème des n reines utilise le même schéma choisir-poursuivre-annuler, avec des vérifications de conflits. 🎯
Questions Fréquemment Posées
La leçon « Permutations et idée des N reines » est-elle gratuite ?
Oui — le texte complet de « Permutations et idée des N reines » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Permutations et idée des N reines » ?
Placer les éléments et revenir en arrière en cas de conflit Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Permutations et idée des N reines » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Raisonner récursivement : base et récursion
- Générer tous les sous-ensembles
- Permutations et idée des N reines
- Élaguer pour respecter la limite de temps