Comment obtenir les indices d'un tableau trié en Python

200

J'ai une liste numérique:

myList = [1, 2, 3, 100, 5]

Maintenant, si je trie cette liste pour l'obtenir [1, 2, 3, 5, 100]. Ce que je veux, ce sont les indices des éléments de la liste d'origine dans l'ordre trié, c'est-à-dire [0, 1, 2, 4, 3] --- la fonction de tri de MATLAB qui renvoie à la fois les valeurs et les indices.

Gyan
la source
@unutbu Ce n'est pas dupe (OMI). La question ne contredit pas en utilisant Numpy.argsort ()
amit
@amit: Que voulez-vous dire par "ne contredit pas"?
unutbu
@unutbu Numpy.argsort () est une bonne réponse à cette question, cela pourrait être une dupe à l'autre thread lié (que vous avez également fermé et je pense que vous ne devriez pas avoir) mais pas à celui que vous avez mentionné, comme Numpy. argsort () est une bonne réponse pour ces deux, mais PAS pour celle à laquelle vous avez fait référence.
2015
1
Malheureusement, cette question a un grave défaut dans son choix d'exemple, car deux façons différentes de lire la question donneraient la même réponse lorsque l'entrée est juste une transposition hors de l'ordre trié.

Réponses:

147

Quelque chose comme la prochaine:

>>> myList = [1, 2, 3, 100, 5]
>>> [i[0] for i in sorted(enumerate(myList), key=lambda x:x[1])]
[0, 1, 2, 4, 3]

enumerate(myList) vous donne une liste contenant des tuples de (index, valeur):

[(0, 1), (1, 2), (2, 3), (3, 100), (4, 5)]

