Permutations par retour sur trace

À la profondeur $k$, choisissez quelle position d'entrée encore inutilisée fournit la position de sortie $k$. Suivre les positions, et pas seulement les valeurs, préserve les multiplicités correctes.

def unique_permutations(values: list[int]) -> list[list[int]]:
    values = sorted(values)
    used = [False] * len(values)
    path: list[int] = []
    result: list[list[int]] = []

    def visit() -> None:
        if len(path) == len(values):
            result.append(path.copy())
            return
        for i, value in enumerate(values):
            if used[i]:
                continue
            if i > 0 and value == values[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(value)
            visit()
            path.pop()
            used[i] = False

    visit()
    return result

Le tri regroupe les valeurs égales. À un même niveau de décision, la règle de déduplication n'autorise que le premier exemplaire actuellement inutilisé. Elle élimine ainsi les branches symétriques sans supprimer de permutation distincte.

Coût

Pour $n$ valeurs distinctes, il existe $n!$ résultats de longueur $n$ ; leur matérialisation exige donc $\Theta(n\cdot n!)$ de travail et d'espace de sortie. En plus de cette sortie, le retour sur trace utilise $O(n)$ pour le chemin, l'état d'utilisation et la récursion.

Lorsque les résultats sont consommés progressivement, un générateur évite de conserver toute la sortie, mais ne peut contourner la borne inférieure en temps imposée par sa taille.

Trace des doublons et permutation vide

Pour [1,1,2], la racine peut choisir le premier 1 ou le 2, mais saute le second 1. Une fois le premier 1 choisi, le second devient admissible : le choisir donne [1,1,2], tandis que prendre 2 ensuite donne [1,2,1]. La branche racine commençant par 2 donne [2,1,1]. Les deux copies sont donc conservées quand il le faut ; seules leurs identités interchangeables sont éliminées.

La longueur du chemin augmente à chaque appel et est bornée par n : la récursion termine. L'entrée vide renvoie [[]], pas [] : il existe une permutation de zéro élément. Pour des multiplicités m₁,…,mᵣ, le nombre de sorties distinctes est n!/(m₁!…mᵣ!). Le code parcourt toutefois n positions à chaque nœud interne : son temps n'est pas toujours proportionnel au seul nombre de sorties distinctes. Si toutes les valeurs sont égales, il n'y a qu'une sortie mais Θ(n²) de travail de parcours.

assert unique_permutations([1, 1, 2]) == [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
assert unique_permutations([]) == [[]]

Source

• Stanford CS106B : retour sur trace

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.