Aller au contenu

Tableaux autoréférents

Exercice d'après le sujet 0 du concours CCINP (filière MPI).

Définition

Soit \(n \in \N^*\). Un tableau \(t\) de taille \(n\) à valeurs dans \(\range{0}{n-1}\) est dit autoréférent lorsque, pour tout \(k \in \range{0}{n-1}\), \(t_k\) est le nombre d'occurrences de \(k\) dans \(t\) :

\[ \forall k \in \range{0}{n-1}, \quad t_k = \left| \enscomp{i \in \range{0}{n-1}}{t_i = k} \right| \]

Exemple

Le tableau [|1; 2; 1; 0|] est autoréférent : il contient une fois la valeur 0, deux fois la valeur 1, une fois la valeur 2 et aucune fois la valeur 3.

Les programmes sont à écrire en OCaml. On utilisera la fonction suivante qui renvoie la somme \(t_0 + \dots + t_{i-1}\) des \(i\) premières cases d'un tableau.

let somme t i =
    let s = ref 0 in
    for k = 0 to i-1 do
        s := !s + t.(k)
    done;
    !s

Vérification

Question 1. Montrer qu'il n'existe pas de tableau autoréférent de taille 1, 2 ou 3, et trouver un second tableau autoréférent de taille 4.

Corrigé
  • On a toujours \(t_0 \geq 1\) : si \(t_0 = 0\), la case \(0\) contient un 0, donc 0 apparaît au moins une fois, d'où \(t_0 \ge 1\), contradiction. De plus, si \(t_0 = a\) alors la valeur \(a \ge 1\) apparaît, donc \(t_a \geq 1\).
  • \(n = 1\) : le seul tableau est [|0|], exclu par le point précédent.
  • \(n = 2\) : \(t_0 = 1\), il y a donc un unique 0, nécessairement en case 1. Mais la valeur 1 apparaît (en case 0), donc \(t_1 \ge 1\) : contradiction.
  • \(n = 3\) : si \(t_0 = 2\), les deux 0 sont en cases 1 et 2, donc \(t_2 = 0\) alors que la valeur 2 apparaît. Si \(t_0 = 1\), la valeur 1 apparaît donc \(t_1 \geq 1\), et l'unique 0 est en case 2 : \(t = [|1;1;0|]\), qui contient deux 1 alors que \(t_1 = 1\), ou \(t = [|1;2;0|]\), qui contient un 2 alors que \(t_2 = 0\).
  • \(n = 4\) : [|2; 0; 2; 0|] est aussi autoréférent. On verra à la question 8 qu'il n'y en a pas d'autre.

Question 2. Écrire une fonction est_auto : int array -> bool qui teste si un tableau à valeurs dans \(\range{0}{n-1}\) est autoréférent, en temps \(O(n)\).

Corrigé

On compte les occurrences dans un second tableau puis on compare.

let est_auto t =
    let n = Array.length t in
    let t2 = Array.make n 0 in
    for i = 0 to n-1 do
        t2.(t.(i)) <- 1 + t2.(t.(i))
    done;
    t = t2

La boucle et la comparaison structurelle de deux tableaux de taille \(n\) sont en \(O(n)\).

Question 3. Montrer que si \(t\) est autoréférent de taille \(n\), alors \(\displaystyle \sum_{k=0}^{n-1} t_k = n\).

Corrigé

Chaque case \(i\) contient exactement une valeur \(t_i \in \range{0}{n-1}\), elle est donc comptée dans exactement un des \(t_k\), celui pour \(k = t_i\). Ainsi \(\sum_k t_k = \sum_k \left|\enscomp{i}{t_i = k}\right| = n\).

Génération par retour sur trace

Question 4. Écrire une fonction gen_auto : int -> int array list qui renvoie la liste des tableaux autoréférents de taille \(n\), en essayant toutes les valeurs possibles pour chaque case, de la gauche vers la droite. Quelle est sa complexité ?

Corrigé 
let gen_auto n =
    let solutions = ref [] in
    let t = Array.make n 0 in
    let rec aux i =
        if i = n
        then (if est_auto t
              then solutions := Array.copy t :: !solutions)
        else
            for k = 0 to n-1 do
                t.(i) <- k;
                aux (i+1)
            done
    in aux 0;
    !solutions

L'arbre des appels a \(n^n\) feuilles, chacune effectuant un test en \(O(n)\), et \(\sum_{i=0}^{n-1} n^i \leq n^n\) nœuds internes : la complexité est en \(O(n^{n+1})\).

Question 5. En utilisant la question 3, proposer un premier élagage : une condition sur \(t_0, \dots, t_{i-1}\) qui permet d'abandonner l'exploration. Écrire la fonction gen_auto_opt1 correspondante.

Corrigé

Comme les cases sont positives, si \(t_0 + \dots + t_{i-1} > n\) aucune complétion ne peut vérifier la question 3 : on peut abandonner.

