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
    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é
    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
    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
    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é
    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
    Ok je vais chercher dans ce sens.

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

  7. #7
    Membre confirmé
    Au lieu de stocker en mémoire, stocke dans un fichier.

###raw>template_hook.ano_emploi###