Re: algorithme dee permutation

[Olivier Miakinen]

[copie et suivi vers fr.comp.algorithmes]

Bonjour,

Le 04/01/2020 10:54, François Patte a écrit :
>
> Voici une suite de permutations des éléments d'un ensemble qui permet
> d'écrire de manière exhaustive les n! permutations:
>
> 1 2 3 4 5 6 7
> 2 1 3 4 5 6 7
> 1 3 2 4 5 6 7
> 3 1 2 4 5 6 7
> 2 3 1 4 5 6 7
> 3 2 1 4 5 6 7
> 1 2 4 3 5 6 7
> 2 1 4 3 5 6 7
> 1 4 2 3 5 6 7
> 4 1 2 3 5 6 7
> 2 4 1 3 5 6 7
> 4 2 1 3 5 6 7
> 1 3 4 2 5 6 7
> 3 1 4 2 5 6 7
> ............
>
> Je ne vais pas écrire les 5040 lignes...
>
> Est-ce un algorithme connu?

En tout cas, il me semble facile de l'écrire sous forme d'un algorithme
récursif.

================================================
Fonction recurse(liste1, liste2)
Si liste2 est vide, imprimer liste1
Sinon,
Pour tout élément de liste2,
recurse(liste1 + élément, liste2 - élément)

recurse(vide, {1 2 3 4 5 6 7})
================================================

Dans l'algorithme ci-dessus, ce que j'ai noté « liste1 + élément »
ajoute l'élément à la fin de la liste, alors que ce que j'ai noté
« liste2 - élément » retire l'élément où qu'il soit.

Par exemple,
{5 6 1 3} + 2 -> {5 6 1 3 2}
{5 6 1 3} - 1 -> {5 6 3}


...

Euh... je viens juste de lire vraiment ton exemple, et de voir que
ce sont les derniers éléments qui changent en dernier. Tu devrais
pouvoir facilement adapter mon algorithme en conséquence, et je vois
plusieurs méthodes pour le faire. Demande si ce n'est pas le cas.

--
Olivier Miakinen