Liste

[Juzo]

Bonjour,

La réponse à cette question est peut-être simple et ne vous intéressera peut-être pas, mes excuses par avance si c'est le cas.

Je me demandais s'il est possible de faire moins d'opérations pour mesurer le désordre d'un ensemble que pour ordonner complètement cet ensemble, vis-à-vis d'un ordre défini.

On peut imaginer par exemple une liste de mots, l'ordre défini étant l'ordre alphabétique.
Le nombre d'opérations (dans cet exemple ou dans un autre) pourrait correspondre au nombre d'opérations réalisées par une machine qui suivrait un algorithme (pour ranger la liste dans l'ordre alphabétique, ou bien pour mesurer son désordre vis-à vis de l'ordre alphabétique).

Les termes méritent encore d'être précisés, désolé si ça manque de précision j'ai peu de connaissances sur ce sujet..

A priori je dirais que le désordre se mesure justement en nombre d'opérations qu'il faudrait réaliser pour ordonner complètement la liste.

Bonne soirée
-----

[Juzo]

Edit : A priori la question est idiote, puisque la réponse serait de toute évidence "non".

[amineyasmine]

Bonjour,

A priori je dirais que le désordre se mesure justement en nombre d'opérations qu'il faudrait réaliser pour ordonner complètement la liste.

Bonne soirée

bonjour
d'après t'as définition de mesurer le désordre, il y équivalence entre mesurer le désordre et ordonner , même nombre d'opérations.

il y a une question importante, est ce que ordonner la liste est un problème P ou NP ?

[amineyasmine]

Edit : A priori la la question ........

A priori la réponse en toute évidence est "non"

[A voir en vidéo sur Futura]

[Liet Kynes]

C'est une question intéressante, pour une liste de mots désordonnée d'un point de vue alphabétique on peut par exemple prendre les mots deux à deux et les ordonner entre eux puis recommencer jusqu' à ce qu'il n'y est plus de "désordre". Le nombre de fois ou l'on recommence serait inférieur de 1 au nombre de fois ou l'on mesure l'ordre car les deux opérations seraient concomitantes et le dernier "tri" n'appelle pas de reclassement.

[Juzo]

Bonjour, merci pour vos réponses.

Tout d'abord pour la méthode de mesure du désordre :

Selon l'exemple que j'ai pris, on pourrait dire intuitivement qu'une liste de mots A ordonnée dans l'ordre anti-alphabétique (à l'envers) serait plus ordonnée vis-à-vis de l'ordre alphabétique qu'une liste B de mot rangés aléatoirement.

On peut imaginer deux manières de mesurer l'ordre d'une liste qui devraient rendre compte de cela :

1) Mesurer la "logique interne" du rangement de la liste, vis-à-vis de l'ordre choisi. Difficile de définir rigoureusement comment cette logique est mesurée, mais on peut supposer que la liste anti-alphabétique aurait un score plus fort que la liste aléatoire. Si vous avez des suggestions pour mesurer la logique d'un ensemble vis-à-vis d'un ordre O je suis preneur. Et il faut encore définir le nombre d'opérations que cela coûte.

2) Mesurer le nombre d'opérations qu'il faut pour ordonner la liste. Il faut alors définir des opérations élémentaires :
- Déplacer un éléments dans la liste
- permuter deux éléments de la liste.
Sauf erreur, avec ces opérations la liste aléatoire et la liste anti-alphabétique obtiendront toujours le même score puisque le même nombre d'opérations sera nécessaire pour les ordonner.
Je suggère donc de rajouter une autre opération élémentaire :
- substituer chaque indice de position des éléments d'un sous-ensemble par un autre indice de position, suivant une formule. Par exemple pour la liste anti-alphabétique qui contiendrait n éléments, chaque élément de position i irait à la position n + 1 - i, ce qui reviendrait à "retourner" la liste.
La liste anti-alphabétique serait alors ordonnée en une seule opération, ce qui est impossible avec la liste aléatoire.

Cette opération de substitution englobe la 1ère, le déplacement (substitution sur un seul élément). Est-ce que ça engloberait aussi la permutation ?

Pour ce qui est de mesurer le désordre avec moins d'opérations que pour ordonner la liste, je vais prendre le temps de comprendre la réponse de Liet Kynes avant de répondre.

