X-PC 2010
> restart;
> allouer:=proc(m)
> RETURN(array(1..m))
> end:
> t:=allouer(4);

                        t := array(1 .. 4, [])

> taille:=proc(t)
> RETURN(op(2,op(2,op(1,t))))
> end:
> taille(t);

                                  4

> evaluation:=proc(P,v)
> local horn,m,k;
> horn:=0;
> m:=taille(P);
> for k from 0 to m-1 do
>         horn:=(horn +P[m-k])*v
> od;
> RETURN(horn)
> end:
> P:=array(1..4,[-1,1,0,1]);evaluation(P,3);

                          P := [-1, 1, 0, 1]


                                  87

> valuation:=proc(P)
> local va,m,k;
> m:=taille(P);
> va:=1;
> k:=1;
> while P[k]=0 and k<m do 
>           va:=va+1;
>           k:=k+1 
> od;
> if va=m and P[m]=0 then
>      va:=0
> fi;
> RETURN(va)
> end:
> valuation(P);

                                  1

> difference:=proc(P1,P2)
> local m1,m2,diff,k;
> m1:=taille(P1);
> m2:=taille(P2);
> if m1>=m2 then
>      diff:=allouer(m1);
>      for k from 1 to m2 do
>             diff[k]:=P1[k]-P2[k]
>      od;
>      for k from m2+1 to m1 do
>             diff[k]:=P1[k]
>      od;
> else 
>      diff:=difference(P2,P1);
>      for k from 1 to m2 do
>              diff[k]:=-diff[k]
>      od;
> fi;
> RETURN(diff);
> end:
> P1:=array(1..4,[-1,1,0,1]);P2:=array(1..3,[-2,1,1]);

                         P1 := [-1, 1, 0, 1]


                           P2 := [-2, 1, 1]

> eval(difference(P2,P1));

                            [-1, 0, 1, -1]

> compare_neg:=proc(P1,P2)
> local diff,v;
> diff:=difference(P1,P2);
> v:=valuation(diff);
> if v<>0 and (-1)^v*diff[v]<0 then
>        RETURN(-v)
> else RETURN(v)
> fi;
> end:
> compare_neg(P1,P2);compare_neg(P1,P1);

                                  -1


                                  0

> tri:=proc(t)
> local n,sous_t,sous_t_trie,t_trie,k,i;
> n:=taille(t);
> if n=1 then 
>       RETURN(t);
> else
>       sous_t:=allouer(n-1);
>       t_trie:=allouer(n);
>       for k from 1 to n-1 do 
>                    sous_t[k]:=t[k]
>       od;
>       sous_t_trie:=tri(sous_t);
>       k:=1;
>       while k<n and compare_neg(sous_t_trie[k],t[n])>0 do
>                    t_trie[k]:=sous_t_trie[k];
>                    k:=k+1 
>       od;
>       t_trie[k]:=t[n];
>       for i from k+1 to n do   
>                    t_trie[i]:=sous_t_trie[i-1]
>       od;
> fi;
> RETURN(t_trie)
> end:
> P1:=array(1..1,[0]);P2:=array(1..2,[0,1]);P3:=array(1..3,[0,0,-1]);t:=array(1..3,[P2,P3,P1]);tt:=array(1..3,[P1,P2,P3]);

                              P1 := [0]


                             P2 := [0, 1]


                           P3 := [0, 0, -1]


                          t := [P2, P3, P1]


                          tt := [P1, P2, P3]

> eval(tri(t));

                             [P2, P3, P1]

> compare_pos:=proc(P1,P2)
> local diff,v;
> diff:=difference(P1,P2);
> v:=valuation(diff);
> if v<>0 and diff[v]<0 then
>        RETURN(-v)
> else RETURN(v)
> fi;
> end:
> verifier_permute:=proc(pi,t)
> local n,perm,k,reponse,t_trie;
> n:=taille(t);
> perm:=allouer(n);
> for k from 1 to n do
>         perm[k]:=t[pi[k]]
> od;
> reponse:=`vrai`;
> for k from 1 to n-1 do
>         if compare_pos(perm[k+1],perm[k])>0 then
>                reponse:=`faux`
>         fi;
> od;
> RETURN(reponse)
> end:
> 
> pi:=array(1..3,[1,3,2]);verifier_permute(pi,t);pi:=array(1..3,[3,1,2]);verifier_permute(pi,t);

                           pi := [1, 3, 2]


                                 vrai


                           pi := [3, 1, 2]


                                 faux

> est_echangeur_aux:=proc(pi,d)
> local pid,reponse,pic,pib,c,a,b,n;
> n:=taille(pi);
> ;pid:=pi[d];
> reponse:=`vrai`;
> for c from d+1 to n-2 do
>         pic:=pi[c];
>         for b from c+1 to n-1 do
>                 pib:=pi[b];
>                 for a from b+1 to n do
>                        if pib>pid and pid>pi[a] and pi[a]>pic then 
>                                     reponse:=`faux`
>                        elif pic>pi[a] and pi[a]>pid and pid>pib then
>                                     reponse:=`faux`
>                        fi;
>                 od;
>         od;
> od;
> RETURN(reponse)
> end:
> est_echangeur:=proc(pi)
> local k,reponse,n;
> n:=taille(pi);
> reponse:=`vrai`;
> for k from 3 to n-1 do
>         if est_echangeur_aux(pi,n-k)=`faux` then
>              reponse:=`faux`
>         fi;
> od;
> RETURN(reponse)
> end:
> pi:=array(1..4,[1,2,3,4]);est_echangeur(pi);pi1:=array(1..4,[3,1,4,2]);est_echangeur(pi1);

                          pi := [1, 2, 3, 4]


                                 vrai


                         pi1 := [3, 1, 4, 2]


                                 faux

> nombre_echangeur:=proc(n)
> local nbre,k;
> if n=1 then
>     nbre:=1
> else
>     nbre:=nombre_echangeur(n-1);
>     for k from 1 to n-1 do
>             nbre:=nbre+nombre_echangeur(k)*nombre_echangeur(n-k)
>     od;
> fi;
> RETURN(nbre)
> end:
> 
> nombre_echangeur(4);

                                  22

> decaler:=proc(t,v)
> local n,u,k;
> n:=taille(t);
> u:=allouer(n+1);
> u[1]:=v;
> for k from 2 to n+1 do
>      if t[k-1]<v then
>               u[k]:=t[k-1]
>      else
>               u[k]:=1+t[k-1]
>      fi;
> od;
> RETURN(u)
> end:
> enumerer_echangeurs:=proc(n)
> local tab,a,sous_tab,b,k,i,v,u,tt,j;
> if n=1 then 
>      tab:=allouer(1);
>      tab[1]:=allouer(1);
>      tab[1][1]:=1;
> else
>      a:=nombre_echangeur(n);
>      tab:=allouer(a);
>      sous_tab:=enumerer_echangeurs(n-1);
>      b:=nombre_echangeur(n-1);
>      k:=1;
>      for i from 1 to b do
>             for v from 1 to n do
>                     tt:=allouer(n-1);
>                     for j from 1 to n-1 do tt[j]:=sous_tab[i][j] od;
>                     u:=decaler(tt,v);
>                     if est_echangeur_aux(u,1)=`vrai` then
>                            tab[k]:=eval(u);
>                            k:=k+1
>                     fi;
>             od;
>      od; 
> fi;
> RETURN(tab)
> end:
> 
>                
> for k from 1 to 4 do eval(enumerer_echangeurs(k)) od;

                                [[1]]


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


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


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

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

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

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

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

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

>