Jak uzyskać indeksy posortowanej tablicy w Pythonie

Mam listę numeryczną:

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

Teraz posortuję tę listę, aby uzyskać [1, 2, 3, 5, 100]. To, czego chcę, to indeksy elementów z oryginalnej listy w posortowanej kolejności, tj. [0, 1, 2, 4, 3] --- ala funkcja sortująca MATLAB, która zwraca zarówno wartości, jak i indeksy.

Jeśli używasz numpy, masz dostępną funkcję argsort ():

>>> import numpy
>>> numpy.argsort(myList)
array([0, 1, 2, 4, 3])

http://docs.scipy.org/doc/numpy/reference/generated/numpy.argsort.html

Zwraca argumenty, które posortowałyby tablicę lub listę.

Coś jak następne:

>>> 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) daje listę zawierającą krotki (indeks, wartość):

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

Sortujesz listę, przekazując ją sortedi określając funkcję do wyodrębnienia klucza sortowania (drugi element każdej krotki; po to lambdajest. Na koniec oryginalny indeks każdego posortowanego elementu jest wyodrębniany przy użyciu [i[0] for i in ...]listy.

myList = [1, 2, 3, 100, 5]    
sorted(range(len(myList)),key=myList.__getitem__)

[0, 1, 2, 4, 3]

Odpowiedzi enumeratesą miłe, ale osobiście nie lubię lambda używanego do sortowania według wartości. Poniższe odwraca indeks i wartość i sortuje je. Więc najpierw posortuje według wartości, a następnie według indeksu.

sorted((e,i) for i,e in enumerate(myList))

Zaktualizowana odpowiedź za pomocą enumeratei itemgetter:

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

Spakuj listy razem: pierwszy element w krotce będzie indeksem, drugi to wartość (następnie posortuj go przy użyciu drugiej wartości krotki x[1], x to krotka)

Lub używając itemgetterz operatormodułu`:

from operator import itemgetter
sorted(enumerate(a), key=itemgetter(1))

Zrobiłem szybką kontrolę wydajności tych przy pomocy perfplot (mój projekt) i stwierdziłem, że trudno jest polecić cokolwiek innego niż numpy (zwróć uwagę na skalę logów):

Kod do odtworzenia fabuły:

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)",
)

Jeśli nie chcesz używać numpy,

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

jest najszybszy, jak pokazano tutaj .

Zasadniczo musisz zrobić argsort , to jakiej implementacji potrzebujesz, jeśli chcesz korzystać z zewnętrznych bibliotek (np. NumPy) lub jeśli chcesz pozostać czystym Pythonem bez zależności.

Pytanie, które musisz sobie zadać, brzmi: czy chcesz

• indeksy, które posortowałyby tablicę / listę
• indeksy, które elementy miałyby w posortowanej tablicy / liście

Niestety przykład w pytaniu nie wyjaśnia, co jest pożądane, ponieważ oba dają ten sam rezultat:

>>> 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)

Wybierając argsort implementacji

Jeśli masz do dyspozycji NumPy, możesz po prostu użyć funkcji numpy.argsortlub metody numpy.ndarray.argsort.

Wdrożenie bez NumPy zostało już wspomniane w kilku innych odpowiedziach, więc po prostu podsumuję najszybsze rozwiązanie zgodnie z odpowiedzią testu porównawczego tutaj

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

Uzyskiwanie wskaźników, które posortowałyby tablicę / listę

Aby uzyskać indeksy, które posortowałyby tablicę / listę, możesz po prostu wywołać argsorttablicę lub listę. Używam tutaj wersji NumPy, ale implementacja Pythona powinna dawać takie same wyniki

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

Wynik zawiera indeksy potrzebne do uzyskania posortowanej tablicy.

Ponieważ posortowana tablica byłaby tablicą [1, 2, 3, 4]argsortowaną, zawiera indeksy tych elementów w oryginale.

• Najmniejszą wartością jest 1i jest w indeksie 1w oryginale, więc pierwszym elementem wyniku jest1 .
• 2Jest indeksem 2w oryginale więc drugi element wyniku jest 2.
• 3Jest indeksem 0w oryginale więc trzeci element wyniku jest 0.
• Największa wartość 4i jest w indeksie 3w oryginale, więc ostatnim elementem wyniku jest 3.

Uzyskiwanie indeksów, które elementy miałyby w posortowanej tablicy / liście

W takim przypadku należy złożyć argsort dwukrotnie wniosek :

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

W tym przypadku :

• pierwszym elementem oryginału jest 3, co jest trzecią co do wielkości wartością, więc miałby indeks 2w posortowanej tablicy / liście, więc pierwszym elementem jest2 .
• drugim elementem oryginału jest 1, która jest najmniejszą wartością, więc miałby indeks 0w posortowanej tablicy / liście, więc drugim elementem jest 0.
• trzecim elementem oryginału jest 2, co jest drugą najmniejszą wartością, więc miałby indeks 1w posortowanej tablicy / liście, więc trzeci element to 1.
• czwartym elementem oryginału jest 4największa wartość, więc miałby indeks 3w posortowanej tablicy / liście, więc ostatnim elementem jest 3.

Inne odpowiedzi są NIEPRAWIDŁOWE.

Uruchamianie argsortraz nie jest rozwiązaniem. Na przykład następujący kod:

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

plony, array([1, 2, 0], dtype=int64)których nie chcemy.

Odpowiedź powinna brzmieć argsortdwa razy:

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

daje array([2, 0, 1], dtype=int64)zgodnie z oczekiwaniami.

Zaimportuj numpy jako np

DLA INDEKSU

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 Zwraca indeksy S w posortowanej kolejności

DLA WARTOŚCI

np.sort(S)

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

Utworzymy kolejną tablicę indeksów od 0 do n-1, następnie spakujemy ją do oryginalnej tablicy, a następnie posortujemy na podstawie oryginalnych wartości

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

`