Permutation utilisant la récursivité!!

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) ;
}

En fait tu peux procéder en trois boucles :

Code:

---

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.

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

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

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

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:

---

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

---