Chapitre 1 : Numérotations Table des matières

Chapitre 1 : Annexe

  1. Couples et triplets
  2. Listes d'entiers
  3. Ensembles d'entiers

1. Couples et triplets

Voici le code de fonctions de numérotation pour les couples et les triplets

struct couple {
  int x, y;
};

struct triplet {
  int x, y, z;
};

typedef struct couple couple;
typedef struct triplet triplet;

/* Numérotation des couples */

int numeroCouple (couple c) {
  int d = c.x + c.y;
  return d * (d  + 1) / 2 + c.y;
}

couple coupleNumero (int n) {
  int d, t = 0;
  couple c;
  
  for (d = 1; ; d++) {
    t = t + d;
    if (t > n) break;
  }
  /* reculer */
  t = t - d;
  d--;
  c.y = n - t;
  c.x = d - c.y;
  return c;
}

/* conversions entre couples et triplets */

couple t2c (triplet t) {
  couple c = {t.x, t.y};
  int n = numeroCouple (c);
  c.x = n;
  c.y = t.z;
  return c;
}

triplet c2t (couple c) {
  triplet t;
  t.z = c.y;
  c = coupleNumero (c.x);
  t.x = c.x;
  t.y = c.y;
  return t;
}

int numeroTriplet (triplet t) {
  return numeroCouple (t2c (t));
}

triplet tripletNumero (int n) {
  return c2t (coupleNumero (n));
}

Voici le début de la numérotation des couples et triplets :

0 -> (0, 0) -> (0, 0, 0) -> 0
1 -> (1, 0) -> (1, 0, 0) -> 1
2 -> (0, 1) -> (0, 0, 1) -> 2
3 -> (2, 0) -> (0, 1, 0) -> 3
4 -> (1, 1) -> (1, 0, 1) -> 4
5 -> (0, 2) -> (0, 0, 2) -> 5
6 -> (3, 0) -> (2, 0, 0) -> 6
7 -> (2, 1) -> (0, 1, 1) -> 7
8 -> (1, 2) -> (1, 0, 2) -> 8
9 -> (0, 3) -> (0, 0, 3) -> 9
10 -> (4, 0) -> (1, 1, 0) -> 10
11 -> (3, 1) -> (2, 0, 1) -> 11
12 -> (2, 2) -> (0, 1, 2) -> 12
13 -> (1, 3) -> (1, 0, 3) -> 13
14 -> (0, 4) -> (0, 0, 4) -> 14
15 -> (5, 0) -> (0, 2, 0) -> 15
16 -> (4, 1) -> (1, 1, 1) -> 16
17 -> (3, 2) -> (2, 0, 2) -> 17
18 -> (2, 3) -> (0, 1, 3) -> 18
19 -> (1, 4) -> (1, 0, 4) -> 19
20 -> (0, 5) -> (0, 0, 5) -> 20
21 -> (6, 0) -> (3, 0, 0) -> 21
22 -> (5, 1) -> (0, 2, 1) -> 22
23 -> (4, 2) -> (1, 1, 2) -> 23
24 -> (3, 3) -> (2, 0, 3) -> 24

2. Listes d'entiers

Voici le code de fonctions de numérotation pour les listes. Celles-ci, dans le code ci-dessous, ont une taille fixe, choisie en accord avec la taille des entiers C (type int) sur les machines courantes (32 bits), taille qui limite sévèrement les numérotations de listes ; noter que par exemple x + y + 2 bits sont nécessaires, avec l'algorithme ci-dessous, pour le numéro de la liste à deux éléments x et y. Maple, qui possède un type standard liste, et manipule des entiers de taille quelconque, serait un langage préférable pour réaliser la numérotation des listes, ce qui n'empêcherait pas d'atteindre rapidement les limites pratiques de l'algorithme (comme souvent en calculabilité), puisque le nombre de bits du numéro est déterminé essentiellement par la somme des entiers qui composent la liste.

struct liste {
  int taille;
  int element [32];
};

typedef struct liste liste;

int numeroListe (liste u) {
  int i, j, n = 0;
  
  for (i = u.taille - 1; i >= 0; i--) {
    n = 2 * n + 1;
    for (j = 0; j < u.element [i]; j++)
      n = 2 * n;
  }
  return n;
}

