COMBINATOIRE
verdy_p
Messages postés
202
Date d'inscription
vendredi 27 janvier 2006
Statut
Membre
Dernière intervention
29 janvier 2019
-
7 avril 2008 à 06:49
vctrs Messages postés 3 Date d'inscription mardi 1 avril 2008 Statut Membre Dernière intervention 14 mai 2008 - 14 mai 2008 à 12:36
vctrs Messages postés 3 Date d'inscription mardi 1 avril 2008 Statut Membre Dernière intervention 14 mai 2008 - 14 mai 2008 à 12:36
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/46253-combinatoire
https://codes-sources.commentcamarche.net/source/46253-combinatoire
14 mai 2008 à 12:36
http://www.google.com/...
8 avril 2008 à 10:11
Maintenant, poiurquoi ton code ci-dessus limite N à 31 et non 32? N'y-a-t-il pas 32 bits dans un "int" Java? (OK le dernier bit de poids fort a une valeur négative si on essaye de l'afficher, mais (1<<31) est parfaitement valide, c'est le 32e bit de poids fort, le seul qui soit négatif (ont doit donc faire attention si on fait ensuite des décalages vers la droite avec >> car il se copie dans les bits à gauche, contrairement à >>> qui insère des bits nuls), de même que (1<<0) qui est le premier bit de poids faible.
Conclusion: remplace ">>" par ">>>" dans ton code (afin de traiter les entiers comme s'ils étaient non signés), et tu pourra utiliser le 32e bit (donc monter N à 32). Maintenant, je reste persuadé que pour des valeurs de N petites (N<10 dans ton cas), la classe est superflue car on peut énumérer les combinaisons valides (à P éléments) facilement dans avoir à les stocker toutes.
Exemple:
private int[] decodeCombination(final int encodedCombination) {
final int[] result = new int[iP];
int index = 0;
for (int i = 0; i < iN; i++)
if ((encodedCombination & (1 << i)) != 0)
result[index++] = i;
assert index == iP; // devrait être vrai, test effectué au debogage
return result;
}
Avec un BitSet, cela remplace les "encodedCombination" pour des valeurs de N plus grandes que 32 (note: le BitSet utilise en interne des "long" sur 64 bits dans son tableau de stockage et non des int, pour des raisons de performance. Il gère en interne l'allocation de son tableau de stockage de bits selon une méthode de crossiance exponentielle (fonction de la valeur du bit le plus élevé ajouté au Set, mais son tableau interne ne se réduit pas tout seul en taille, ce peut être une classe couteuse si un seul bit est inclu dans le Set à une position élevée. Il supporte les opérations classiques sur les Set (comme union, intersection, différence...) mais pas la négation (ensemble complémentaire) car il est virtuellement de taille infinie. Pour faire la négation il faut d'abord construire un BitSet contenant tous les bits positionnés à 1 correspondant à la taille de ton ensemble "univers", puis faire la différence. Tant que l'univers reste raisonnable en taille, ça va, mais souvent il vaut mieux en faire une classe dérivée permettant de stocker l'état "ensemble complementaire" dans un seul booléen, et alors réécrire les opérations sur les ensembles pour qu'il en tienne compte (il faut aussi réécrire les itérateurs comme nextSetBit() et nextClearBit()). Ca a été proposé à Sun depuis longtemps, mais la gestion des ensembles complémentaires n'est toujours pas faite dans BitSet.
Si j'ai un peu de temps j'extrairai le code que j'utilise dans une de mes applis pour avoir un BitSet complémentable capable de travailler sur des ensembles très grands de façon efficace.
Dernière note: BitSet ne sait pas non plus travailler efficacement sur des grands ensembles clairsemés ("sparse") où seuls quelques bits sont utilisés parmi un grand nombre (il va les stocker tous jusqu'au plus grand, ce qui prends une place mémoire considérable si on manipule beaucoup d'instances). Le BitSet standard du JRE ne dispose pas de plusieurs stratégies de stockage et représentation interne pour représenter l'enesble clairsemé avec un index rapide, des sections représentées par des bitpatterns 64-biyts, et des sections où les valeurs isolées d'int sur 32 bits sont directement énumérées dans un tableau. Il n'y a pas de méthode générale facile pour répondre à ce problème, de façon satisfaisante pour tous les problèmes. On doit donc adapter son problème en utilisant dans une classe adaptée un ou plusieurs BitSets et/ou des tableaux d'entiers. Pourtant mon utilisation la plus fréquente des BitSet porte sur des tailles voisines de 1 à 16 Kbits, parfois jusqu'à 1 mégabits.
Les BitSet ne sont pas fournis non plus pour gérer des entiers de grande taille: ils ne supportent pas les opération artithmétiques de base. Pour cela il y a plutot BigDecimal ou BigInteger (mais BigInteger ne gère pas non plus les opérations sur les set): on ne peut pas avoir le beurre, et l'argent de la crémière... Ce que fournit les classes du JRE ce sont des classes traitant les cas les plus généraux et réutilisables, avec lesquels on construit les autres cas particuliers.
7 avril 2008 à 15:56
En fait j'utilise cette classe pour un cas particulier ou N est très restreint (<10) et ou je suis amené à réutiliser de nombreuses fois les même combinaisons, donc j'ai préféré stocker les combinaisons (pour N<10, ça ne fait pas lourd en mémoire) et gagner un poil de temps processeur sur les calculs suivants...
Merci pour les conseils, en particulier sur la classe BitSet que je ne connaissais pas.
7 avril 2008 à 06:49
Pour des valeurs plus grandes de N, il faudrait stocker dans la table initialisée par le constructeur des "long" (N jusqu'à 64), sinon des objets BitSet. Le seule ennui est que le constructeur tente de remplir sa table d'index interne avec toutes les combinaisons valides, et il le fait par une méthode récursive.
Il semble donc bien plus efficace d'utiliser de simples Set d'éléments (dont toutes les valeurs possibles sont énumérées dans un tableau indexé par un entier, ou bien sont issues d'une classe enum déclarée ce qui est équivalent quand on sait comment fonctionne les enum en Java5+), et d'utiliser la methode size() de l'interface Set pour connaitre le nombre d'éléments dans le set et savoir si c'est une combinaison valide. Les instances de Set sont elles-mêmes indexables si on veut gérer par exemple des listes de combinaisons valides (car Set est un Object implémentant les méthodes de hachage). Le BitSet est un Set plus économique encore car on connait les valeurs possibles énumérées (elles sont donc ordonnées et naturellement indexées par un entier correspondant à un bit du BitSet), et il n'est pas nécessaire de stocker les valeurs ou références des éléments de la combinaison, juste leur présence ou absence dans la combinaison.
Vouloir un objet énumérant toutes les combinaisons de P éléments parmi N possibles ne nécessite à priori aucun stockage: on peut tout à fait écrire un itérateur qui les parcours tous, sans même avoir à jamais les stocker: l'itérateur n'a besoin que d'un seul Bitset de taille N, d'un entier indiquant la position du P-ième bit le plus élevé présent dans le bitset et la position du 1er bit déjà parcouru. Pour le reste, il n'a qu'à faire glisser les bits les plus forts vers le bit le plus élevé (sans le superposer) et donc il suffit uniquement dans l'itérateur de stocker les positions courantes des P éléments (l'itérateur commencera par retourner la combinaison {0,1,2,...,P-2,P-1} puis il incrémentera le dernier jusqu'à ce qu'il atteigne la valeur maximale N-1; quand il ne peut plus être incrémenté, on le retire du BitSet pour incrémenter le dernier élement restant (tant qu'il laisse suffisamment de place pour les bits manquants, sinon on le retire aussi et on boucle; s'il ne reste plus de bit dans le BitSet qui soit déplaçable sans dépasser la capacité, l'itérateur a terminé).
L'idée est, ni plus ni moins, que d'encapsuler dans le BitSet contenu dans l'itérateur l'état de P boucles imbriquées (mais à aucun moment on ne parcourera la totalité des combinaisons valides, et le nombre d'opérations pour chaque étape next() de l'itérateur reste limité en O(P)...). Si P est faible mais N grand, le bitset utilisé pour stocker l'état sera de taille N ce qui peut être moins économique qu'un simple tableau de P entiers (à valeur dans 0..N-1).
La représentation la plus efficace est facile à déterminer: un tableau de P entiers prendront 32*P bits dans le tableau; un BitSet piur N élements prendra (N+63)/64*64 bits pour le Bitset; dans les deux cas on aura aussi à stocker dans l'itérateur une référence d'objet (soit la référence au BitSet, soit la référence au tableau d'entiers), ainsi que les valeurs de P et N. Le choix de représentation est donc facile à déterminer dans le constructeur, et ensuite on peut l'identifier facilement en utilisant l'opérateur "instanceof" de Java.
Je doûte donc très fortement de l'utilité de cette classe pour des cas pratiques (même quand les valeurs de N et P ne sont pas constantes dans un programme). Dernière note: si N est inféieur à P-N on a intéret à stocker dans l'itérateur les valeurs énumérées qui font parties de la combinaison. Dans le cas contraire, il vaut mieux stocker au contraire les P-N valeurs énumérées qui ne font PAS partie de la combinaison (surtout si N est grand!)