- Génération aléatoire d'une partition33 3.6. - Génération aléatoire d'une partition impaire40 3.7. - Génération aléatoire d'une partition paire44 3.8. - Génération aléatoire d'une partition stricte49 4. - Programme de génération aléatoire d'une partition d'entier59 4.6. - Programme de génération aléatoire d'une partition stricte d'entier66 5. - Ils permettent de générer aléatoirement une partition impaire, une partition paire ou une partition stricte. - Tous ces algorithmes assurent la distribution uniforme et sont basés sur la méthode de génération aléatoire d'une partition [5][6. - (7, 4, 2, 2, 1) est une partition de 16.. - (8, 5, 2, 1) est une partition stricte de 16.. - (5, 5, 3, 3) est une partition impaire de 16.. - (6, 4, 2, 2, 2) est une partition paire de 16.. - Ils permettent de générer aléatoirement une partition impaire, une partition paire ou une partition stricte. - Tous ces algorithmes assurent la distribution uniforme et sont basés sur la méthode d'Euler [5][6] pour générer aléatoirement une partition qui se situe dans la section 3.5. - Partition paire : Une partition paire d'un entier positif n est une séquence décroissante . - Il n'y a qu'une partition de n parties de l'entier n. - λ λ 1 , λ 2 , ...,λ k ) est une partition de n ayant précisément k parties n = λ. - Cette forme est une partition de l'entier n.. - Cette forme est une partition de 12. - Considérer la partie x i ≥ 3 dans une partition. - Dans cette section, nous introduisons l'algorithme d'Euler pour générer aléatoirement une partition. - Ce principe est appliqué dans l'algorithme pour générer aléatoirement une partition d'entier. - Maintenant, on appliquera ce principe général pour générer aléatoirement une partition de n.. - La deuxième preuve de (3.6) est une preuve combinatoire basée sur la représentation de multiplicité de partitions et elle est la base de l'algorithme de génération aléatoire d'une partition dans cette partie.. - Soit ' une partition de n. - Nous pouvons maintenant décrire l'algorithme de génération aléatoire d'une partition de l'entier n.. - Sortie : Une partition de n. - 0, on arrête et on a une partition de n. - 3.5.3.3 Complexité de l'algorithme de génération aléatoire d'une partition d'Euler Premièrement, nous calculons les opérations dans chaque fois de répétition de l'algorithme. - La partition P est initialisée par une partition vide. - 0, on arrête et on a une partition de l'entier n. - L'algorithme a la complexité maximale quand il génère aléatoirement une partition sous forme (1,1,...,1). - Alors, la complexité maximale de génération aléatoire d'une partition est égale à . - Soit ' une partition de n. - Π la probabilité pour avoir une partition de l'entier m <. - La section 3.5 vient de présenter l'algorithme de génération aléatoire d'une partition. - partition impaire et une partition paire. - 3.6 Génération aléatoire d'une partition impaire. - 3.6.1 Algorithme de génération aléatoire d'une partition impaire . - L'idée de cet algorithme est identique avec la génération aléatoire d'une partition dans la section 3.5. - Sortie : une partition impaire de n.. - 0, on arrête et on a une partition impaire de l'entier n. - 3.6.2.3 Complexité de notre algorithme pour générer aléatoirement une partition impaire . - La partition P est initialisée par une partition . - Table 7 – Complexité de génération aléatoire d'une partition impaire Selon l'analyse au dessus, la complexité de l'algorithme dans chaque fois de répétition est . - L'algorithme a la complexité maximale quand il génère aléatoirement une partition impaire sous forme (1,1,...,1). - Alors, la complexité maximale de génération aléatoire d'une partition est . - Soit ' une partition impaire de n. - Π la probabilité pour avoir une partition impaire de l'entier m <. - Nous venons de prouver que tous les partitions impaires de n' ont la même probabilité de génération et la probabilité de génération aléatoire d'une partition impaire est égale à . - Dans la section suivante, nous continuons à introduire l'algorithme de génération d'une partition paire. - 3.7 Génération aléatoire d'une partition paire. - 3.7.2 Algorithme de génération aléatoire d'une partition paire. - L'idée de notre algorithme est identique avec la génération aléatoire d'une partition dans la section 3.5. - Sortie : une partition paire de n.. - 0, on arrête et on a une partition paire de l'entier n. - Soit ' une partition paire de n. - Π la probabilité pour avoir une partition paire de l'entier m <. - 3.8 Génération aléatoire d'une partition stricte. - Nous pouvons utiliser la méthode de bijection pour générer aléatoirement une partition stricte. - Tout d'abord, nous générons aléatoirement une partition impaire. - Puis, nous convertissons cette partition pour avoir une partition stricte. - 3.8.1 Bijection d' Euler pour transformer entre une partition stricte et une partition impaire. - Transformation d'une partition impaire à une partition stricte. - Une partition impaire de l'entier n peut être écrite comme suite : n= μ 1 . - Cette représentation obtenue est une partition stricte de n.. - On a (30, 22, 15, 10, 7, 5, 4, 3) qui est une partition stricte de 96.. - On a (7, 5, 3, 3, 1, 1) qui est une partition impaire de 20.. - Nous avons introduit un algorithme d'Euler qui permet de générer aléatoirement une partition. - Nos algorithmes permettent à générer aléatoirement une partition impaire, une partition paire ou une partition stricte. - Générer aléatoirement une partition d'un entier 4.5.1 Algorithme, complexité et distribution uniforme. - Une liste d'entiers pour contenir une partition impaire.. - cette procédure génère aléatoirement une partition de n. - Figure 12 –Une partition de 250. - Une liste d'entiers pour contenir une partition impaire.. - cette procédure génère aléatoirement une partition impaire.. - Le programme génère aléatoirement une partition impaire de 350.. - Figure 13 – Une partition impaire de 350 . - – La complexité du programme est identique avec le programme pour générer aléatoirement une partition impaire.. - Une liste d'entiers pour contenir une partition paire.. - Les classes et les procédures de ce programme sont identiques aves le programme pour générer aléatoirement une partition impaire. - cette procédure génère aléatoirement une partition paire de n.. - Le programme génère aléatoirement une partition paire de 500.. - Figure 14 – Une partition paire de 500 . - Premièrement, nous générons une partition impaire. - – Avec une partition impaire, nous aurons une partition stricte. - Donc, la distribution uniforme de génération aléatoire d'une partition stricte est égale à 1/op(n) où op(n) est le nombre des partitions impaires de n. - cette procédure génère aléatoirement une partition impaire de n.. - La classe StrictePartition pour tranformer d'une partition impaire à une partition stricte. - cette procédure transforme une partition impaire pour obtenir une partition stricte. - Le programme génère aléatoirement une partition stricte de 400.. - Figure 15 – Une partition stricte de 400 4.9. - Ensuite, nous avons continué à introduire dans le chapitre 3 deux algorithmes de génération tous les partitions et un algorithme pour générer aléatoirement une partition. - Nos algorithmes permettent à générer aléatoirement une partition impaire, une partition paire ou une partition stricte. - Le premier axe est d'étudier la génération aléatoire d'objets comme les partitions kstrictes (une partition kstricte ayant (a i a i+1. - Particulièrement, nous voulons trouver des méthodes permettant de génération aléatoirement une partition plane. - Programme de génération aléatoire d'une partition d'entier. - Programme de génération aléatoire d'une partition impaire d'entier. - Programme de génération aléatoire d'une partition paire d'entier. - Programme de génération aléatoire d'une partition stricte d'entier