liste listeNumero (int n) {
  int t = 0, x = 0;
  liste u;
  
  while (n > 0) {
    if (n % 2 == 0) x++;
    else {
      u.element [t++] = x;
      x = 0;
    }
    n = n / 2;
  }
  u.taille = t;
  return u;
}

Voici le début de la numérotation des listes ; on a ajouté l'opération miroir, qui renverse une liste ; la fonction composée, qui associe, sur chaque ligne ci-dessous, l'entier le plus à droite à l'entier le plus à gauche, est la traduction "arithmétique" du miroir ; ceci illustre le principe selon lequel toute procédure informatique peut être vue comme calculant une fonction N → N.

0 -> [] -> [] -> 0
1 -> [0] -> [0] -> 1
2 -> [1] -> [1] -> 2
3 -> [0, 0] -> [0, 0] -> 3
4 -> [2] -> [2] -> 4
5 -> [1, 0] -> [0, 1] -> 6
6 -> [0, 1] -> [1, 0] -> 5
7 -> [0, 0, 0] -> [0, 0, 0] -> 7
8 -> [3] -> [3] -> 8
9 -> [2, 0] -> [0, 2] -> 12
10 -> [1, 1] -> [1, 1] -> 10
11 -> [1, 0, 0] -> [0, 0, 1] -> 14
12 -> [0, 2] -> [2, 0] -> 9
13 -> [0, 1, 0] -> [0, 1, 0] -> 13
14 -> [0, 0, 1] -> [1, 0, 0] -> 11
15 -> [0, 0, 0, 0] -> [0, 0, 0, 0] -> 15
16 -> [4] -> [4] -> 16
17 -> [3, 0] -> [0, 3] -> 24
18 -> [2, 1] -> [1, 2] -> 20
19 -> [2, 0, 0] -> [0, 0, 2] -> 28
20 -> [1, 2] -> [2, 1] -> 18
21 -> [1, 1, 0] -> [0, 1, 1] -> 26
22 -> [1, 0, 1] -> [1, 0, 1] -> 22
23 -> [1, 0, 0, 0] -> [0, 0, 0, 1] -> 30
24 -> [0, 3] -> [3, 0] -> 17

Voici des exemples de listes avec de "grands" numéros (on pourra méditer sur les codes hexadécimaux de 1000000 et 528919, à savoir f4240 et 81217) :

1000000 -> [0, 0, 0, 1, 4, 2, 6] -> [6, 2, 4, 1, 0, 0, 0] -> 528919
1000001 -> [0, 0, 0, 1, 4, 2, 5, 0] -> [0, 5, 2, 4, 1, 0, 0, 0] -> 791063
1000002 -> [0, 0, 0, 1, 4, 2, 4, 1] -> [1, 4, 2, 4, 1, 0, 0, 0] -> 659991
1000003 -> [0, 0, 0, 1, 4, 2, 4, 0, 0] -> [0, 0, 4, 2, 4, 1, 0, 0, 0] -> 922135
1000004 -> [0, 0, 0, 1, 4, 2, 3, 2] -> [2, 3, 2, 4, 1, 0, 0, 0] -> 594455
1000005 -> [0, 0, 0, 1, 4, 2, 3, 1, 0] -> [0, 1, 3, 2, 4, 1, 0, 0, 0] -> 856599
1000006 -> [0, 0, 0, 1, 4, 2, 3, 0, 1] -> [1, 0, 3, 2, 4, 1, 0, 0, 0] -> 725527
1000007 -> [0, 0, 0, 1, 4, 2, 3, 0, 0, 0] -> [0, 0, 0, 3, 2, 4, 1, 0, 0, 0] -> 987671
1000008 -> [0, 0, 0, 1, 4, 2, 2, 3] -> [3, 2, 2, 4, 1, 0, 0, 0] -> 561687
1000009 -> [0, 0, 0, 1, 4, 2, 2, 2, 0] -> [0, 2, 2, 2, 4, 1, 0, 0, 0] -> 823831
1000010 -> [0, 0, 0, 1, 4, 2, 2, 1, 1] -> [1, 1, 2, 2, 4, 1, 0, 0, 0] -> 692759
1000011 -> [0, 0, 0, 1, 4, 2, 2, 1, 0, 0] -> [0, 0, 1, 2, 2, 4, 1, 0, 0, 0] -> 954903
1000012 -> [0, 0, 0, 1, 4, 2, 2, 0, 2] -> [2, 0, 2, 2, 4, 1, 0, 0, 0] -> 627223
1000013 -> [0, 0, 0, 1, 4, 2, 2, 0, 1, 0] -> [0, 1, 0, 2, 2, 4, 1, 0, 0, 0] -> 889367
1000014 -> [0, 0, 0, 1, 4, 2, 2, 0, 0, 1] -> [1, 0, 0, 2, 2, 4, 1, 0, 0, 0] -> 758295
1000015 -> [0, 0, 0, 1, 4, 2, 2, 0, 0, 0, 0] -> [0, 0, 0, 0, 2, 2, 4, 1, 0, 0, 0] -> 1020439
1000016 -> [0, 0, 0, 1, 4, 2, 1, 4] -> [4, 1, 2, 4, 1, 0, 0, 0] -> 545303

