Il est possible d'avoir la note maximale même sans traiter l'intégralité du sujet.

N'oubliez pas de déposer votre fichier comme indiqué à la fin du sujet.

Introduction

Nous considérons le problème de la génération des partitions d'un entier.

Définition

• n₁ + n₂ + ... + n_k = n
• n₁ ≥ n₂ ≥ ... ≥ n_k > 0

Les entiers n_i sont appelés parties de la partition.

Exemple

Les partitions de l'entier 4 sont les listes

(4)
(3,1)
(2,2)
(2,1,1)
(1,1,1,1)

Représentation graphique des partitions

Il est en général pratique de représenter graphiquement les partitions. Par exemple la partition (6,4,3,1) de l'entier 14 peut être représentée par le diagramme

oooooo
oooo
ooo
o

Ainsi, on associe à une partition (n₁,...,n_k) de n un diagramme de k lignes. Le diagramme contient au total n cercles. Sur la ligne numéro i, on met n_i cercles.

Représentation Java d'une partition

Nous représenterons une partition comme une liste d'entiers.

On fournit un squelette Partition.java à compléter dans les questions suivantes.

Écrire la méthode public String toString() de la classe Partition. Chaque partie n_i de la partition (n₁,...,n_k) sera affichée sur une ligne distincte: on affichera l'entier n_i suivi de n_i cercles (pour obtenir un cercle, on affiche la lettre "o" minuscule).

Tester à l'aide de la fonction main suivante:

public static void main(String[] args) {
		Partition p = new Partition(9,new Partition(8,new Partition(4,new Partition(1,null))));
		System.out.println("Affichage de la partition (9,8,4,1):\n" + p);

	}

L'exécution de java Partition avec la méthode main donnée devra donner

Affichage de la partition (9,8,4,1):
9 ooooooooo
8 oooooooo
4 oooo
1 o

Représentation Java d'une liste de partitions

On représente l'ensemble des partitions d'un entier par une liste d'objets de la classe Partition (la classe que nous venons de définir dans la question précédente). Ces listes de partitions sont représentées par des objets de la classe PartitionList.

Pour créer la liste des partitions de l'entier 2 constituée des partitions (2) et (1,1) on peut par exemple faire

Partition p1 = new Partition(2,null);
Partition p2 = new Partition(1, new Partition(1,null));
PartitionList p = new PartitionList(p1, new PartitionList(p2,null));

Union de deux listes de partitions

Dans la classe PartitionList écrire une fonction public static PartitionList union(PartitionList p1,PartitionList p2) qui renvoie l'union de p1 et de p2. Cette fonction devra être persistante c'est-à-dire ne pas modifier p1 et ne pas modifier p2. Il n'est pas obligatoire que l'ordre des éléments dans p1 et p2 soit respecté.

Tester votre programme avec la fonction main suivante (dans la classe PartitionList):

	public static void main(String[] args) {
		//p1 est constituté la partition (1)
		PartitionList p1 = new PartitionList(new Partition(1,null),null);
		
		//p2 est constitué de la partition (1) et de la partition (2)
		PartitionList p2 = new PartitionList(new Partition(1,null),new PartitionList(new Partition(2,null),null));
		
		//p3 est constitué des partitions (3) et (4)
		PartitionList p3 = new PartitionList(new Partition(3,null),new PartitionList(new Partition(4,null),null));
		
		//pl_null est la liste vide
		PartitionList pl_null = null;
		
		System.out.println("L'union de la liste de partitions contenant la partition (1) et de la liste de partitions null donne" + union(p1,pl_null));
		System.out.println("L'union de la liste de partitions null et de la liste de partitions contenant la partition (1) donne" + union(pl_null,p1));
		System.out.println("L'union de la liste de partitions contenant les partitions (1) et (2) et de la liste de partitions contenant la partition (3,4) donne" + union(p2,p3));
	}

Insertion en tête