[Juzo]

PS : on est d'accord que la substitution demande plusieurs sous-opérations à une machine, puisque il faut l'appliquer à chaque élément d'un sous-ensemble, mais je propose justement de la compter comme une seule opération.
La mesure de l'ordre d'un ensemble selon un ordre O, serait donc le nombre minimum de formules de substitution qu'il faudrait appliquer à ses sous-ensembles pour l'ordonner complètement selon O.

[ArchoZaure]

Bonjour.

[Début des deux secondes de réflexion.]
Je trouve personnellement cette manière de quantifier le désordre complètement idiot.
Le désordre apparait dés lors qu'on observe l'ensemble.
C'est "écrit dessus".
Encore faut-il savoir le lire...
[Fin des deux secondes de réflexion.]

Dit comme ça c'est obscure n'est-ce pas ?
Mais ça vous fera une énigme.

[JPL]

Sachant qu’il existe plusieurs méthodes algorithmiques pour trier une liste (c’est le B A BA de la programmation) et qu’elles ne nécessitent pas le même nombre d’opérations intermédiaires, cela fournira plusieurs valeurs différentes du désordre d’un même liste. On reste donc très à la surface d’un problème intéressant, pour ne pas dire que c’est du bavardage naïf.

[Juzo]

Sachant qu’il existe plusieurs méthodes algorithmiques pour trier une liste (c’est le B A BA de la programmation) et qu’elles ne nécessitent pas le même nombre d’opérations intermédiaires, cela fournira plusieurs valeurs différentes du désordre d’un même liste. On reste donc très à la surface d’un problème intéressant, pour ne pas dire que c’est du bavardage naïf.

Bonjour, justement pour caractériser une mesure du désordre il suffit de choisir le minimum d'opérations intermédiaires réalisées toutes méthodes confondues, non ?
Et peut-il exister des méthodes de mesure du désordre demandant MOINS d'étapes intermédiaires que la méthode de tri la moins gourmande ? C'était ma question initiale. Intuitivement je dirais que non mais c'est la démonstration rigoureuse qui m'intéressait.
Je suis bien conscient de la naïveté de mes propositions et qu'il existe déjà des théories sur ce sujet, j'espérais avoir des informations à propos de ces théories.

Le désordre apparait dés lors qu'on observe l'ensemble.
C'est "écrit dessus".
Encore faut-il savoir le lire...

Pour moi cela reste abscons... Comment peut-on "lire" la mesure du désordre directement en "observant l'ensemble" ?

[Liet Kynes]

Sachant qu’il existe plusieurs méthodes algorithmiques pour trier une liste (c’est le B A BA de la programmation) et qu’elles ne nécessitent pas le même nombre d’opérations intermédiaires, cela fournira plusieurs valeurs différentes du désordre d’un même liste. On reste donc très à la surface d’un problème intéressant, pour ne pas dire que c’est du bavardage naïf.

C'est en cela (ta réponse) que c'est intéressant; "calculer le plusieurs " : comment et en fonction de quoi?

[Deedee81]

Salut,

Soyons précis (être dans le forum ludique ne justifie pas de bavarder comme un canard épileptique).

- trier une liste, c'est facile, on sait faire et ce n'est pas un problème NP. Et ce quel que soit le type d'ordre qu'on veut puisque tout algorithme de tri le fait à travers une fonction de comparaison. Les algorithmes les plus performant sont par exemple le Heap-sort et le tri-fusion. C'est une complexité O(n.log n) donc très performant : https://fr.wikipedia.org/wiki/Algorithme_de_tri

- Mesurer la complexité/désordre d'une liste. Il n'y a malheureusement pas de définitions standards. Tout dépend surtout des usages. On pourrait évidemment imaginer une mesure simpliste : par exemple, je parcours la liste, je compte le nombre de fois où les éléments n et n+1 sont dans l'ordre et le nombre de fois où ils ne le sont pas. Si c'est deux nombres sont proches c'est désordonné. Une telle mesure est évidemment plus rapide que le tri (c'est en complexité O(n)). Mais il existe aussi des définitions classiques : par exemple, on utilise un (bon) algorithme de compression et on vérifie le résultat : plus il est petit plus la liste était ordonnée. Ca dépend de l'algo mais c'est de l'ordre de la complexité du tri. C'est un mesure utile. Un méthode plus rigoureuse est la complexité de Kolmogorov https://fr.wikipedia.org/wiki/Comple..._de_Kolmogorov peu utilisée car assez couteuse, beaucoup plus cette fois que le tri. Il existe aussi une mesure "d'information utile" (une liste strictement ordonnée ne porte que peu d'info, une liste totalement désordonnée non plus), utile en théorie du signal mais j'ai oublié comment s'appelle la mesure (j'avais lu ça dans un article de Delahaye dans Pour La Science).

