Combinatoire

Soyez le premier à donner votre avis sur cette source.

Snippet vu 9 408 fois - Téléchargée 18 fois

Contenu du snippet

calcule les combinaisons de P éléments dans N éléments et les conserve sous forme d'index pour qu'elles soient réutilisables...

voir les commentaires dans le code

Source / Exemple :


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
/**

  • Stores all the combinations of P elements in N elements.
  • This class considers that you have a list of N indexed objects.
  • It stores all combinations of the indexes of P elements in these N elements...
  • The main point here is that you use indexes...
  • Hence you can calculate the combinations once for all...
  • Example: you calculate the combinations of 3 elements in 5, then you can apply the result to any list of 5 elements,
  • be it a list of strings, of cards, numbers, with the {@link #getCombination(Object[], int, boolean)} method...
  • @author vctrs
  • /
public class Combinations { /**
  • Size of the universe (N)
  • /
private int iN; /**
  • Size of the combinations (P)
  • /
private int iP; /**
  • Stores all the combinations.
  • NB: a combination is stored as an integer, with each bit corresponding to an index being present or not...
  • example: int = 25 -> bit = 11001 -> means that the combination includes the elements at index 0,3,4
  • @see #encodeCombination(int[])
  • @see #decodeCombination(int)
  • Hence the N<=31 limitation since an int is coded on 31bits (+1 for sign)
  • But it divides the memory usage by P compared to a 'basic' way of handling combinations...
  • /
private Collection<Integer> list = new ArrayList<Integer>(); /**
  • @return list of all the indexes combinations of P elements in N elements
  • @see #list
  • /
public Collection<Integer> getList() {return list;} /**
  • Calculates the combinations of P in N
  • @param P Size of the combinations (P)
  • @param N Size of the universe (N)
  • @throws Exception if N>31 or P>N
  • /
public Combinations(int P, int N) throws Exception{ System.out.println("Combinations of P="+P+" elements in N="+N+" elements"); if(N>31)throw new Exception("Too many elements for N (Max=31)"); if(P>N)throw new Exception("No combination if P>N"); iN = N; iP = P; findCombinations(0, new int[iP]);//finds the list of combinations... } /**
  • Main algorithm to find the combinations
  • @param index currently filling this index of the current combination
  • @param currentCombination temporary object used to store the combination
  • NB: basically it uses the same method you instinctively use to find combinations manually...
  • /
private void findCombinations(int index, int[] currentCombination) { if (index>=iP) {//combination has the good size list.add(encodeCombination(currentCombination)); }else{ int start=0; if (index>0) start=currentCombination[index-1]+1;//start from the latest found index... for(int i=start;i<iN;i++) { currentCombination[index]=i; findCombinations(index+1, currentCombination); } } } /**
  • @param decodedCombination a list of indexes
  • @return an int that express the given list as a combination
  • /
private int encodeCombination(int[] decodedCombination){ int encodedCombination = 0; for(int index:decodedCombination)encodedCombination |= (1 << index); return encodedCombination; } /**
  • @param encodedCombination a combination expressed as an int
  • @return the list of indexes linked to the given combination
  • /
private int[] decodeCombination(int encodedCombination){ int[] result = new int[iP]; int index = 0; for(int i=0;i<iN;i++) if((0x1 & (encodedCombination >> i))==1){ result[index] = i; index++; } return result; } /**
  • @param universe a collection of objects (that was used to calculate the combination)
  • @param selectedCombination a combination that should be applied to the given universe
  • @param complement return the combination (=false) or everything except the combination (=true)?
  • @return the combination or everything except the combination
  • NB: the given universe and the selected combination must be linked
  • (typically you calculate the list of combinations by taking the size of the universe)
  • See usage in the main method
  • NB: universe is an array, but it could become a collection, given that this collection ensures the order of its elements...
  • But basically it is more simple to keep it as an array...
  • /
public <U> Collection<U> getCombination(U[] universe, int selectedCombination, boolean complement){ Collection<U> result = new ArrayList<U>(iN); int usedCombination = complement?~selectedCombination:selectedCombination; for(int i=0;i<iN;i++)if((0x1 & (usedCombination >> i))==1)result.add(universe[i]); return result; } /**
  • @param encodedCombination
  • @return the given combination as a list of indexes
  • /
private String displayCombination(int encodedCombination){ return Arrays.toString(decodeCombination(encodedCombination))+"\n"; } /**
  • @return all the indexes combinations linked to this object
  • /
public String toString(){ String result=""; for(Integer i:list)result+=displayCombination(i); return result; } /**
  • Testing results:
example#1 Combinations of P=3 elements in N=5 elements abc abd abe acd ace ade bcd bce bde cde example#2 Combinations of P=2 elements in N=5 elements [0, 1] [0, 2] [0, 3] [0, 4] [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4] example#3 Combinations of P=1 elements in N=1 elements [0] example#4 Combinations of P=2 elements in N=1 elements No combination if P>N example#5 Combinations of P=1 elements in N=32 elements Too many elements for N (Max=31)
  • /
public static void main(String[] args) { try { System.out.println("example#1"); String[] universe = {"a","b","c","d","e"}; int N = universe.length; int P = 3;//look for all the combinations of 3 elements in the given universe... Combinations c = new Combinations(P,N); for(int combination:c.getList()){ String sCombination = ""; Collection<String> cCombination = c.getCombination(universe, combination, false);//returns the list of elements of the original list that are in the given combination... for(String s:cCombination)sCombination+=s;//display the combination we just found... System.out.println(sCombination); } System.out.println("example#2"); System.out.println(new Combinations(2,5).toString()); System.out.println("example#3"); System.out.println(new Combinations(1,1).toString()); } catch (Exception e) { System.out.println(e.getMessage()); } try { System.out.println("example#4"); System.out.println(new Combinations(2,1).toString()); } catch (Exception e) { System.out.println(e.getMessage()); } try { System.out.println("example#5"); System.out.println(new Combinations(1,32).toString()); } catch (Exception e) { System.out.println(e.getMessage()); } } }//end of class /*
  • This file was inspired by the source code of Steven J. Metsker, found at the following address
  • http://www.google.com/...
  • Copyright of the original file:
  • Copyright (c) 2000 Steven J. Metsker. All Rights Reserved.
  • Steve Metsker makes no representations or warranties about
  • the fitness of this software for any particular purpose,
  • including the implied warranty of merchantability.
  • /
import java.util.ArrayList; import java.util.Arrays; import java.util.Collection; import java.util.Iterator; /**
  • This class provides an iteration of all combinations of P in N objects.
  • /
public class CombinationsTucker<O> implements Iterable<Collection<O>> { /**
  • Stores the universe in a collection with access by index
  • /
protected ArrayList<O> universeWithArray; /**
  • size of the universe
  • /
protected int n; /**
  • size of the combinations
  • /
protected int p; /**
  • Array that keeps track of the next combination to return.
  • For example, an index on 5 things taken 3 at a time might contain {0 3 4}.
  • This index will be followed by {1 2 3}.
  • Initially, the index is {0 ... m - 1}.
  • /
protected int[] combinationIndex; /**
  • Create a Combination to iterate through all combinations of the supplied collection, selecting P at a time.
*
  • @param universe the group to choose from
  • @param p the number to select in each choice
  • @exception Exception if m is greater than the length of universe, or less than 0.
  • /
public CombinationsTucker(Collection<O> universe, int p)throws Exception{ this.n = universe.size(); this.p = p; System.out.println("Combinations of P="+p+" elements in N="+n+" elements"); if(p>n)throw new Exception("No combinations if P>N"); if(p<0)throw new Exception("No combinations if P<0"); this.universeWithArray = new ArrayList<O>(this.n); this.universeWithArray.addAll(universe); //Find first combination combinationIndex = new int[p]; for(int i=0; i<p; i++) combinationIndex[i]=i; } /**
  • Create a Combination to iterate through all combinations of the supplied collection, selecting P at a time.
*
  • @param universe the group to choose from
  • @param p the number to select in each choice
  • @exception Exception if m is greater than the length of universe, or less than 0.
  • /
public CombinationsTucker(O[] universe, int p)throws Exception{ this(Arrays.asList(universe),p); } /**
  • Return an iterator for the combinations.
  • */
