Algorithme rapide de permutation

La question :

bonjour

Je cherche un algo le plus rapide possible pour
générer les permutations de {1, 2, .., 9}

On part d'un tableau T = {1, 2, 3, ...9}

qu'on passe en argument d'une fonction

qui me ressort par exemple l'ordre suivant

T = {3, 1, 9, .. 8}

et après 9! itération on retrouve T = {1, 2, 3, ...9}

Peu importe l'ordre dans lequel la liste est obtenue

pour ceux qui seraient intéressé, j'ai un déjà algo qui
donne la liste dans l'ordre lexicographique (mais il est
lent)

le voici
1. Déterminer le plus grand entier i tel que t.(i) < t.(i + 1).
2. Permuter t.(i) avec le plus petit élément qui lui
soit plus grand parmi t.(i + 1), . . . , t.(n ? 1).
3. Trier la partie restante du tableau (i.e. t.(i +1), . . . , t.(n ? 1)).

merci

Poser votre question sur le forum Programmation

Les 3 réponses :

"ast" a écrit dans le message de
news:5170f1af$0$3735$...


bonjour

Je cherche un algo le plus rapide possible pour
générer les permutations de {1, 2, .., 9}

On part d'un tableau T = {1, 2, 3, ...9}

qu'on passe en argument d'une fonction

qui me ressort par exemple l'ordre suivant

T = {3, 1, 9, .. 8}

et après 9! itération on retrouve T = {1, 2, 3, ...9}

Peu importe l'ordre dans lequel la liste est obtenue

pour ceux qui seraient intéressé, j'ai un déjà algo qui
donne la liste dans l'ordre lexicographique (mais il est
lent)

le voici
1. Déterminer le plus grand entier i tel que t.(i) < t.(i + 1).
2. Permuter t.(i) avec le plus petit élément qui lui
soit plus grand parmi t.(i + 1), . . . , t.(n ? 1).
3. Trier la partie restante du tableau (i.e. t.(i +1), . . . , t.(n ? 1)).

merci



Tout dépend des outils utilisés !

Nous ne sommes pas ici dans le cadre de l'étude d'une
rapidité de convergence vers une solution, à laquelle
on peut mathématiquement répondre, mais d'une
recherche de la performance.

Tous les algos de tri, Bubble sort, Quicksort, permutations, etc ...
verront leurs performances varier selon les caractéristiques
et de tel ou tel langage, interpréteur ou compilateur, et du
support physique sur lequel il s'éxécute (tâches parallélisées
ou non, gestion de séquences ininterruptibles, etc.).

Il n'y a pas de solution ultime et universelle.

Il est même souvent nécessaire d'utiliser plusieurs algos
avec un point-selle permettant de décider quand il est
plus efficace de changer de méthode, en cours de traitement.

De plus, la répartition des valeurs joue un rôle dans le temps
de traitement, donc suivant le cas : une seule série de données
ou un certain nombre de séries de données ou une infinité de
séries de données, on utilisera un stratégie globale, ou une
tactique locale, voire même une heuristique !

Au fait, quand tu dis "lent", quel est l'ordre de grandeur ?

Gérard.

"@wanadoo" a écrit dans le message de
news:kkrfua$92e$...


"ast" a écrit dans le message de
news:5170f1af$0$3735$...


bonjour

Je cherche un algo le plus rapide possible pour
générer les permutations de {1, 2, .., 9}

On part d'un tableau T = {1, 2, 3, ...9}

qu'on passe en argument d'une fonction

qui me ressort par exemple l'ordre suivant

T = {3, 1, 9, .. 8}

et après 9! itération on retrouve T = {1, 2, 3, ...9}

Peu importe l'ordre dans lequel la liste est obtenue

pour ceux qui seraient intéressé, j'ai un déjà algo qui
donne la liste dans l'ordre lexicographique (mais il est
lent)

le voici
1. Déterminer le plus grand entier i tel que t.(i) < t.(i + 1).
2. Permuter t.(i) avec le plus petit élément qui lui
soit plus grand parmi t.(i + 1), . . . , t.(n ? 1).
3. Trier la partie restante du tableau (i.e. t.(i +1), . . . , t.(n ? 1)).

merci



Tout dépend des outils utilisés !

Nous ne sommes pas ici dans le cadre de l'étude d'une
rapidité de convergence vers une solution, à laquelle
on peut mathématiquement répondre, mais d'une
recherche de la performance.

Tous les algos de tri, Bubble sort, Quicksort, permutations, etc ...
verront leurs performances varier selon les caractéristiques
et de tel ou tel langage, interpréteur ou compilateur, et du
support physique sur lequel il s'éxécute (tâches parallélisées
ou non, gestion de séquences ininterruptibles, etc.).

Il n'y a pas de solution ultime et universelle.

Il est même souvent nécessaire d'utiliser plusieurs algos
avec un point-selle permettant de décider quand il est
plus efficace de changer de méthode, en cours de traitement.

