Permutations

+10

Vous recevez une liste nums d’entiers distincts. Renvoyez tous les ordres possibles de ces valeurs, chacun sous forme de liste utilisant chaque valeur exactement une fois, de sorte que n valeurs donnent n! ordres. Énumérez-les dans l’ordre lexicographique : comparez deux ordres position par position et laissez leur première différence les départager. Pour [1, 2, 3], cela place [1, 2, 3] en premier et [3, 2, 1] en dernier.

Fonction

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

numsinteger-array: les valeurs, toutes différentes, dans n’importe quel ordre
Renvoieinteger-2d-array: tous les ordres possibles des valeurs, listés dans l’ordre lexicographique

Contraintes

1 ≤ nums.length ≤ 6
-10 ≤ nums[i] ≤ 10
Toutes les valeurs de nums sont différentes.
nums peuvent être dans n’importe quel ordre.

Exemples

Entrée: nums = [3, 1, 2]
Sortie: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Explication: Trois valeurs ont 3! = 6 ordres possibles. Une fois triées, les valeurs sont 1, 2, 3, donc les ordres qui commencent par 1 viennent en premier, et [1, 2, 3] vient avant [1, 3, 2] parce que 2 est plus petit que 3 à la deuxième position. L’ordre des valeurs d’entrée n’a pas d’importance.

Entrée: nums = [2, -1]
Sortie: [[-1, 2], [2, -1]]
Explication: Deux valeurs peuvent être écrites dans deux ordres. [-1, 2] vient en premier parce que -1 est inférieur à 2.

+13 tests cachés à la soumission

Pour aller plus loin

Étant donné un ordre, peux-tu produire le suivant dans l’ordre lexicographique, sur place, en O(n) et avec un espace supplémentaire de O(1) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Une liste de n valeurs distinctes possède n! ordres possibles, soit 720 pour six valeurs, et la réponse doit tous les énumérer : le travail est donc d’au moins n × n!. Le défi consiste à construire chaque ordre une seule fois et à les produire dans l’ordre lexicographique. Le retour arrière sur les valeurs triées, en essayant toujours d’abord la plus petite valeur inutilisée, permet de faire les deux en même temps.

Insérez dans chaque espace, puis triez

Intuition

Fais croître les ordonnancements une valeur à la fois. Sans aucune valeur, il n’existe qu’un seul ordonnancement : la liste vide. Pour ajouter la valeur 3 à l’ordonnancement [1, 2], place-la dans chacun de ses trois intervalles : [3, 1, 2], [1, 3, 2] et [1, 2, 3]. Fais cela pour chaque ordonnancement obtenu, et les ordonnancements de k valeurs deviennent des ordonnancements de k+1 valeurs.

Chaque ordonnancement de k+1 valeurs est construit exactement une fois : retire la valeur la plus récente et tu obtiens l’unique ordonnancement dont il est issu, tandis que la position de cette valeur indique l’intervalle. Les nombres d’ordonnancements sont donc 1, 2, 6, 24, et n valeurs donnent n! ordonnancements.

Ils ne sont pas produits dans l’ordre requis. Pour [1, 2, 3], le premier ordonnancement construit est [3, 2, 1], il faut donc terminer par un tri qui compare les positions une par une. Ce tri est la partie coûteuse : n! ordonnancements nécessitent environ n! × log(n!) comparaisons, et chacune lit jusqu’à n valeurs. Pour six valeurs, cela représente environ 720 × 9.5 × 6, soit environ 41 000 lectures. La méthode conserve également en mémoire toute une génération d’ordonnancements pendant qu’elle construit la suivante.

Algorithme

Commencez avec une liste contenant un ordre vide.
Pour chaque valeur de nums, construisez une nouvelle liste : pour chaque ordre obtenu jusqu’ici et chaque emplacement de 0 à sa longueur, copiez l’ordre en insérant la valeur à cet emplacement.
Remplacez l’ancienne liste par la nouvelle.
Triez les ordres position par position et renvoyez-les.

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

Retour arrière avec un tableau de valeurs utilisées

Intuition

Remplis n cases de gauche à droite. La première case a n candidats, la deuxième n-1, et ainsi de suite : c’est de là que vient n!. Dessine ces choix sous forme d’arbre : la racine est un chemin vide, chaque arête ajoute une valeur, et chaque feuille, à la profondeur n, correspond à un ordre complet. Pour les valeurs triées 1, 2, 3, la racine a pour enfants [1], [2] et [3] ; [1] a pour enfants [1, 2] et [1, 3] ; chacun de ces nœuds a une feuille.