Bref : la réponse est parfois oui parfois non souvent floue. Et je ne suis même pas Normand

Juzo, il faudrait peut-être que tu précises l'objectif précis de ta question initiale car là franchement c'est plus épais qu'un brouillard Belge. Et même dans le forum ludique ça fait.... désordre

[ArchoZaure]

Il existe aussi une mesure "d'information utile" (une liste strictement ordonnée ne porte que peu d'info, une liste totalement désordonnée non plus), utile en théorie du signal mais j'ai oublié comment s'appelle la mesure (j'avais lu ça dans un article de Delahaye dans Pour La Science).

Tient à ce propos, je suis retombé sur cette synthèse de Jean-Paul Delahaye :

Le simple s'oppose au complexe.

Pourtant complexe signifie :
sans ordre, sans régularité, aléatoire

ou signifie :
organisé, fortement structuré, riche en information

Il y a deux types de complexité :
la complexité aléatoire (le désordre)
la complexité organisée (l'ordre non trivial et structuré)

https://www.fermedesetoiles.com/docu...h_DELAYAHE.pdf

Il y distingue donc :
Complexité aléatoire appelée complexité de Kolgomorov ou complexité de Chaitin-Kolgomorov ou complexité algorithmique, voir page 12
Complexité organisée.

[Deedee81]

Je te remercie, beaucoup plus technique que l'article en question. Vraiment intéressant.
Et j'y ai retrouvé la mesure dont je parlais :
https://fr.wikipedia.org/wiki/Profondeur_de_Bennett

[ArchoZaure]

Sinon concernant la méthode "obscure" que j'aurai appliqué dans le cas de Juzo.
Je vais juste prendre un exemple avec une liste de valeurs et proposer plusieurs ordonnancements :

Le principe :
On a n valeurs x₁, ..., x_n
On calcule "l'ensemble", donc une valeur totale de la manière suivante :
V=x₁ⁿ + ... + x_n¹

Plus la valeur V est basse et plus c'est ordonné (du plus petit au plus grand).

Par exemple :
3 7 4 1 2
V=3⁵ + 7⁴ + 4³ + 1² + 2¹ = 243+2401+64+1+2=2711

3 7 4 2 1
V=3⁵ + 7⁴ + 4³ + 2² + 1¹ = 243+2401+64+4+1=2713

1 2 3 4 7
V=1⁵ + 2⁴ + 3³ + 4² + 7¹ = 1+16+9+16+7=49

1 2 3 7 4
V=1⁵ + 2⁴ + 3³ + 7² + 4¹ = 1+16+9+49+4=79

Il y aura bien sûr des "trous" dans l'ensemble des valeurs possibles... certaines possibilités en interdisant d'autres.

Je m'excuse si c'est "un peu" faux, mais comme ça m'est venu comme ça en 3 secondes j'ai trouvé le rendement intéressant.
Je suis aussi bien conscient qu'on triche lorsqu'on ne fait pas appel à un algorithme basé uniquement sur des 0 et des 1, mais d'un point de vue pratique c'est peut-être utile.

[Deedee81]

Je m'excuse si c'est "un peu" faux, mais comme ça m'est venu comme ça en 3 secondes j'ai trouvé le rendement intéressant.

C'est astucieux et amha tant du point de vue "coût" (un tel calcul est assez facile à fortement optimiser, c'est pas les méthodes numériques qui manquent) que "validité" (à quantifier) ça doit être du même ordre que ma méthode de comparaison des éléments voisins.

