Inscription / Connexion Nouveau Sujet
Niveau autre
Partager :

Nombre de permutation minimal

Posté par
Ryan07896
22-07-17 à 12:19

Bonjour,

Je me demandais s'il était possible de savoir le nombre de permutation minimal entre chaque élément d'une liste pour que cette dernière devienne ordonnée, en sachant que l'on peut effectuer une permutation sur deux éléments uniquement s'ils sont côte  à côte, par exemple :

A_0 = {4, 2, 1, 3} \\ A_ 1= {4, 1, 2, 3} \\ A_2 = {1, 4, 2, 3} \\ A_3 = {1, 2, 4, 3} \\ A_4 = {1, 2, 3, 4}

Dans ce cas il faut 4 étapes, mais il suffit de modifier un tout petit peu la liste de départ pour modifier le nombre d'étapes nécessaires, auriez-vous une idée de s'il est possible de trouver le nombre d'étapes uniquement grâce à la liste de base ?

Merci d'avance!

Posté par
carpediem
re : Nombre de permutation minimal 22-07-17 à 14:42

salut

pour ramener l'entier i qui se trouve à la position j = p(i) il faut |i - j| permutations

il faut donc \sum_{i = 1}^n |p(i) - i| = \sum_1^n |s^{-1}(i) - i| ...environ permutations

où s est la permutation :

1  2  3  4
4  2  1  3

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !