On suppose qu'une fonction rand() est disponible qui retourne un entier pseudo-aléatoire distribué uniformément dans [0...N).
fonction randint(val a,b : entier):entier;
var n:entier;
debut
n:=N/(b-a+1); /*arrondi a l'entier plus bas*/
retourne(a+rand()/n);
fin
finfonction
procédure choisir(ref P:tab; ref i:entier);
var x:réel;
début
x:=(rand()+0.0)/N);
i:=1;
tantque i<m ET x>P[i] faire
/* test i<m nécessaire en raison d'arithmétique réelle inexacte*/
x:=x-P[i];
i:=i+1
fintantque;
finprocédure;
Dans les deux exercices qui suivent, on veut construire un graphe aléatoire, non-orienté et régulier (tous les sommets ont le même degré d), sur l'ensemble de sommets 1...2n. Ce graphe peut être représenté par une matrice d'adjacence ou par une autre représentation plus compacte.
procedure couplage(val n:entier; ref Tableau: C);
var i, j, posj, compteur, restant:entier;
var DISP: Tableau 1..2*n de entier;
debut
pour compteur allant de 1 a 2*n faire
DISP[compteur]:=compteur;
restant=2n;
/* les nombres restant disponibles sont dans DISP entre [1] et [restant]*/
pour compteur allant de 1 a n faire
i:=DISP[restant];
restant:=restant-1;
posj:=randint(1,restant);
j:=DISP[posj];
DISP[posj]:=DISP[restant];
restant=restant-1;
/*signaler en C que i et j sont couples*/
C[j]:=i;
C[i]:=j;
finpour;
fin
finprocedure
Réponse: Oui (si on suppose que randint est uniforme)
procedure graphe(val n, d: entier; ref Tableau2D: G);
var reussi: booleen;
var coup, i, coup2: entier;
debut
repeter
pour coup allant de 1 a d faire
couplage(n,G[coup]);
finpour;
reussi:=vrai;
pour i allant de 1 a 2*n-1 faire
/* reussi = faux si i a le meme partenaire en deux couplages*/
pour coup allant de 1 a d-1 faire
pour coup2 allant de coup+1 a d faire
si G[coup][i]=G[coup2][i] alors
reussi:=faux;
finsi;
finpour;
finpour;
finpour;
jusqu'a reussi finrepeter;
fin
finprocedure
/*il serait plus efficace de sortir des boucles des qu'un
sommet a le meme partenaire en deux couplages*/