Discussion :

[LucyFayry]

bonjour à toutes et tous

mon problème est simple. j'ai une liste d'éléments et je dois déterminer quelle permutation l'ordonne.

par exemple si j'ai L=[b,c,a,d] la permutation qui l'ordonne est P=(2,0,1,3) car les L[ P(i) ] sont en ordre croissant. si plusieurs permutations permettent de l'ordonner il me faudrait la plus petite lexicographiquement. par exemple avec L=[a,a,a,a] n'importe quel permutation est ordonante je devrais trouver la permutation identité P=(0,1,2,3).

trouver une permutation n'est pas un souci mais c'est trouver la plus petite permutation qui est compliqué car je ne sais pas comment commencer.

merci pour l'aide que vous pourrez m'apportez.

[AbsoluteLogic]

Bonjour,

Puisque tu fais un tri implicite, il n'y aura pas de solution de complexité de moins de O(n log n).

trouver une permutation n'est pas un souci mais c'est trouver la plus petite permutation qui est compliqué car je ne sais pas comment commencer.

Ca aurait été bien que tu nous donne ta 1ère solution dans ce cas pour qu'on puisse rebondir dessus... Du coup, je reprends une solution de zéro :
Une solution consiste à trier la liste selon l'algorithme que tu veux, mais en attachant à chaque entier une valeur correspondant à sa position.
Ainsi, en triant par exemple [(b,0), (c,1), (a,2), (d,3)], tu obtiendras [(a,2), (b,0), (c,1), (d,3)], et donc une permutation inversée P^-1 = (2, 0, 1, 3). Pour avoir ta permutation à l'endroit, tu fais pour tout i=1...n, P[P^-1[i]] = i.
Pour résoudre ton problème d’ambiguïté, on a alors juste à jouer sur l'opération de comparaison qui définit ton algorithme de tri. L'opération (k1, p1) < (k2, p2) pourra renvoyer vrai si (k1 < k2) ou (k1 == k2 et p1 < p2).
Ainsi, trier [a, b, b, a] amène :
[(a,0), (b,1), (b,2), (a,3)] => tri=> [(a,0), (a,3), (b,1), (b,2)] => extraction => (0, 3, 1, 2) => inversion => (0, 2, 3, 1)
Quel que soit une autre méthode pour trouver une permutation au début, la désambiguïsation se jouera certainement sur un <, > <= ou >=.

[WhiteCrow]

Bonjour,

un tri stable t'assurera de trouver la première permutation en ordre lexicographique.

Bonjour,

Puisque tu fais un tri implicite, il n'y aura pas de solution de complexité de moins de O(n log n).
[...]

La limite O(n log n) n'existe que pour les tris par comparaisons d'éléments entre eux … Si on ne compare plus les éléments entre eux on peut s'arranger avec des limites plus basses comme un O(k.n) avec k la longueur maximale de la clé de tri en bits pour un radixsort par exemple.

[tbc92]

"trouver une permutation n'est pas un souci mais c'est trouver la plus petite permutation qui est compliqué car je ne sais pas comment commencer."

Donc, comme déjà dit, tu fais un tri "stable". Si ça ne te parle pas, tu peux considérer que tu commences par résoudre les cas de doubles.
La liste est (a,a,a,a) ? ok, on la remplace par (a0001,a0002, a0003, a0004), puis on fait le travail.

La liste est (a,c,b,d) ... on la remplace par (a0001,c0002, b0003, d0004), puis on fait le travail. Ici, la manipulation n'apporte rien. Mais on ne se pose pas de question, on la fait systématiquement.

La solution 'tri stable' est bien entendu beaucoup plus propre.

[LucyFayry]

merci pour vos réponses.
j'ai rapidement implémenté ce tri en python

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
def esort( numseq ):
     numseqlen = len(numseq)
     perm = list(range(numseqlen))
     for i in range(numseqlen):
         for j in range(i+1,numseqlen):
             if numseq[ perm[i] ] > numseq[ perm[j] ]:
                 perm[i],perm[j] = perm[j],perm[i]
     return perm

un tri à bulle qui est stable. la permutation renvoyée doit être la première lexicographique. j'ai fait ce code pour vérifier sur quelque liste

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def issorted( numseq, perm ):
     for i in range(numseq-1):
         if numseq[ perm[i] ] > numseq[ perm[j] ]:
             return false
     return true
 
n=[ random.randint(0,10) for i in range(5) ]
p=esort(n)
print(n)
print(p)
for np in itertools.permutations( range(len(n)) ):
    if issorted(n,np)[0]:
        print(np)
        if list(p)==list(np):
            print('OK')
            break
        else:
            print('NOK')

j'ai un contrexemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
[6, 6, 10, 3, 9]
[3, 1, 0, 4, 2]
(3, 0, 1, 4, 2)
NOK
(3, 1, 0, 4, 2)
OK

je me suis trompée quel que part ?

[WhiteCrow]

Sans doute parce que ce que tu as implémenté n'est pas un tri à bulle stable (même si ça y ressemble) ?

[AbsoluteLogic]

Le tri à bulle fonctionnerait, mais on doit permuter seulement des éléments adjacents jusqu'à ce qu'il n'y ait plus de permutation à faire. Toi tu permutes des éléments quelconques (indices i et j), ce qui en fait plutôt un tri par sélection, non stable.

[LucyFayry]

comment je peux prouver cette hypothèse ?

[WhiteCrow]

La question n'a de sens que s'il y a au moins deux valeurs identiques dans le tableau, sinon la permutation de tri est unique et la question ne se pose pas.

Alors on pourrait émettre l'hypothèse qu'un tri stable ne donne pas la plus petite permutation au sens lexicographique du terme.
Avec A[0..n-1] : le tableau de départ, p : la permutation donnée par le tri stable, cela se traduirait par :
∃ (i,j)∈ [0,n[² tq i<j et A[i]=A[j] et p(i) > p(j)
car on pourrait trouver une nouvelle permutation plus petite au sens lexicographique en construisant p'=p avec p'(i)=p(j) et p'(j)=p(i).

Or par définition pour un tri stable on a forcément : ∃ (i,j)∈ [0,n[² tq i<j et A[i]=A[j] ⇒ p(i) < p(j).
Cela contredit notre hypothèse de départ et par conséquent un tri stable fournit la plus petite permutation au sens lexicographique du terme ∎

[LucyFayry]

Merci