Dans la classe PartitionList écrire une fonction public static PartitionList insert(int m, PartitionList l) qui crée une nouvelle liste obtenue en ajoutant m en tête de tous les éléments de l. Cette fonction devra être persistante. On supposera que m est plus grand que tous les entiers présents dans les partitions de la liste l, afin de préserver la condition de décroissance des parties et donc, obtenir effectivement comme résultat de cette fonction une liste de partitions.

Tester votre programme avec la fonction main suivante (dans la classe PartitionList):

	public static void main(String[] args) {
			//p3 est constitué  des partition (3) et (4)
			PartitionList p3 = new PartitionList(new Partition(3,null),new PartitionList(new Partition(4,null),null));

			//pl_null est la liste vide
			PartitionList pl_null = null;
		
			System.out.println("L'insertion de 7 dans chacune des partitions de la liste \n\n"+ pl_null + "\n");
			System.out.println("donne \n\n"+ insert(7,pl_null)+"\n");
			System.out.println("L'insertion de 7 dans chacune des partitions de la liste \n"+ p3);
			System.out.println("donne \n"+ insert(7,p3));
		}

L'exécution de java PartitionList avec la méthode main donnée devra donner

L'insertion de 7 dans chacune des partitions de la liste 

null

donne 

null

L'insertion de 7 dans chacune des partitions de la liste 

3 ooo

4 oooo

donne 

7 ooooooo
3 ooo

7 ooooooo
4 oooo

Partitions d'un entier

On souhaite maintenant définir un algorithme pour construire la liste des partitions d'un entier strictement positif n dont les parties sont dans une liste d'entiers parts. On supposera que les éléments de parts sont en ordre strictement décroissant.

La classe IntList, que nous vous avons fournie à la fin du fichier Partition.java, contient une représentation très simple de liste d'entiers d'une manière totalement similaire à ce que nous avons fait en TD. Elle sera utilisée pour la liste d'entiers parts. Vous aurez besoin dans la suite d'utiliser les fonctions (déjà écrites) :

• int getFirst() permettant d'obtenir le premier élément de la liste ;
• IntList getNext() permettant d'obtenir la suite de la liste (sans le premier élément) ;

Le principe de l'algorithme est le suivant :