De plus, la répartition des valeurs joue un rôle dans le temps
de traitement, donc suivant le cas : une seule série de données
ou un certain nombre de séries de données ou une infinité de
séries de données, on utilisera un stratégie globale, ou une
tactique locale, voire même une heuristique !

Au fait, quand tu dis "lent", quel est l'ordre de grandeur ?



j'ai des centaines de milliers de permutations à gérer
et globalement le programme est trop lent à fournir un
résultat, de l'ordre de l'heure.

J'ai trouvé un algo plus rapide; l'algorithme Steinhaus?
Johnson?Trotter décrit ici:

http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm




Gérard.

ast écrivit :



"@wanadoo" a écrit dans le message de
news:kkrfua$92e$...


"ast" a écrit dans le message de
news:5170f1af$0$3735$...


bonjour

Je cherche un algo le plus rapide possible pour
générer les permutations de {1, 2, .., 9}

On part d'un tableau T = {1, 2, 3, ...9}

qu'on passe en argument d'une fonction

qui me ressort par exemple l'ordre suivant

T = {3, 1, 9, .. 8}

et après 9! itération on retrouve T = {1, 2, 3, ...9}

Peu importe l'ordre dans lequel la liste est obtenue

pour ceux qui seraient intéressé, j'ai un déjà algo qui
donne la liste dans l'ordre lexicographique (mais il est
lent)

le voici
1. Déterminer le plus grand entier i tel que t.(i) < t.(i + 1).
2. Permuter t.(i) avec le plus petit élément qui lui
soit plus grand parmi t.(i + 1), . . . , t.(n ? 1).
3. Trier la partie restante du tableau (i.e. t.(i +1), . . . , t.(n ?
1)).

merci



Tout dépend des outils utilisés !

Nous ne sommes pas ici dans le cadre de l'étude d'une
rapidité de convergence vers une solution, à laquelle
on peut mathématiquement répondre, mais d'une
recherche de la performance.

Tous les algos de tri, Bubble sort, Quicksort, permutations, etc ...
verront leurs performances varier selon les caractéristiques
et de tel ou tel langage, interpréteur ou compilateur, et du
support physique sur lequel il s'éxécute (tâches parallélisées
ou non, gestion de séquences ininterruptibles, etc.).

Il n'y a pas de solution ultime et universelle.

Il est même souvent nécessaire d'utiliser plusieurs algos
avec un point-selle permettant de décider quand il est
plus efficace de changer de méthode, en cours de traitement.

De plus, la répartition des valeurs joue un rôle dans le temps
de traitement, donc suivant le cas : une seule série de données
ou un certain nombre de séries de données ou une infinité de
séries de données, on utilisera un stratégie globale, ou une
tactique locale, voire même une heuristique !

Au fait, quand tu dis "lent", quel est l'ordre de grandeur ?



j'ai des centaines de milliers de permutations à gérer
et globalement le programme est trop lent à fournir un
résultat, de l'ordre de l'heure.

J'ai trouvé un algo plus rapide; l'algorithme Steinhaus?
Johnson?Trotter décrit ici:

http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm


J'allais proposer le fascicule de Knuth, mais je vois qu'il est en
référence sur cette page.

Poser votre question sur le forum Programmation

Questions similaires :

algorithme de la fonction pow

[Copie et suivi vers fr.comp.algorithmes] Le 13/09/2011 10:24, Etienne a écrit dans fr.sci.maths : Dans quelle implémentation sur quelle machine ? Sans cette précision, je ne vois pas bien qui pourrait deviner de quel algorithme il s'agit exactement ! À tout hasard, un algorithme est exposé ici...

algorithme itératif de calcul de distance

Salut. l'algorithme de Bresenham http://fr.wikipedia.org/wiki/Algorithme_de_trac%C3%A9_d'arc_de_cercle_de_Bresenham permet de tracer un cercle en utilisant des opération simple. existe t-il un algorithme pour remplir le disque avec la valeur de la distance des points par rapport à leur centre...

Algorithme de simulation

Bonjour , Je suis à la recherche d'un algorithme de simulation discrete informatique et l'algorithme ou le code source colonie de fourmie j'ai fais boucoup de recherche mais j'ai pas trouvé l'algorithme .Please Bonne année et Merci . All the best .

Algorithme de minimisation de variable.

Salut. j'ai 275 équations (qui ne sont que des additions, mais bon a aurait pu être autre chose), lesquels sont dépendantes les unes des autres voila une portion du...

Algorithme un peu compliqué de recherche de motif.

Salut. Alors j'ai un problème assez compliqué. il est d'ailleurs tellement compliqué que je ne suis pas sur d'arriver à l'expliquer... Dans un premier temps je dois chercher si une sequence (disons de lettres) est "inclues" dans une autres (que je vais appeler séquence source) exemple: séquence :...