Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

  1. #1
    Membre à l'essai
    Inscrit en
    décembre 2005
    Messages
    49
    Détails du profil
    Informations forums :
    Inscription : décembre 2005
    Messages : 49
    Points : 22
    Points
    22
    Par défaut Algo pour toutes les combinaisons possibles
    Bonjour, voilà je me creuse la tête depuis quelques temps et j'arrive pas à trouver de solution à mon problème.

    Bon je cherche à faire sa en Java :

    int n = un nombre qui peut varier
    public void combinaisons possibles(n){...}

    Le but étant d'affichier dans la méhode toutes les combinaisons possibles des nombres 0,1,2,3,4,...,n.

    Donc par exemple, si n = 3 :
    012
    120
    021
    ...

    Ou si n=5 :
    012345
    123450
    021345
    ...

    Alors peut être que certains vont trouver sa classique comme pb mais là je galère à trouver un algo récursif qui me fait sa (et oui la récursivité s'impose vue que n n'est pas un nombre fixe).

    Pouvez-vous m'aider ?
    Merci

  2. #2
    Membre éclairé
    Profil pro
    Inscrit en
    février 2007
    Messages
    572
    Détails du profil
    Informations personnelles :
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations forums :
    Inscription : février 2007
    Messages : 572
    Points : 675
    Points
    675
    Par défaut
    Ca n'est pas un probleme java, mais d'algorithme.

    Il faut que tu le trouves par toi-meme, sur le papier, avant de l'ecrire en java. De cette facon tu apprendras quelque chose.

    Si par la suite tu as vraiment un probleme java, no souci pour y remedier.

  3. #3
    Membre à l'essai
    Inscrit en
    décembre 2005
    Messages
    49
    Détails du profil
    Informations forums :
    Inscription : décembre 2005
    Messages : 49
    Points : 22
    Points
    22
    Par défaut
    Oui beh justement je demande votre aide pour trouver l'algorithme lol
    Je galère dessus depuis hier après-midi...

  4. #4
    Membre à l'essai
    Inscrit en
    décembre 2005
    Messages
    49
    Détails du profil
    Informations forums :
    Inscription : décembre 2005
    Messages : 49
    Points : 22
    Points
    22
    Par défaut
    Bon bonne nouvelle, après quelques heures de recherche intensive, j'ai réussit à créer une méthode me donnant toutes les possibilités possibles...

    Le seul hic maintenant, c'est qu'il faut qu'il fonctionne pour n=8, n=12, etc...
    mais actuellement pas de problème pour le 8, mais au 12 j'ai l'exception suivante qui se lance :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    Exception in thread "AWT-EventQueue-0" java.lang.OutOfMemoryError: Java heap space
    	at search.Resolve.nbOfPossibilities(Resolve.java:180)
    (...)
    La ligne 180 correspondant à celle que j'ai mise en rouge dans le code ci-dessous.

    Voici les codes : (n = otherGrayPiecies.size())
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
        private ArrayList<int[]> possibilities;
    
        public void nbOfPossibilities(int i, ArrayList<int[]> oldValues){
        	int oldNbOfLines = oldValues.size();
        	possibilities = new ArrayList<int[]>();
        	
        	int[] lineValues;
        	
        	for(int j=0 ; j<(i+1) ; j++){ // Nb blocks
        		for(int k=0 ; k<oldNbOfLines ; k++){ //Lignes par block
        			int indice=0;
        			lineValues = new int[i+1];
    				int numLigne = (j*oldNbOfLines)+k;
        			
        			for(int m=0 ; m<(i+1) ; m++){
        				
        				// Cas où on est dans le premier block
        				if(j==0){
        					if(m==0){
        						lineValues[m]=i;
        					}
        					else{
        						lineValues[m]=oldValues.get(k)[m-1];
        					}
        				}
        				else{
        					if(m==j){
        						lineValues[m]=i;
        					}
        					else{
        						lineValues[m]=oldValues.get(k)[indice];
        						indice++;
        					}
        				}
        			}
        			possibilities.add(numLigne, lineValues);
        		}
        	}
        		
        	if(i+1<otherGrayPiecies.size())
        		nbOfPossibilities(i+1,possibilities);
        	else
        		return;
        }
        
        public ArrayList<int[]> initNbOfPossibilitiesDefaultValues(){
    		ArrayList<int[]> valuesList = new ArrayList<int[]>();
    		
    		int[] values = {0,1};
    		valuesList.add(0,values);
    		
    		int[] values2 = {1,0};
    		valuesList.add(1,values2);
    		
    		return valuesList;
        }
    
        public static void main(String[] args) {
    (...)
            // Valeurs d'initialisation pour recherche un nombre de cas possibles
    	ArrayList<int[]> defaultValues = initNbOfPossibilitiesDefaultValues();
    	nbOfPossibilities(2,defaultValues);
    
            System.out.println("nb combinaisons trouvées : "+possibilities.size());
    (...)
        }
    Le pb est donc que je dépasse à un moment du calcul l'espace mémoire maximum autorisé, mais j'avoue que je ne comprends pas pourquoi, et surtout il faudrait à arriver à régler ce problème qui est ennuyant...

    Cette fois-ci c'est bel et bien un problème de Java

    Est-ce que quelqu'un peut m'aider ?

    Merci à tous

  5. #5
    Membre éclairé
    Profil pro
    Inscrit en
    février 2007
    Messages
    572
    Détails du profil
    Informations personnelles :
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations forums :
    Inscription : février 2007
    Messages : 572
    Points : 675
    Points
    675
    Par défaut
    Cette fois-ci c'est bel et bien un problème de Java
    Ben en fait, pas vraiment.

    Certes, tu as une exception levée, mais c'est en grande partie parce que l'algorithme n'est pas adequat.

    Ton probleme, c'est trouver toutes les permutations. Tu trouveras la définition d'une permutation, en sens mathématique, ici
    Tu y verras notamment que le nombre de permutation pour un ensemble a n elements, c'est n!
    Ce qui fait pour n=12, 4790016000 possibilités. Si tu mets ca dans un tableau d'int, en java, ca donne 4790016000*4 bytes, soit environ 1,9Go.

    Ce que je te conseille, c'est de chercher sous google avec le mot cle permutation. Tu devrais trouver ton bonheur.

  6. #6
    Membre à l'essai
    Inscrit en
    décembre 2005
    Messages
    49
    Détails du profil
    Informations forums :
    Inscription : décembre 2005
    Messages : 49
    Points : 22
    Points
    22
    Par défaut
    Ok je vais chercher dans ce sens.

    Merci de m'avoir expliqué le pourquoi de l'erreur.

  7. #7
    Membre confirmé Avatar de billynirvana
    Homme Profil pro
    Architecte technique
    Inscrit en
    décembre 2004
    Messages
    472
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Architecte technique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : décembre 2004
    Messages : 472
    Points : 549
    Points
    549
    Par défaut
    Au lieu de stocker en mémoire, stocke dans un fichier.

Discussions similaires

  1. Réponses: 3
    Dernier message: 12/04/2015, 14h00
  2. Réponses: 1
    Dernier message: 09/01/2014, 22h27
  3. Réponses: 5
    Dernier message: 18/06/2007, 21h52
  4. Réponses: 16
    Dernier message: 20/10/2006, 17h31
  5. toutes les combinaisons possibles
    Par marocleverness dans le forum Algorithmes et structures de données
    Réponses: 6
    Dernier message: 29/05/2006, 01h11

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo