Calculer le nombre de relations d'équivalence pour un ensemble ayant 10 éléments

Question

Étant donné un ensemble A avec 10 éléments, comment trouver le nombre de relations d'équivalence en utilisant des instructions if imbriquées? Tout d'abord, nous pouvons considérer l'ensemble 12,3, ..., 10 pour notre but. Cela fera la même chose.

Nous pouvons créer un tableau de taille 10 × 10 de sorte que nous obtenons toutes les combinaisons de 2 éléments de 1,2,3, ..., 10. Notez que la diagonale de la matrice carrée contient (a, a) pour tout a {1,2,3 ..., 10}. Donc, 2 à la puissance: la moitié supérieure de la diagonale + la diagonale donne un compte des relations symétriques. Comment utiliser sinon les conditions de la programmation pour compter le nombre total de relations d'équivalence? J'essaie d'utiliser l'une des moitiés supérieure ou inférieure en fait. Cela réduirait la complexité temporelle du programme, mais comme je ne l'ai pas terminé, je ne peux pas commenter plus.

L'algorithme du pire cas est peut-être de créer un tableau 2D et de vérifier en utilisant if-else si les deux symétriques et transitives sont satisfaites ou non. Mais cela utiliserait O (n²). J'essaie d'obtenir un meilleur algorithme.

Answer 1

Il existe une bijection entre les relations d'équivalence sur un ensemble et les partitions de l'ensemble. Compter le nombre de relations d'équivalence revient à compter le nombre de partitions. Le nombre de partitions d'un ensemble avec n éléments est le Bell Number B_n.

Il existe une formule de relation de récurrence et aucun besoin de if/then/else imbriqué. Veuillez mettre à jour votre question afin de préciser ce que vous essayez de réaliser et quelles sont vos contraintes sur la solution.