Vous triez la liste en la passant à sortedet en spécifiant une fonction pour extraire la clé de tri (le deuxième élément de chaque tuple; c'est la lambdaraison d'être. Enfin, l'index d'origine de chaque élément trié est extrait à l'aide de la [i[0] for i in ...]compréhension de la liste.

Roman Bodnarchuk
la source
7
vous pouvez utiliser à la itemgetter(1)place de la fonction lambda
John La Rooy
4
@gnibbler fait référence à la itemgetterfonction du operatormodule, FYI. Il faut from operator import itemgetterdonc l'utiliser.
Lauritz V. Thaulow
1
vous pouvez obtenir la liste triée et les indices en utilisant zip:sorted_items, sorted_inds = zip(*sorted([(i,e) for i,e in enumerate(my_list)], key=itemgetter(1)))
Charles L.
@RomanBodnarchuk cela ne fonctionne pas, x = [3,1,2]; numpy.argsort(x)donne [1,2,0].
shahar_m
24

Les réponses enumeratesont agréables, mais personnellement, je n'aime pas le lambda utilisé pour trier par valeur. Ce qui suit inverse simplement l'index et la valeur et trie cela. Il va donc d'abord trier par valeur, puis par index.

sorted((e,i) for i,e in enumerate(myList))
Ant6n
la source
11

Réponse mise à jour avec enumerateet itemgetter:

sorted(enumerate(a), key=lambda x: x[1])
# [(0, 1), (1, 2), (2, 3), (4, 5), (3, 100)]

Compressez les listes ensemble: le premier élément du tuple sera l'index, le second est la valeur (puis triez-le en utilisant la deuxième valeur du tuple x[1] , x est le tuple)

Ou en utilisant itemgetterdepuis le operatormodule`:

from operator import itemgetter
sorted(enumerate(a), key=itemgetter(1))
Mat
la source
1
énumérer semble plus approprié que zip dans ce cas
njzk2
10

J'ai fait une vérification rapide des performances avec perfplot (un de mes projets) et j'ai trouvé qu'il était difficile de recommander autre chose que numpy (notez l'échelle logarithmique):

entrez la description de l'image ici


Code pour reproduire l'intrigue:

import perfplot
import numpy


def sorted_enumerate(seq):
    return [i for (v, i) in sorted((v, i) for (i, v) in enumerate(seq))]


def sorted_enumerate_key(seq):
    return [x for x, y in sorted(enumerate(seq), key=lambda x: x[1])]


def sorted_range(seq):
    return sorted(range(len(seq)), key=seq.__getitem__)


def numpy_argsort(x):
    return numpy.argsort(x)


perfplot.save(
    "argsort.png",
    setup=lambda n: numpy.random.rand(n),
    kernels=[sorted_enumerate, sorted_enumerate_key, sorted_range, numpy_argsort],
    n_range=[2 ** k for k in range(15)],
    xlabel="len(x)",
)
Nico Schlömer
la source
6

Si vous ne souhaitez pas utiliser numpy,

sorted(range(len(seq)), key=seq.__getitem__)

est le plus rapide, comme démontré ici .

mab
la source
5

Essentiellement, vous devez faire une argsort, quelle implémentation dont vous avez besoin dépend si vous voulez utiliser des bibliothèques externes (par exemple NumPy) ou si vous voulez rester pure-Python sans dépendances.

La question que vous devez vous poser est la suivante: voulez-vous

  • indices qui trieraient le tableau / la liste
  • indices que les éléments auraient dans le tableau / liste trié

Malheureusement, l'exemple de la question ne précise pas ce qui est souhaité car les deux donneront le même résultat:

>>> arr = np.array([1, 2, 3, 100, 5])

>>> np.argsort(np.argsort(arr))
array([0, 1, 2, 4, 3], dtype=int64)

>>> np.argsort(arr)
array([0, 1, 2, 4, 3], dtype=int64)

Choisir le argsort implémentation

Si vous avez NumPy à votre disposition, vous pouvez simplement utiliser la fonction numpy.argsortou la méthode numpy.ndarray.argsort.

Une implémentation sans NumPy a déjà été mentionnée dans certaines autres réponses, je vais donc récapituler la solution la plus rapide en fonction de la réponse de référence ici

def argsort(l):
    return sorted(range(len(l)), key=l.__getitem__)

Obtenir les indices qui trieraient le tableau / la liste

Pour obtenir les indices qui trieraient le tableau / la liste, vous pouvez simplement appeler argsortle tableau ou la liste. J'utilise les versions de NumPy ici mais l'implémentation Python devrait donner les mêmes résultats

>>> arr = np.array([3, 1, 2, 4])
>>> np.argsort(arr)
array([1, 2, 0, 3], dtype=int64)

Le résultat contient les indices nécessaires pour obtenir le tableau trié.

Puisque le tableau trié serait [1, 2, 3, 4]le tableau argsorted contient les indices de ces éléments dans l'original.

  • La plus petite valeur est 1et elle est à l'index 1dans l'original, donc le premier élément du résultat est1 .
  • Le 2est à l'index 2dans l'original donc le deuxième élément du résultat est 2.
  • Le 3est à l'index 0dans l'original, donc le troisième élément du résultat est 0.
  • La plus grande valeur 4et elle est à l'index 3dans l'original, donc le dernier élément du résultat est 3.

Obtention des indices que les éléments auraient dans le tableau / liste trié

Dans ce cas, vous devrez postuler argsort deux fois :

>>> arr = np.array([3, 1, 2, 4])
>>> np.argsort(np.argsort(arr))
array([2, 0, 1, 3], dtype=int64)

Dans ce cas :

  • le premier élément de l'original est 3, qui est la troisième plus grande valeur de sorte qu'il aurait un index 2dans le tableau / liste trié de sorte que le premier élément est2 .
  • le deuxième élément de l'original est 1, qui est la plus petite valeur pour qu'il ait un index 0dans le tableau / liste trié, de sorte que le deuxième élément l'est 0.
  • le troisième élément de l'original est 2, qui est la deuxième plus petite valeur, de sorte qu'il aurait un index 1dans le tableau / liste trié, de sorte que le troisième élément l'est 1.
  • le quatrième élément de l'original est 4la valeur la plus élevée, il aurait donc un index 3dans le tableau / la liste trié, de sorte que le dernier élément l'est 3.
MSeifert
la source
4

Les autres réponses sont FAUX.

Courir argsortune fois n'est pas la solution. Par exemple, le code suivant:

import numpy as np
x = [3,1,2]
np.argsort(x)

des rendements array([1, 2, 0], dtype=int64)qui ne sont pas ce que nous voulons.

La réponse devrait être d'exécuter argsortdeux fois:

import numpy as np
x = [3,1,2]
np.argsort(np.argsort(x))

donne array([2, 0, 1], dtype=int64)comme prévu.

shahar_m
la source
Votre revendication fait x[2](3) l'élément le plus petit et x[1](1) l'élément le plus grand (puisque le tri des entiers les ordonne de la plus petite valeur à la plus grande valeur). En outre, avec l'exemple des OP, un seul np.argsort([1, 2, 3, 100, 5])rendement array([0, 1, 2, 4, 3]), qui semble être les indices souhaités par l'OP.
0 0
1
@ 0 0 votre exemple est un cas particulier. Si nous courons, arr = [1,2,3,100, 5, 9] res = np.argsort(arr) print(res)nous obtenons [0 1 2 4 5 3]ce qui est faux.
shahar_m
Je ne sais pas ce qui ne va pas: les arr[res]rendements array([ 1, 2, 3, 5, 9, 100]), ce qui semble être parfaitement bien, car ce tableau résultant est dans l'ordre (croissant).
0 0
@ 0 0 pour arr=[1,2,3,100, 5, 9], je m'attends à ce que la sortie soit inds=[0,1,2,5,3,4], parce que c'est l'ordre dans lequel vous ordonnerez les éléments (de plus en plus) - 1 est à la place des 0, 2 à la 1ère place, ...., 5 sur la 3e place et 9 à la 4e place. Afin d'obtenir cette sortie ( inds), je dois exécuter argsortdeux fois, comme je l'ai mentionné.
shahar_m
Ces indices sont donc une sorte de classement des éléments du tableau (0ème place, 1ère place, etc.). Étant donné la mention de l'OP à MATLABsort , je pense que l'OP veut l'autre fonctionnalité, tout comme np.argsortest normalement utilisée (où l'on peut utiliser arr[np.argsort[arr]]pour obtenir le tableau trié, comme dans le dernier exemple MATLAB). Votre réponse s'applique plutôt à ce cas / question .
0 0
0

Importer numpy comme np

POUR INDEX

S=[11,2,44,55,66,0,10,3,33]

r=np.argsort(S)

[output]=array([5, 1, 7, 6, 0, 8, 2, 3, 4])

argsort Renvoie les indices de S dans l'ordre trié

POUR LA VALEUR

np.sort(S)

[output]=array([ 0,  2,  3, 10, 11, 33, 44, 55, 66])
negi
la source
0

Nous allons créer un autre tableau d'index de 0 à n-1 Puis compresser ceci dans le tableau d'origine, puis le trier sur la base des valeurs d'origine

ar = [1,2,3,4,5]
new_ar = list(zip(ar,[i for i in range(len(ar))]))
new_ar.sort()

"

Jai dewani
la source