let gen_auto_opt1 n =
    let solutions = ref [] in
    let t = Array.make n 0 in
    let rec aux i =
        if i = n
        then (if est_auto t
              then solutions := Array.copy t :: !solutions)
        else
            let elague =
                somme t i > n
            in
            if not elague
            then begin
                for k = 0 to n-1 do
                    t.(i) <- k;
                    aux (i+1)
                done
            end
    in aux 0;
    !solutions

Question 6. Lorsqu'on veut placer la valeur \(k\) en case \(i\) avec \(k < i\), la valeur \(t_k\) est déjà fixée. En déduire un second élagage, en maintenant un tableau occ tel que occ.(k) soit le nombre d'occurrences de \(k\) parmi \(t_0, \dots, t_{i-1}\). Écrire gen_auto_opt2.

Corrigé

Dans un tableau autoréférent, la valeur \(k\) apparaît exactement \(t_k\) fois. Si \(k < i\), on ne peut donc placer une nouvelle occurrence de \(k\) que si occ.(k) < t.(k). Si \(k \ge i\), \(t_k\) n'est pas encore choisi et il n'y a pas de contrainte. On met à jour occ avant l'appel récursif et on le restaure après.

let gen_auto_opt2 n =
    let solutions = ref [] in
    let t = Array.make n 0 in
    let occ = Array.make n 0 in
    let rec aux i =
        if i = n
        then (if est_auto t
              then solutions := Array.copy t :: !solutions)
        else
            let elague =
                somme t i > n
            in
            if not elague
            then begin
                for k = 0 to n-1 do
                    if k >= i || occ.(k) < t.(k)
                    then begin
                        t.(i) <- k;
                        occ.(k) <- occ.(k) + 1;
                        aux (i+1);
                        occ.(k) <- occ.(k) - 1
                    end
                done
            end
    in aux 0;
    !solutions

Question 7. Soit \(t\) autoréférent et \(i \in \range{1}{n}\). On note \(s = t_0 + \dots + t_{i-1}\) et \(o\) le nombre de 0 parmi \(t_0, \dots, t_{i-1}\). Montrer que \(s \leq i + t_0 - o\). En déduire gen_auto_opt3.

Corrigé

D'après la question 3, \(n = \sum_{j=0}^{n-1} t_j = s + \sum_{j=i}^{n-1} t_j\). Parmi les \(n - i\) cases \(t_i, \dots, t_{n-1}\), exactement \(t_0 - o\) valent 0 (il y a \(t_0\) zéros en tout), les \((n - i) - (t_0 - o)\) autres valent au moins 1. Ainsi \(\sum_{j \ge i} t_j \geq n - i - t_0 + o\), d'où \(s \leq n - (n - i - t_0 + o) = i + t_0 - o\).

On peut donc abandonner dès que \(s > i + t_0 - o\), ce qui raffine la condition \(s > n\) (pour \(i = 0\), \(s = 0\) et la condition est fausse : t.(0) vaut encore sa valeur initiale 0, sans conséquence).

let gen_auto_opt3 n =
    let solutions = ref [] in
    let t = Array.make n 0 in
    let occ = Array.make n 0 in
    let rec aux i =
        if i = n
        then (if est_auto t
              then solutions := Array.copy t :: !solutions)
        else
            let elague =
                let s = somme t i in
                s > n || s > i + t.(0) - occ.(0)
            in
            if not elague
            then begin
                for k = 0 to n - 1 do
                    if k >= i || occ.(k) < t.(k)
                    then begin
                        t.(i) <- k;
                        occ.(k) <- occ.(k) + 1;
                        aux (i + 1);
                        occ.(k) <- occ.(k) - 1
                    end
                done
            end
    in aux 0;
    !solutions

Remarque

somme t i coûte \(O(i)\) à chaque appel. On pourrait passer la somme partielle en argument de aux pour la maintenir en temps constant.

Question 8. Donner les tableaux autoréférents pour \(n \le 11\). Que conjecturer ?

Corrigé

Les quatre fonctions renvoient les mêmes solutions pour \(n \leq 7\) (et les deux dernières jusqu'à \(n = 11\)) :

\(n\) tableaux autoréférents
1, 2, 3, 6 aucun
4 [|1;2;1;0|], [|2;0;2;0|]
5 [|2;1;2;0;0|]
7 [|3;2;1;1;0;0;0|]
8 [|4;2;1;0;1;0;0;0|]
9 [|5;2;1;0;0;1;0;0;0|]
10 [|6;2;1;0;0;0;1;0;0;0|]
11 [|7;2;1;0;0;0;0;1;0;0;0|]

On conjecture que pour \(n \ge 7\) l'unique tableau autoréférent est \(t_0 = n - 4\), \(t_1 = 2\), \(t_2 = 1\), \(t_{n-4} = 1\) et \(t_k = 0\) sinon (on vérifie facilement qu'il est autoréférent ; l'unicité est admise).