Permutation de tri

Version imprimable

06/06/2021, 09h46
LucyFayry

Permutation de tri

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.
06/06/2021, 13h21
AbsoluteLogic

Bonjour,

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

Citation:

Envoyé par LucyFayry

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 >=.
06/06/2021, 14h02
WhiteCrow

Bonjour,

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

Citation:

Envoyé par AbsoluteLogic

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.
06/06/2021, 17h16
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.

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

Code:

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:

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:

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 ?

07/06/2021, 11h31
WhiteCrow

Sans doute parce que ce que tu as implémenté n'est pas un tri à bulle stable (même si ça y ressemble) :aie: :) ?
07/06/2021, 21h31
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.
08/06/2021, 09h39
LucyFayry

comment je peux prouver cette hypothèse ?
08/06/2021, 14h32
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 ∎
08/06/2021, 17h17
LucyFayry

Merci