Petite rectification ci-dessus (encore merci pour le lien d'ailleurs) : Kolmogorov est pas seulement couteux à calculer : c'est carrément non calculable (au sens Turing, donc en fait on peut le calculer jusqu'à une taille donnée de suite pour un programme donné, mais avec un coût faramineux lorsque la taille augmente). Il existe des algos approchés, mais je les connais trop mal pour en juger.

[Juzo]

Bonjour, merci pour vos réponses !

Juzo, il faudrait peut-être que tu précises l'objectif précis de ta question initiale car là franchement c'est plus épais qu'un brouillard Belge. Et même dans le forum ludique ça fait.... désordre

Je vais essayer d'être plus précis. J'utiliserai "désordre aléatoire" à la place de désordre (en espérant que cela aide )
Il y a une question générale et deux défis. Pour chaque défi j'identifie une hypothèse de départ qui est pourrait être invalidée.

1) Question : Quelles sont les méthodes pour mesurer le désordre aléatoire d'une liste par rapport à un ordre O défini, et existe-t-il une seulement manière de classer tout ensemble de listes de la plus ordonnée à la moins ordonnée par rapport à cet ordre (peut-on définir une relation d'ordre pour un ordre O, justement) ? Vous m'avez donné des pistes sur ce sujet.

2) Hp 1 : soit une liste L. On obtient une mesure M du désordre aléatoire de L par rapport à un ordre O donné, en comptant le nombre d'opérations nécessaires pour ordonner complètement L en suivant un algorithme de rangement optimisé pour l'ordre O. Une méthode basique est de ranger la liste L en suivant l'algorithme et de compter les opérations réalisées. Défi : trouver une manière obtenir la valeur de M en faisant moins d'opérations que pour ordonner complètement la liste L avec l'algorithme (si c'est possible).

3) Hp 2 : Si on considère l'ordre alphabétique, alors une liste rangée dans l'ordre anti-alphabétique a un désordre aléatoire bien plus bas qu'une liste rangée... aléatoirement. (cet exemple me paraît intuitif mais on aurait pu en prendre d'autres) Défi : indiquer une méthode de mesure du désordre aléatoire qui rende compte de cela.

On calcule "l'ensemble", donc une valeur totale de la manière suivante :
V=x1n + ... + xn1

- Avec cette méthode, il me semble que la liste anti-alphabétique obtient justement le plus haut score de désordre aléatoire ! Si on accepte l'hypothèse selon laquelle elle contient moins de désordre aléatoire qu'une liste aléatoire, ça invalide ta méthode pour le défi 1.
Proposition : mesurer le désordre aléatoire d'une liste L en comptant le nombre de formules de substitution qu'il faut appliquer à des sous-ensembles de L, pour l'ordonner complètement. Avec l'ordre anti-alphabétique, une seule formule : i -> n+1-i. Donc un désordre de niveau 1
- De plus est-on sûr que ce calcul, même s'il tient en une seule expression, demande moins d'opérations que de ranger complètement la liste ? (Défi 2) Vraie question, je n'ai pas assez de connaissances pour faire une affirmation.

Je suis conscient que je n'ai précisé ces défis qu'à l'instant.

[vgondr98]

En R, on peut utiliser la fonction cor pour comparer des listes numériques.
liste1 <- c(0,1,2)
liste2 <- c(2,1,0)
test <- cor.test(liste1, liste2)

test

Pearson's product-moment correlation

data: liste1 and liste2
t = -Inf, df = 1, p-value < 2.2e-16
alternative hypothesis: true correlation is not equal to 0
sample estimates:
cor
-1

[Juzo]

Re-bonjour, je crois que mon message précédent était encore plus obscur désolé, je l'ai écrit en étant pressé par le temps... J'y reviens plus tranquillement dans une dernière tentative.

Sauf erreur les méthodes proposées par Deedee81 comme la compression permettent de mesurer le désordre aléatoire intrinsèque d'une liste. Dans cette discussion il s'agit de mesurer le désordre aléatoire vis-à-vis d"un ordre arbitraire prédéfini.

Je pourrais généraliser les défis précédents en donnant deux objectifs :
1) trouver une méthode fiable pour caractériser le désordre aléatoire d'une liste L vis-à-vis de n'importe quel ordre O prédéfini.
(à condition que cette quantification soit définie pour L, on n'ira pas vérifier si une liste de nombre est rangée dans l'ordre alphabétique...).

vgondr98 propose une méthode que je n'ai pas tout à fait compris.