• si parts est vide (il n'y a plus de parts possibles pour construire la partition), on renvoie la liste vide null ;
• sinon, appelons x le premier élément de parts et queue la suite de parts. L'algorithme renvoie l'union des deux ensembles calculés de la manière suivante :
  • pour le premier ensemble: si n - x > 0 alors on construit récursivement l'ensemble des partitions de l'entier n - x avec des parts toujours dans parts et on ajoute (en tête) x à toutes ces partitions ; sinon si n - x = 0 alors le premier ensemble contient un seul élément: la partition (x). Dans les autres cas, le premier ensemble est l'ensemble vide ;
  • pour le deuxième ensemble: on construit l'ensemble des partitions de n où les parts sont dans l'ensemble queue.

Dans la classe PartitionList écrire une fonction public static PartitionList generation(int n, IntList parts) qui renvoie la liste des partitions de n dont les parties appartiennent à parts.

En déduire, pour la classe PartitionList

• une fonction public static PartitionList partitionOf(int n) qui renvoie la liste des partitions de n.
• une fonction public static PartitionList rendreLaMonnaie(int n), qui donne toutes manière de rendre la monnaie de n euros en supposant que l'on dispose d'un nombre infini de pièces de 10, 5, 2 et 1 euros.

Tester votre programme avec la fonction main suivante (dans la classe PartitionList):

	public static void main(String[] args) {
		int n=Integer.parseInt(args[0]);
		System.out.println("Les partitions de "+ n + " sont ");
		System.out.println(PartitionList.partitionOf(n));
		System.out.println("Rend la monnaie de " + n);
		System.out.println(rendreLaMonnaie(n));
}

Les partitions de 4 sont 

4 oooo

3 ooo
1 o

2 oo
1 o
1 o

2 oo
2 oo

1 o
1 o
1 o
1 o

Rend la monnaie de 4

2 oo
1 o
1 o

2 oo
2 oo

1 o
1 o
1 o
1 o

Partitions en parties impaires distinctes

On rappelle que pour une partition (n₁,n₂,...,n_k) de n, les entiers n_i sont appelés parties de la partition. Une partition de n en parties impaires distinctes est ainsi une partition de n telle que

• pour 1 ≤ i < j ≤ k, on a ni ≠ nj ;
• pour 1≤ i ≤ k, l'entier ni est impair.

Dans la classe Partition, écrire une fonction boolean oddDistinctParts() testant si une partition est en parties impaires distinctes.

Dans la classe PartitionList écrire une fonction public PartitionList sublistOddDistinctParts() qui renvoie les partitions qui sont en parties impaires distinctes. Cette fonction devra être persistante.

Tester votre programme avec la fonction main suivante (dans la classe PartitionList):

	public static void main(String[] args) {
		int n=Integer.parseInt(args[0]);
		PartitionList pl_partitions = PartitionList.partitionOf(n);
		System.out.println("Les partitions de "+ n + " sont ");
		System.out.println(pl_partitions);
		System.out.println("La liste des partitions en parties impaires distinctes est " + pl_partitions.sublistOddDistinctParts());
}

Partitions auto-duales

Si on effectue une symétrie du diagramme de la partition par rapport à la diagonale principale (en rouge dans les exemples ci-dessous), on obtient une autre partition de n. Par exemple,

La partition duale de 
6 oooooo
4 oooo
3 ooo
1 o

est la partition
4 oooo
3 ooo
3 ooo
2 oo
1 o
1 o

La partition duale de 
8 oooooooo
4 oooo
2 oo

est la partition
3 ooo
3 ooo
2 oo
2 oo
1 o
1 o
1 o
1 o

2 oo
2 oo

4 oooo
2 oo
1 o
1 o

3 ooo
3 ooo
2 oo

• Dans la classe Partition, écrire une fonction public Partition dual() calculant la partition duale. Cette fonction devra être persistante.

  Tester votre programme avec la fonction main suivante (dans la classe PartitionList):

  	public static void main(String[] args) {
  		int n=Integer.parseInt(args[0]);
  		PartitionList pl = PartitionList.partitionOf(n);
  		while(pl!=null){
  			System.out.println("La partition duale de \n" + pl.first);
  			System.out.println("est la partition\n" + (pl.first).dual());
  			pl = pl.next;
  		}
  }
  

  en exécutant java PartitionList 4.

• Dans la classe Partition, écrire une fonction public boolean isEqual(Partition p) testant l'égalité de deux partitions.

• Dans la classe PartitionList, écrire une fonction public PartitionList sublistAutoDual() qui renvoie les partitions qui sont auto-duales. Cette fonction devra être persistante.

  Tester votre programme avec la fonction main suivante (dans la classe PartitionList):

  	public static void main(String[] args) {
  		int n=Integer.parseInt(args[0]);
  		PartitionList pl_partitions = PartitionList.partitionOf(n);
  		System.out.println("Les partitions de "+ n + " sont ");
  		System.out.println(pl_partitions);
  		System.out.println("La liste des partitions auto-duales est " + pl_partitions.sublistAutoDual());
  		System.out.println("La liste des partitions en parties impaires distinctes est " + pl_partitions.sublistOddDistinctParts());
  }
  

  en exécutant java PartitionList 4 puis java PartitionList 8.

Que constatez-vous sur le nombre de partitions auto-duales d'un entier et sur le nombre de partitions en parties impaires distinctes ? Pouvez-vous l'expliquer ? Vous pourrez répondre dans un commentaire à la fin du fichier Partition.java.

Déposer le fichier Partition.java