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.5worksheet bis

Nous avons vu à l'exercice 3 de la page 45, comment énumérer tous les permutations d'une liste avec une occupation en mémoire qui est un O(n^2). Nous allons voir qu'en employant un tableau nous arrivons au même résultat avec une place en mémoire qui est seulement un O(n).

Rappelons d'abord un détail technique. On obtient les indices d'une table par la procédure indices.

> T:=array(1..3,[a,b,c]);

> indices(T);

La procédure principale perm se contente d'appeler une procédure auxiliaire recur, après une petite vérification des données. D'autre part nous définissons une procédure exchange, qui échange deux éléments d'un tableau. Elle est surtout là pour alléger le code de recur. Notez que l'on y modifie le tableau t ; un tel code ne fonctionnerait pas avec une liste. On profite du fait qu'en Maple les tables et les procédures sont les seuls objets que l'on puisse modifier. C'est ce qui va faire gagner de la place en mémoire. Dans le cas des listes la procédure crée une autre liste, alors qu'ici l'échange se fait en place.

> perm:=proc(t::array,n::posint)

    local i;

    if [indices(t)]<>[[i]$i=1..n] then

      ERROR("expected its first argument to be an array

             indexed by 1..n, where n is the second argument,

             but received",t,n)

    else

      recur(t,n,n)

    fi

  end:

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

    local c;

    c:=t[i];

    t[i]:=t[j];

    t[j]:=c;

    NULL

  end:

Le coeur de la chose est l'écriture de la procédure recur. L'appel recur(t,i,n), où t est un tableau indexé par les entiers de 1 à n et i un entier entre 1 et n, va provoquer l'écriture de toutes les permutations du tableau qui laissent fixes les éléments dont les indices sont strictement plus grands que i. L'explication du fonctionnement de la procédure est le même que dans le cas des listes et le code est plus simple puisqu'on travaille toujours dans le même tableau.

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

    local j;

    if i=1 then print([seq(t[j],j=1..n)])

    else for j to i do 

        exchange(t,i,j);

        recur(t,i-1,n);

        exchange(t,i,j)

      od

    fi

  end:

> perm(array(1..3,[a,b,c]),3);

Puisqu'on utilise uniquement un tableau de taille n, sans en créer d'autres, l'occupation de la mémoire est un O(n). Il faut ajouter que cette vision est un peu optimiste parce que le simple fait d'ouvrir une session crée une table de hachage de grande taille. Le tableau que nous utilisons va venir s'ajouter à cette table et la mémoire occupée a donc une taille qui s'écrit n+K où K est une grosse constante alors que n va certainement rester assez petit vu le problème posé. On ne peut cependant pas nier que n+K soit un O(n).

Le package combstruct propose un itérateur sur les structures combinatoires qui permet de décrire toutes les objets d'une taille donnée. La structure combinatoire que sont les permutations est prédéfinie et la procédure est dans ce cas d'un emploi direct.

> allp := combstruct[iterstructs](Permutation([a,b,c]));

On pourrait voir le code de la procédure qui permet de passer d'une permutation à la suivante par les deux instructions que voici.

> interface(verboseproc=2):

> eval(allp[nextvalue]);

En tout cas, nous énumérons sans difficulté les permutations de [a,b,c].

> while not combstruct[finished](allp) do
      
    combstruct[nextstruct](allp) 

  od;

Retour en page principale