3. Ensembles d'entiers

Le type liste est aussi utilisé pour représenter un ensemble.

int numeroEnsemble (liste u) {
  int i, j, k, n = 0;
  
  for (i = u.taille - 1; i >= 0; i--) {
    n = 2 * n + 1;
    if (i > 0)
      k = u.element [i-1] + 1;
    else
      k = 0;
    for (j = k; j < u.element [i]; j++)
      n = 2 * n;
  }
  return n;
}

liste ensembleNumero (int n) {
  int i, t = 0;
  liste u;
  
  for (i = 0; n > 0; i++) {
    if (n % 2)
      u.element [t++] = i;
    n = n / 2;
  }
  u.taille = t;
  return u;
}

Voici le début de la numérotation des ensembles :

0 -> []
1 -> [0]
2 -> [1]
3 -> [1, 0]
4 -> [2]
5 -> [2, 0]
6 -> [2, 1]
7 -> [2, 1, 0]
8 -> [3]
9 -> [3, 0]
10 -> [3, 1]
11 -> [3, 1, 0]
12 -> [3, 2]
13 -> [3, 2, 0]
14 -> [3, 2, 1]
15 -> [3, 2, 1, 0]
16 -> [4]
17 -> [4, 0]
18 -> [4, 1]
19 -> [4, 1, 0]
20 -> [4, 2]
21 -> [4, 2, 0]
22 -> [4, 2, 1]
23 -> [4, 2, 1, 0]
24 -> [4, 3]

Voici les ensembles de numéro voisin de un million (comparer avec les listes correspondantes ci-dessus) :

1000000 -> [19, 18, 17, 16, 14, 9, 6]
1000001 -> [19, 18, 17, 16, 14, 9, 6, 0]
1000002 -> [19, 18, 17, 16, 14, 9, 6, 1]
1000003 -> [19, 18, 17, 16, 14, 9, 6, 1, 0]
1000004 -> [19, 18, 17, 16, 14, 9, 6, 2]
1000005 -> [19, 18, 17, 16, 14, 9, 6, 2, 0]
1000006 -> [19, 18, 17, 16, 14, 9, 6, 2, 1]
1000007 -> [19, 18, 17, 16, 14, 9, 6, 2, 1, 0]
1000008 -> [19, 18, 17, 16, 14, 9, 6, 3]
1000009 -> [19, 18, 17, 16, 14, 9, 6, 3, 0]
1000010 -> [19, 18, 17, 16, 14, 9, 6, 3, 1]
1000011 -> [19, 18, 17, 16, 14, 9, 6, 3, 1, 0]
1000012 -> [19, 18, 17, 16, 14, 9, 6, 3, 2]
1000013 -> [19, 18, 17, 16, 14, 9, 6, 3, 2, 0]
1000014 -> [19, 18, 17, 16, 14, 9, 6, 3, 2, 1]
1000015 -> [19, 18, 17, 16, 14, 9, 6, 3, 2, 1, 0]
1000016 -> [19, 18, 17, 16, 14, 9, 6, 4]

Note. Un lecteur attentif remarquera que, dans tous les exemples ci-dessus, les listes (qui servent aussi à représenter des ensembles) sont affichées dans l'ordre inverse de leur implantation en mémoire (autrement dit l'élément d'indice 0 est affiché en dernier) ; ainsi, les entiers affichés en tête de liste sont ceux "de poids fort", qui varient le moins vite lors d'une énumération ; c'est la même convention que pour l'écriture des chiffres d'un nombre (on écrit en premier, c'est à dire à gauche, les chiffres de poids fort d'un nombre).