2) Trouver la méthode algorithmique la moins gourmande en opérations pour tester l'ordre alphabétique (ou l'ordre croissant), puis essayer de généraliser.

ArchoZaure a proposé le calcul V=x1^n + ... + xn^1 pour tester l'ordre croissant de nombres mais ça ne me semblait pas satisfaisant, puisqu'une liste parfaitement rangée parfaitement mais à l'envers (ordre décroissant) aura le pire score.
La méthode de vgondr98 entre peut-être dans cet objectif ?

Pour l'objectif 1) j'imagine un paquet de feuillets avec un mot par feuillet, qui doit être rangé dans l'ordre alphabétique. Si le paquet est dans l'ordre anti-alphabétique il suffit de le retourner. Le paquet aléatoire est beaucoup plus long à ranger.
Je définis donc des opérations élémentaires sur les sous-groupes de feuillets du paquet : déplacer un sous-groupe dans le paquet ou retourner un sous-groupe.
Je le traduis mathématiquement par des formules de substitution sur les indices des feuillets : déplacer un sous groupe revient à ajouter +k ou -k à l'indice des feuillets, retourner un sous-groupe d'indices i à j revient à remplacer chaque indice k par i+j-k (sauf erreur).

Pour l'objectif 2) je n'ai pas de proposition, sauf ranger le paquet et compter les opérations réalisées.

[JPL]

Mais que fait cette discussion dans Science ludique ? !

[pm42]

Mais que fait cette discussion dans Science ludique ? !

Je suis de loin mais je dirais que c'est du bavardage naïf pour citer quelqu'un.
Et que ce bavardage qui ignore notamment certaines remarques pertinentes qui ont été faites.

De plus, Juzo utilise le concept "d'algorithme de rangement optimisé pour l'ordre O" sans que cela soit défini et ait du sens.
Les algorithmes sont indépendants de l'ordre (c'est même un argument qu'on passe en programmation) et "optimisé" veut dire quoi ?
Chaque algorithme a une complexité moyenne mais aussi des cas favorables et défavorables.

Par exemple, certains algorithmes vont faire un nombre important d'opérations sur une liste déjà triée (à l'endroit où à l'envers).
Avec la définition donnée, la mesure du désordre par le nombre d'opérations de l'algorithme donnerait donc un résultat aberrant.
Pire, un changement d'algorithme pourrait donner des résultats très différents.

Ce n'est pas un hasard si les liens donnés par Deedee81 sont des méthodes coûteuses ou même non calculables : c'est le prix pour avoir un résultat cohérent.
Si on veut simplement une évaluation rapide du désordre qui soit heuristique et pas 100% solide, on peut repartir sur ce qui a été suggéré plus haut : compter les changement des direction, mesurer les périodes de stricte croissance ou décroissance et calculer moyenne et écart-type, etc.
On va se retrouver en O(n) sauf à faire du "sampling".
Ces méthodes ne sont pas spécialement intéressantes d'un point de vue théoriques mais pourraient éventuellement servir en pratique encore qu'il serait intéressant de connaitre des cas d'usage pour ne pas parler dans le vide.

[JPL]

Si j’ai fait ma remarque dans le message n° 9 c’est que j’avais bien en tête que la discussion abordait de façon extrêmement naïve une question touchant un domaine effroyablement complexe... celui de la notion mathématique de complexité.

[pm42]

Si j’ai fait ma remarque dans le message n° 9 c’est que j’avais bien en tête que la discussion abordait de façon extrêmement naïve une question touchant un domaine effroyablement complexe... celui de la notion mathématique de complexité.

Oui, c'est ce que je confirmais : Deedee81 a donné des liens mais ils ont été ignorés et à la place, on a du "j'ai inventé un truc intuitivement sans avoir étudié ce qui a déjà été fait sur le sujet et je me dis que ça marche".
C'est le classique de "je fais de la science ou de l'ingénierie avec les mains, au feeling".
Cela ne marche jamais.

[Juzo]

