Générer les permutations

[lapras]

Bonjour,
j'ai un algorithme récursif pour générer les permutations de {1,2,...,n} en Maple :
genere := proc(k, n, a)
> local r,q;
> if n > 0 then
> r := k mod n ; q := (k - r)/n ; genere(q, n - 1, a) ;
> a[n] := a[r + 1] ; a[r + 1] := n ;
> fi ;
> end ;
genere(k,n,a) renvoir dans le tableau a la kieme permutation (selon un ordre quelconque).


J'aimerais bien savoir, pour des raisons de pratique, si vous en connaissiez un très rapide pour générer toutes les permutations (ou mieux juste celle qui commencent par '1').
Lapras

[fatal_error]

salut,

peux-tu donner un exemple de ton algo? (entrée, sortie)
Par ailleurs je comprends pas cque t'entends par permutation, pour moi une permut(n,k) c'est l'arrangement(n,k) = n!/(n-k)!, cqui est surement pas le cas si tu parles de tableau

[lapras]

Permutation(n,k) : k ieme permutation parmi les n! permutations de {1,..,n}, l'ordre étant quelconque (il est défini par récurrence).
Exemple :
>genere(1,8,a); eval(a);
Renvoie [7, 8, 2, 3, 4, 5, 6, 1, 8, 9].

[fatal_error]

re,

si vous en connaissiez un très rapide pour générer toutes les permutations (ou mieux juste celle qui commencent par '1').

Si je me plante pas tu veux jor generer
(1,2,3,4,5)
(1,2,3,5,4)
...
(1,5,2,3,4)
Toutes les poss ou le 1 est devant.

Si c'est le cas, voici un script php

Code: Tout sélectionner

/**
 * @param e un nombre
 * @param listeUtilises tableau de nombres
 * @return vrai si e est present dans listeUtilises
 *          faux si e n'est pas present
 */
function estUtilise($e,$listeUtilises){
   return in_array($e,$listeUtilises);
}

/**
 * Affiche la liste des permutations qui commencent par la valeur "e".e prend sa valeur
 * dans listeNombres
 * @param n nombre delements a permuter. n vaut la taille du tableau de listeNombres...
 * @param listeNombres tableau de nombres (1,4,6,8,10)
 * @param listeUtilises tableau contient les valeurs des nombres deja utilises dans la permutation courante
 * @param indiceCourant indice du degre de recursivite
 * @param e element a ajouter dans la permutation (on initialise la permutation avec 1 par defaut)
 * @param permutCourante un tableau qui contient la permutation en cours
 */
function recurreMoi($n,&$listeNombres,$e,$listeUtilises = array(),$indiceCourant=0,&$permutCourante=array()){
   /*
    * Algorithme :
    * Initialisation : On remplit notre permutation par le premier nombre : e
    * Ensuite, on va remplir la case numero 1 de la permutation (la case numero 0 contenant e)
    *  Pour ca, on pioche tous les nombres disponibles, et on teste s'ils n'ont pas déjà été utilisés
    *  Si on peut utiliser un nombre, on se rappele pour remplir la case numero 2, et on marque le nombre
    *   qu'on vient d'utiliser (pour ne plus l'utiliser par la suite)
    *  Lorsque la case numero n-1 (la permutation est pleine) est atteinte, on affiche le résultat
    *
    */
   //on le rajoute l'element ou i faut dans notre permutation (dans la bonne "case")
   $permutCourante[$indiceCourant] = $e;
   //on le marque en tant qu'utilisé
   array_push($listeUtilises,$e);
   //Si on a fini, cad on est en derniere case du tableau de permutation
   if($indiceCourant == $n -1){
      //on affiche notre permutation
      show($permutCourante);
   }else{
      //pour tous les elements de listeNombres
      for($i = 0; $i< $n; $i++){
         $e = $listeNombres[$i];
         //si on s'est pas encore servi du nombre
         if(!estUtilise($e,$listeUtilises)){
            //on va remplir la case suivante de notre permutation
            recurreMoi($n,$listeNombres,$e,$listeUtilises,$indiceCourant+1,$permutCourante);
         }
      }
   }
}



Bon, on peut remarquer qu'on a une liste de nombres au lieu de numéroter de 1 a n.
Qui peut le plus peut le moins...
On remarque aussi qu'on peut tout faire commencer par un autre nombre que 1, jor 2.

J'espère que c'était ca que tu cherchais.
Si tu cherches a donner précisément une permutation (ou tu les as toutes ordonnées), alors chui a coté :marteau:

[lapras]

C'est le résultat que j'ai déja, malheureusement l'algorithme est trop lent.
J'aimerais un algo qui me génere toutes les permutation de {1,..,13} en 30 secondes...

[fatal_error]

t'es obligé maple?

Un langage compilé serait bien plus rapide. L'optimisation serait plus de ce coté que du coté code...

M'enfin, coté code on peut surement faire mieux, mais je pense que l'idée est bonne. Le seul truc ou on pourrait sensiblement jouer c'est sur le teste du nombre déjà utilisé.

[lapras]

Du moment que c'est rapide je veux bien prendre n'importe quel langage (le C je connais la syntaxe un peu). Ca va vraimet changer quelquechose ?

[phryte]

Bonjour.

n'importe quel langage

Matlab et Scilab font cela avec : perms

[fatal_error]

re,

j'ai testé perms sous octave avec tableau de 13, depassement memoire.

J'ai testé en c++, m'enfin, ca fait plus C que C++, je tourne a 131secondes de temps pour toutes les trouver (pas afficher) (si on les affiche forcément ca prend plus de temps)
L'algo :

Code: Tout sélectionner

//-------------------------------------------------------- Include système
using namespace std;

#include
//pour memcpy()
#include
//pour time()
#include
//------------------------------------------------------ Include personnel

//------------------------------------------------------------- Constantes
#define LENGTH 13

int globale = 0;
void recurreMoi(int n,int *listeNombres,int e,int indiceCourant,int *permutCourante);
void show(int *t,int n){
   //cout';
}
$globale = 0;
function main ()
{
   $LENGTH = 11;//PAS 13 mais 11
   $t = array($LENGTH-1);//notre tableau de nombre
   $permutCourante = array($LENGTH-1);
   for($i = 0; $i ';
   echo "fact(LENGTH-1) vaut : ".Math::fact($LENGTH-1).'';//on verifie si on a bien tous les nombres
   echo "temps : ".($b-$a).'';
   return 0;
}



[abcd22]

Bonjour,

J'aimerais bien savoir, pour des raisons de pratique, si vous en connaissiez un très rapide pour générer toutes les permutations (ou mieux juste celle qui commencent par '1').

Le nombre de permutations de n éléments est n! donc par définition du problème il est impossible de trouver un algorithme dont la complexité ne soit pas exponentielle, c'est-à-dire le plus lent possible. Avec seulement les permutations qui commencent par 1 la complexité reste exponentielle mais en (n - 1)! seulement.
Avec n = 13 il y a déjà plus de 6 milliards de permutations, dont 479 001 600 qui commencent par 1.

[Doraki]

Si tu veux générer toutes les permutations c'est légèrement mieux de pas recalculer toute la permutation à chaque fois comme t'es en train de faire.

Mais bon.., 12! c'est beaucoup et on peut rien y faire.

[fatal_error]

plop,

je remonte ce post qui date. Ya pas longtemps j'ai du générer des permutations...et au lieu de mon algo tout merdique, yen a un qui run pas mal.
(le dernier) : 12second pour une perm a 12 elem, et 169 pour une perm a 13...sur un pc pas exceptionnel (2ghz)