Le retour sur trace parcourt cet arbre avec un path partagé et un indicateur used pour chaque valeur. À chaque nœud, il parcourt les valeurs et ignore celles qui sont déjà utilisées. Pour chaque valeur disponible, il la choisit (la marque comme utilisée et l’ajoute), l’explore (récursion à un niveau plus profond), puis annule le choix (la retire et la marque comme disponible). Cette annulation rétablit exactement l’état qu’avait la boucle avant, de sorte que la valeur suivante est essayée depuis le même nœud. Un chemin de longueur n est une feuille : enregistre-en une copie et retourne.

L’ordre se forme naturellement. La boucle essaie d’abord la plus petite valeur disponible, et le parcours termine tous les ordres commençant par un préfixe donné avant de passer à un autre préfixe. Ainsi, tous les ordres commençant par 1 précèdent ceux commençant par 2, et parmi eux, [1, 2, ...] précède [1, 3, ...]. C’est l’ordre lexicographique. C’est aussi pour cela que tu tries nums en premier : la boucle parcourt les indices, donc ceux-ci doivent être dans l’ordre des valeurs.

L’arbre contient environ e × n! nœuds (e vaut environ 2.72), et chacun exécute une boucle de n éléments ; le temps est donc O(n × n!), du même ordre que la taille du résultat. En dehors du résultat, le chemin, les indicateurs et la pile d’appels contiennent chacun au plus n éléments.

Algorithme

Triez les valeurs et créez un tableau used de n indicateurs faux.
Écrivez explore(). Si path contient n valeurs, ajoutez-en une copie au résultat et retournez.
Sinon, pour chaque indice i de 0 à n-1 dont la valeur est disponible : marquez-la comme utilisée et ajoutez values[i] (choisir), appelez explore() (explorer), puis retirez-la et marquez-la comme disponible (annuler le choix).
Appelez explore() une fois et retournez le résultat.

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

Pièges et cas limites

Les bogues de retour sur trace sont presque toujours dus à un état qui n’est pas restauré ou qui est partagé par inadvertance.

Enregistrer path au lieu d’en enregistrer une copie. Les n! entrées finissent par être la même liste, qui est vide une fois le parcours terminé.
Annuler seulement la moitié d’un choix. Si vous retirez la valeur, mais laissez used[i] défini, cette valeur ne réapparaît jamais dans une branche ultérieure et vous obtenez moins de n! permutations.
Ne pas trier nums au préalable. Le parcours trouve toujours toutes les permutations, mais elles suivent l’ordre de l’entrée ; l’entrée [3, 1, 2] serait donc affichée en premier.
Utiliser la méthode par échange (échanger nums[start] avec chaque position suivante, faire un appel récursif, puis rétablir l’échange) sans tri final. Elle trouve les n! permutations, mais pour [1, 2, 3], elle affiche [3, 2, 1] avant [3, 1, 2].
Vérifier si une valeur a été utilisée en parcourant path. Cela fonctionne ici uniquement parce que les valeurs sont différentes, et cela coûte n à chaque étape. Un indicateur par indice est en O(1) et fonctionne toujours lorsque les valeurs se répètent.

Questions fréquentes4

Combien de permutations une liste de n éléments distincts possède-t-elle ?

n!, se lit « n factorielle » : n choix pour la première position, n-1 pour la deuxième, jusqu’à un pour la dernière, multipliés entre eux. Trois valeurs donnent 6 ordres possibles, six en donnent 720, et dix en donnent déjà 3,628,800, c’est pourquoi les problèmes de permutation gardent n petit.

Quelle est la complexité temporelle de la génération de toutes les permutations ?

O(n × n!). Il y a n! ordres et écrire chacun d’eux prend n étapes, donc aucune méthode ne peut faire mieux lorsqu’elle doit tous les renvoyer. Le retour sur trace atteint cette borne et, outre la sortie, nécessite un espace O(n) pour le chemin actuel, les indicateurs d’utilisation et la récursion.

Pourquoi le retour sur trace produit-il des permutations dans l’ordre lexicographique ?

Il s’agit d’un parcours en profondeur qui essaie d’abord la plus petite valeur disponible. Il termine tous les ordres qui commencent par un préfixe donné avant de passer au préfixe suivant, et il essaie les préfixes du plus petit au plus grand. Cela correspond à l’ordre des mots dans un dictionnaire, à condition que l’entrée soit triée avant le début du parcours.

Comment générer des permutations lorsque l’entrée contient des doublons ?

Triez les valeurs et, à chaque position, ignorez une valeur égale à celle qui la précède lorsque cette copie précédente n’est pas utilisée : i > 0, values[i] == values[i-1] et !used[i-1]. Cela force les valeurs égales à être placées dans leur ordre d’origine, de sorte que chaque ordre distinct soit construit une seule fois.

Python

def permute(nums):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

nums = [3, 1, 2]

Attendu

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