Bonjour,
Vous avez en partie raison mais pour ma (petite) défense :
- Je n'ai pas eu le temps de consulter les liens de Deedee81 et n'aurai pas le temps avant dimanche, en attendant j'essayais juste de répondre à sa demande de reformuler plus clairement mes objectifs...
Ce sont néanmoins des sujets dont j'ai déjà entendu parlé (Kolmogorov, compression,) et j'en ai tenu compte en disant qu'il y avait "peut-être" une différence ici puisqu'on s'intéresse à un ordre défini (l'ordre alphabétique ou croissant par exemple). Je n'ai pas "purement" ignoré ses propos.
- j'ai expliqué moi-même que mon message 17 était peu clair donc c'est dommage d'en utiliser des extraits pour souligner son inanité. Mon message suivant est-il aussi "inepte" ?


Par rapport à d'autres remarques :

De plus, Juzo utilise le concept "d'algorithme de rangement optimisé pour l'ordre O" sans que cela soit défini et ait du sens.
Les algorithmes sont indépendants de l'ordre (c'est même un argument qu'on passe en programmation) et "optimisé" veut dire quoi ?
Chaque algorithme a une complexité moyenne mais aussi des cas favorables et défavorables.

Par exemple, certains algorithmes vont faire un nombre important d'opérations sur une liste déjà triée (à l'endroit où à l'envers).
Avec la définition donnée, la mesure du désordre par le nombre d'opérations de l'algorithme donnerait donc un résultat aberrant.
Pire, un changement d'algorithme pourrait donner des résultats très différents.

Algorithme optimisé pour un ordre O et une liste L, donc. Ce qui revient à dire que le désordre est le nombre d'opérations qu'il faut pour ranger la liste le plus efficacement possible, ce qui n'est pas aberrant non plus. Plus un enfant range rapidement sa chambre, moins elle est en désordre (quitte à utiliser des arguments naïfs...). Merci pour cette remarque très juste que j'ai bien prise en compte, je n'y avais pas pensé.
Par contre je ne comprends pas (désolé) ce que veut dire "Les algorithmes sont indépendants de l'ordre". Si l'ordre défini est de ranger d'abord les nombres pairs dans n'importe quel ordre puis les impairs dans n'importe quel ordre on ne va pas utiliser le même algorithme de rangement que pour un ordre croissant. Je veux bien des explications sur ce sujet si vous avez le temps.

Bien entendu l'idée d'algorithme optimisé (ou efficace) est difficile à généraliser et vous dites plus loin :

Ces méthodes ne sont pas spécialement intéressantes d'un point de vue théoriques mais pourraient éventuellement servir en pratique encore qu'il serait intéressant de connaitre des cas d'usage pour ne pas parler dans le vide.

Ce qui tombe bien, car j'ai écrit dans mon dernier message censé être plus clair :

Trouver la méthode algorithmique la moins gourmande en opérations pour tester l'ordre alphabétique (ou l'ordre croissant), puis essayer de généraliser

Évidemment j'ai compris maintenant qu'on ne peut pas trouver un algorithme traitant efficacement toute liste qu'on lui présente, sans résultat aberrant. J'ai appris quelque chose, ce qui est ludique pour moi et peut-être d'autres lectrices et lecteurs de mon niveau. Je vérifierai quand même.

Il reste ma proposition, pourtant mathématique, de caractériser le désordre par le nombre de formule de substitution appliquées à des sous-ensembles de la liste pour la ranger complètement. Ce qui pourrait répondre à

1) trouver une méthode fiable pour caractériser le désordre aléatoire d'une liste L vis-à-vis de n'importe quel ordre O prédéfini, à condition que cette caractérisation soit "définie sur L"

Elle n'a pas reçu de commentaire, sûrement parce que trop naïve ou inadéquate ? Évidemment je sais qu'il existe déjà des théories sur le sujet, mais ce qui est ludique pour moi est d'y réfléchir sous forme d'énigme et de corriger mes erreurs.

Merci quand même pour vos retours. Je n'ai pas pu prendre 3 jours pour répondre, donc je suis conscient de produire encore du bavardage comme tout novice sur un sujet.

[pm42]

Si l'ordre défini est de ranger d'abord les nombres pairs dans n'importe quel ordre puis les impairs dans n'importe quel ordre

C'est exactement le problème de ce fil et de ce genre de bavardage : "ordre" a un sens précis en mathématique et il a été utilisé comme cela dans tous le fil, implicitement comme ordre total.
Là, on est passé sur un ordre partiel au mieux ce qui change tout.

Tant que rien ne sera défini mathématiquement, on restera dans la discussion de bistrot et la sous-estimation massive de la difficulté du sujet.

