Philippe.Dumas@inria.fr


http://algo.inria.fr/dumas/Maple/

Retour en page principale Table des matières Index

Maple V.4 worksheet, bis Maple V.5 worksheet, bis

Nous employons l'idée suivante. Pour fabriquer toutes les permutations de la liste L=[x_1,x_2,...,x_n], nous construisons toutes les permutations de la liste [x_2,...,x_n] puis nous insérons x_1 en les n positions possibles. Ceci suppose de disposer d'une procédure d'insertion. Nous commençons donc par là.

> insert:=proc(L::list,x,i::posint)

    local n,j:

    n:=nops(L);

    if n<i-1 then ERROR(`insert expects the length of the list to be

                          not smaller than the position of insertion

                          minus 1, but received`,x,L,i)

    else 

      [seq(L[j],j=1..i-1),x,seq(L[j],j=i..n)]

    fi

  end:

> insert([x,y,z],a,1);

> insert([x,y,z],a,4);

Cependant nous n'allons utiliser cette procédure que comme procédure auxiliaire. La gestion des erreurs n'est donc pas utile car nous n'employerons la procédure qu'avec des données correctes. Plus généralement on évite les tests dans les procédures auxiliaires; le contrôle des données se fait au niveau des procédures visibles de l'utilisateur.

> insert:=proc(L::list,x,i::posint)

    local n,j:

    n:=nops(L);

    [seq(L[j],j=1..i-1),x,seq(L[j],j=i..n)]

  end:

> permlist:=proc(L::list)

    local n,i,LL,LLL;

    n:=nops(L);

    if n<2 then [L]

    else

      LL:=permlist([seq(L[i],i=2..n)]);

      for i to n do 

        LLL[i]:=map(insert,LL,L[1],i)

      od;

      [seq(op(LLL[i]),i=1..n)]

    fi

  end:

> permlist([]);

> permlist([a]);

> trace(permlist):

> permlist([a,b]);

{--> enter permlist, args = [a, b]

{--> enter permlist, args = [b]

<-- exit permlist (now in permlist) = [[b]]}

<-- exit permlist (now at top level) = [[a, b], [b, a]]}

> permlist([a,b,c]);

{--> enter permlist, args = [a, b, c]

{--> enter permlist, args = [b, c]

{--> enter permlist, args = [c]

<-- exit permlist (now in permlist) = [[c]]}

<-- exit permlist (now in permlist) = [[b, c], [c, b]]}

<-- exit permlist (now at top level) = [[a, b, c], [a, c, b], [b, a, c], [c, a, b], [b, c, a], [c, b, a]]}

> untrace(permlist):

La méthode précédente n'a certainement pas le mérite de l'efficacité. Précisons que la procédure permute du package combinat fournit le même travail.

> combinat[permute]([a,b,c]);

Ceci dit, l'énoncé est ambigu. Après sondage auprès des auteurs, il s'avère que la question posée est la suivante : On demande d'écrire une procédure qui prend en entrée une liste et qui produit successivement les permutations de cette liste. Il est clair que ce qui est demandé est beaucoup moins coûteux en mémoire que la procédure permlist que nous venons de mettre au point. En effet on n'a jamais à considérer simultanément les n! permutations d'une liste de longueur n, mais seulement une permutation à la fois. On va voir que la place occupée en mémoire est alors un O(n^2) et non un O(n.n!).

L'idée est d'employer une procédure auxiliaire recur qui va énumérer toutes les permutations de la liste qui laissent fixe les éléments d'indice plus grand qu'un rang donné. La procédure perm se contente donc d'appeler cette procédure auxiliaire et la procédure exchange n'est là que pour alléger l'écriture du code de recur

> perm:=proc(L::list)

    local n;

    n:=nops(L);

    if n=0 then

      L

    else

      recur(L,n,n)

    fi

  end:

> exchange:=proc(L,i,j)

    local k,L1;

    L1:=L:

    L1[i]:=L[j];

    L1[j]:=L[i];

    L1

  end:

Venons en au point essentiel. L'appel recur(L,i,n) provoque l'écriture des permutations de la liste L de longueur n qui laisse en place les éléments dont la place dans la liste est supérieure ou égale à i. Le cas de base est celui où i égale 1 ; il suffit alors d'écrire la liste elle-même. Dans le cas général, on met successivement à la place i l'élément qui est à la place j pour j variant de 1 à n. Pour chacune des permutations que doit renvoyer recur(L,i,n), l'élément qui figure à la place i est l'un des éléments de la liste L qui est en place j avec j plus petit que i. On aura donc bien ainsi toutes les permutations cherchées. D'autre part, on ressort de la boucle d'indice j en retrouvant la permutation que l'on avait en y entrant. Cette invariance permet de prouver la correction du programme.

> recur:=proc(L,i,n)

    local j,L1,L2;

    if i=1 then print(L)

    else 

        L1:=L;

        for j to i do 

        L2:=exchange(L1,i,j);

        recur(L2,i-1,n);

        L1:=exchange(L2,i,j)

      od

    fi

  end:

> perm([a,b,c]);

L'appel récursif de la procédure sur une liste de longueur n a pour effet d'empiler n listes de longueur n, c'est pourquoi nous avons affirmé que la place occupée en mémoire est de l'ordre de n^2.

On trouvera dans [Sedgewick77] la présentation et la comparaison d'un grand nombre d'algorithmes de génération de permutations.

Retour en page principale