public Iterator<Collection<O>> iterator() { return new CombinationIterator(); } /**
  • internal class that calculates the iteration of combinations...
  • a combination is a collection of P objects(<O>)
  • /
protected class CombinationIterator implements Iterator<Collection<O>>{ /**
  • stores next element existence
  • /
private boolean next = true; /**
  • @return true, unless we have already returned the last combination.
  • /
public boolean hasNext() { return next; } /**
  • Calculates the indexes of the univers'elements that will be in the next combination...
  • Move the index forward a notch.
  • The algorithm finds the rightmost index element that can be incremented, increments it,
  • and then changes the elements to the right to each be 1 plus the element on their left.
  • For example, if an index of 5 things taken 3 at a time is at {0 3 4},
  • only the 0 can be incremented without running out of room.
  • The next index is {1, 1+1, 1+2) or {1, 2, 3}.
  • This will be followed by {1, 2, 4}, {1, 3, 4}, and {2, 3, 4}.
  • The algorithm is from "Applied Combinatorics", by Alan Tucker.
  • /
private void calculateNextCombination() { int i = rightmostCombinationIndexBelowMax(); if (i >= 0) { combinationIndex[i] = combinationIndex[i] + 1; for (int j=i+1; j<p; j++) combinationIndex[j] = combinationIndex[j-1] + 1; }else{ next = false; } } /**
  • keep implementation correct
  • /
public void remove() { throw new UnsupportedOperationException(); } /**
  • @return the next combination
  • /
public Collection<O> next() { if (!next) return null; ArrayList<O> out = new ArrayList<O>(p); for(int i=0; i<p; i++) out.add(i, universeWithArray.get(combinationIndex[i])); calculateNextCombination(); return out; } /**
  • @return the index which can be bumped up.
  • /
private int rightmostCombinationIndexBelowMax() { int d = n-p; for(int i=p-1; i>=0; i--) if(combinationIndex[i]<d+i) return i; return -1; } } ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /**
  • Result of main:
example#1 Combinations of P=2 elements in N=4 elements ab ac ad bc bd cd end of example#1 example#2 Combinations of P=3 elements in N=5 elements Alfred Ben Carl Alfred Ben Drew Alfred Ben Edwin Alfred Carl Drew Alfred Carl Edwin Alfred Drew Edwin Ben Carl Drew Ben Carl Edwin Ben Drew Edwin Carl Drew Edwin end of example#2
  • /
public static void main(String[] args) { try { System.out.println("example#1"); Collection<String> universe1 = new ArrayList<String>(); universe1.add("a"); universe1.add("b"); universe1.add("c"); universe1.add("d"); int P1 = 2; CombinationsTucker<String> c1 = new CombinationsTucker<String>(universe1, P1); for(Collection<String> combination:c1){ for(String o:combination)System.out.print(o); System.out.println(); } System.out.println("end of example#1"); System.out.println("example#2"); String[] universe2 = {"Alfred", "Ben", "Carl", "Drew", "Edwin"}; int P2 = 3; CombinationsTucker<String> c2 = new CombinationsTucker<String>(universe2, P2); for(Collection<String> combination:c2){ for(String o:combination)System.out.print(o+"\t"); System.out.println(); } System.out.println("end of example#2"); } catch (Exception e) { System.out.println(e.getMessage()); } } ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// }//end of class

A voir également

Ajouter un commentaire Commentaires
Messages postés
3
Date d'inscription
mardi 1 avril 2008
Statut
Membre
Dernière intervention
14 mai 2008

Messages postés
202
Date d'inscription
vendredi 27 janvier 2006
Statut
Membre
Dernière intervention
29 janvier 2019

BitSet est très utile dès qu'on doit gérer des enembles de valeurs énumérées connues. Ce qui est intéressant est qu'on n'est pas limité en nombre d'éléments.
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.
Messages postés
3
Date d'inscription
mardi 1 avril 2008
Statut
Membre
Dernière intervention
14 mai 2008

Oui, cette classe n'est pas adaptée pour un N important...
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.
Messages postés
202
Date d'inscription
vendredi 27 janvier 2006
Statut
Membre
Dernière intervention
29 janvier 2019

Grosse limitation: N ne peut dépasser 31 (d'ailleurs ce devrait être 32, taille de ce que peut stocker un "int", en acceptant le fait que le décalage binaire peut produire des valeurs négatives si le bit 31 est positionné).

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!)

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.