Discussion :

[dongnold]

S'il vous plaît!
Comment écrire un program en Java qui génère toutes les permuations de 1..n. ??

J'ai fait un program comme ça mais il y a des doublons (111, 112,...)

import java.util.Arrays;

public class test {

public test() {
}


static int[] a = new int[4] ;

public static void rechercher(int k) {
boolean[] b = new boolean[4] ;

Arrays.fill(b, true);

for (int i = 1; i <= 3; i+=1)
if (b[i])
{
a[k] = i ;
b[i] = false ;
if ( k ==3)
System.out.println(a[1]+" " + a[2] +" " + a[3]) ;
else rechercher(k +1) ;


b[i] = true ;
}


}

public static void main(String args[]){
rechercher( 1) ;
}

[PRomu@ld]

En fait tu peux procéder en trois boucles :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
Pour i allant de 1 à n
     Pour j allant de 1 à n
          Pour k allant de 1 à n
               si i != j != k alors
                    afficher i, j, k;
               fin si
          fin pour
     fin pour
fin pour

En fait les doublons partent avec la condition i différent de j différent de k.

[dongnold]

Dans mon progamme, j'ai pris n = 3 pour tester mais quand n est grand ça sera dur de faire avec les boucles.

[PRomu@ld]

Ok, d'accord, et bien dans ce cas, il te faut une approche récursive, dans ce cas, regarde ceci :

http://www.developpez.net/forums/viewtopic.php?t=419030

[dongnold]

Merci!

Le morceau de code m'a éclairé prk j'ai faux. Le programme correct doit être comme ceci :


import java.util.Arrays;

public class test {

public test() {
}


static int[] a = new int[4] ;
static boolean[] b = new boolean[4] ;


public static void rechercher(int k) {

for (int i = 1; i <= 3; i+=1)
if (b[i])
{
a[k] = i ;
b[i] = false ;
if ( k ==3)
System.out.println(a[1]+" " + a[2] +" " + a[3]) ;
else rechercher(k +1) ;


b[i] = true ;
}


}

public static void main(String args[]){
Arrays.fill(b, true);
rechercher( 1) ;
}

Je pense que c'est plus léger par rapport à l'autre code au fait qu'il ne garde en mémoire qu'un entier à chaque profondeur (l'autre code garde 2 chaînes).

[Trap D]

Attention, le programme donné dans le lien donne tous les anagrammes, ce n'est pas ce que semble vouloir dongnold

Un algo itératif pour faire ce qui est recherché, tous les nombres possibles de 111111111 (n fois) à nnnnnnnnnn (nfois);

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
 
entier max : nombre d'éléments à permuter
entier tab[max+1] : tableau des nombres représentant les permutations, numerotation à partir de 1, +1 pour avoir des tests simples de fin d'incrementation
entier i : un compteur
 
début
  remarque : intialisation du tableau 
  pour i de 1 à max par pas de 1
    tab[i] <- 1
  fin pour
 
  remarque : début de l'algo prorpement dit
  faire
    afficher la permutation tab
    remarque : on incrémente la première position de la table, comme on utilise une boucle, 
    remarque : et qu'on augmente l'indice dans la boucle on part de 0
    i <- 0
    faire
      i <- i + 1
      tab[i] <- tab[i] + 1
      remarque : si la position i contient le plus grand nombre on revient au départ, et on continue l'incrémentation
      si tab[i] = max alors
          tab[i] <- 1
      fin si
    tant que tab[i] = 1 
    remarque on n'a pas besoin de tester i avant à cause de la taille du tableau max +1, l'algo s'arrête si on a incrémenté la case supplémentaire, indiquant qu'on a eu toutes les permutations avant
  tant que i <= max 
fin