[vgondr98]

La méthode de la corrélation est simple. Si tu passes deux listes identiques à la fonction cor alors elle retourne 1, si tu passes deux listes ordonnés en sens opposé, tu obtiens -1 sinon si il n'y a pas de corrélation tu obtiens 0.

liste1 <- c(0,1,2,3,4,5,6,7,8,9,10)
liste2 <- c(10,9,8,7,6,5,4,3,2,1)
liste3 <- c(4,7,2,3,1,9,0,5,6,8,10)
liste4 <- c(0,1,10, 9, 8, 7, 6, 5, 4, 3, 2)

cor(liste1,liste2) = -1
cor(liste1, liste1) = 1
cor(liste1, liste3) = 0.4454545
cor(liste1, liste4) = -0.09090909

Voila quelques exemples.

[Juzo]

Tant que rien ne sera défini mathématiquement, on restera dans la discussion de bistrot et la sous-estimation massive de la difficulté du sujet.

Je n'ai jamais précisé pour le cas général s'il s'agissait d'ordre total ou partiel, mais je ne tiens pas particulièrement à garder l'ordre partiel. On peut reprendre la question pour une ordre qui serait d'abord les nombres pairs dans l'ordre croissant, puis les nombres impairs dans l'ordre décroissant si vous le souhaitez.

Je comprends l'agacement qu'il peut y avoir quand un sanglier saccage les plate-bandes théoriques avec des termes imprécis, je propose donc pour cadrer la discussion de me limiter à un cas concret et "petit" : utiliser un peu l'idée de ArchoZaure en travaillant sur les nombres 1 ; 2 ; 3 ; 4 rangés l'ordre croissant. Je ferai attention de procéder ainsi et de ne plus disserter sur de la théorie que je ne maitrise pas dorénavant, je resterai sur un cas simple et concret.

On peut donc se demander si l'on arrive à classer toutes les listes possibles avec 1 ; 2 ; 3 ; 4 de la plus ordonnée à la moins ordonnée, si la solution mathématique de mesure du désordre que j'imaginais ou toute solution que vous proposerez s'applique bien, et s'il est possible de trouver un algorithme qui ordonne les listes pareil quand on compte les opérations réalisées.
J'aurais aimé que la liste rangée dans l'ordre décroissant ne soit pas considérée comme la plus désordonnée mais peut-être faut-il abandonner cette idée ?

vgondr98 : je prendrai le temps de me renseigner sur la fonction cor avant de répondre, mais si je comprends bien la liste ordonnée en sens inverse aura le score le plus éloigné de la liste ordonnée suivant cette fonction ?

[vgondr98]

Voila une page sur la corrélation de Pearson.
http://www.biostat.ulg.ac.be/pages/S...9es%20ou%20pas.

[pm42]

vgondr98 : je prendrai le temps de me renseigner sur la fonction cor avant de répondre, mais si je comprends bien la liste ordonnée en sens inverse aura le score le plus éloigné de la liste ordonnée suivant cette fonction ?

Pas du tout : il a juste "inventé" un truc sans jamais le définir. En l'occurence, il a défini les 2 cas extrêmes mais pas ceux intermédiaires alors que c'est là qu'est la difficulté.

Quand à la corrélation de Pearson qu'il indique, elle ne marche qu'avec des suites de nombre et on ne peut pas la calculer pour mesurer le "désordre" d'une suite de chaînes par exemple.
En plus, elle ne donne pas le résultat indiqué.
Par exemple, si tu prends la liste (1, 10, 100, 1000, 100000) et que tu calcules sa corrélation de Pearson avec la même en ordre inverse, tu n'as pas -1 mais -0.26.
Ce qu'il a indiqué ne marche que pour le genre d'exemple qu'il a donné, les suites arithmétiques. Ce qui est logique puisque Pearson cherche à mesurer une corrélation linéaire.

Encore une fois, la "recherche avec les mains" sur le forum sans définition claire, sans démonstration, sans même vérifier sur plusieurs exemples mais à coup de "j'ai eu une idée" vient d'échouer.

[MissJenny]

une mesure du désordre d'un vecteur x = (x1,...,xn) pourrait être fondée sur le coefficient de corrélation de Spearman entre x et le vecteur y = (1,...,n)