Discussion :

[saturn1]

Bonjour,
je sais qu'il existe beaucoup de topic existant sur ce sujet.
Mais c'est apres beaucoup de recherches que je fais un n(ieme) posts.

Le but est avec une combinaison de chiffre, generer toutes les nombres possibles.

Par exemple pour :
0, 1, 2 => 6 possibilites
0, 1, 2, 3 => 24 possibilites.
Le but n'etant pas de les compter mais de les afficher.

J'ai fais un script mais le probleme c'est qu'il est beaucoup trop long pour les combinaisons a 10 chiffres.

Voici mon script :

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
 
 
 
function perm($nbrs, $res)
{
  for ($i = 0; $i != count($nbrs); $i++)
    {
      $prev = $res[count($res) - 1];
      $tmp = $prev[$i];
      $prev[$i] = $prev[($i + 1) % count($nbrs)];
      $prev[($i + 1) % count($nbrs)] = $tmp;
      if (!in_array($prev, $res))
        {
          $res[] = $prev;
          echo $prev . "\n";
          perm($nbrs, &$res);
        }
    }
  return $res;
}
 
$nbrs = array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
$res = array("0123456789");
echo $res[0] . "\n";
$res = perm($nbrs, &$res);

Comment optimiser ce code ?

Merci bien!

[Fredchkek]

Bonjour,

Beaucoup trop long : c'est à dire ?

Il y a près de 4 millions de solutions (si j'ai bien compris le problème), c'est normal que ce soit long non ?

[saturn1]

j'ai abandonne au bout de 1 mn...

Je pense qu'il y a moyen d'optimiser ca car la je dois faire un in_array voir si il n'est pas deja dans le tableau... ca doit prendre du temps :/

Merci

[pseudocode]

itération des 10!=3628800 permutations en 70 millisecondes sur mon PC

itérateur de permutations

(bon c'est du java, alors c'est un peu lent )

[saturn1]

euh 70 milliseconde ca me semble ... impossible pour le nombre de resultat trouves ^^

Voila mon temps avec un nouvel algo:

total res = 3628800
real 1m24.465s
user 0m21.233s
sys 0m6.308s

PS : j'ai rien compris a ton algo en iteratif !

[pseudocode]

euh 70 milliseconde ca me semble ... impossible pour le nombre de resultat trouves ^^

Code Java :

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

1
2
3
4
5
6
7
8
9
10
11
long t0 = System.currentTimeMillis(), i=0;
 
Character[] sample = new Character[] {'0','1','2','3','4','5','6','7','8','9'};
Permutation<Character> permut = new Permutation<Character>(sample);
 
while(permut.next()) i++;
 
long t1 = System.currentTimeMillis();
 
System.out.println("Nombre de permutations : "+i);
System.out.println("temps écoulé : "+(t1-t0)+"ms");

Résultat:

Code :

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

1
2
3
 
Nombre de permutations : 3628800
temps écoulé : 70ms

Dans ce code, l'algo ne fait que énumérer en mémoire les permutations. S'il faut les afficher ou faire un traitement dessus, ca sera évidement plus long.

PS : j'ai rien compris a ton algo en iteratif !

C'est un odomètre. C'est pas facile a comprendre, mais ca marche.