Замена индексов значениями в списке Python?

(Нет, это не домашнее задание и не конкурс, хотя и может выглядеть так.)

У меня есть список A в Python, который содержит числа range(0, len(A)). Номера не по порядку, но все они есть в списке.

Я ищу простой способ создать список B, в котором индексы и значения поменялись местами, то есть список, который для каждого целого числа n содержит позицию n в A.

Пример:

A = [0, 4, 1, 3, 2]
B = [0, 2, 4, 3, 1]

Я могу поместить код для генерации B либо отдельно, либо в коде, который генерирует A. В частности, вот как я генерирую A:

A = [value(i) for i in range(length)]

Как лучше всего это сделать?


python-3.x python list indices swap
person PurkkaKoodari    schedule 09.02.2015    source источник

Ответы (4)


arrow_upward
4
arrow_downward

Используя функцию enumerate() для украшения каждого значения их индексом, сортируя с помощью < href="https://docs.python.org/2/library/functions.html#sorted" rel="nofollow">sorted() для значений, а затем снова отменить декорирование, чтобы извлечь индексы в порядок значений:

[i for i, v in sorted(enumerate(A), key=lambda iv: iv[1])]

Это имеет временную сложность O(NlogN), потому что мы использовали сортировку.

Демо:

>>> A = [0, 4, 1, 3, 2]
>>> [i for i, v in sorted(enumerate(A), key=lambda iv: iv[1])]
[0, 2, 4, 3, 1]

Мы также можем использовать предварительно созданный список для назначения индексов для решения O (N):

B = [0] * len(A)
for i, v in enumerate(A):
    B[v] = i

Демо:

>>> B = [0] * len(A)
>>> for i, v in enumerate(A):
...     B[v] = i
... 
>>> B
[0, 2, 4, 3, 1]

Это, вероятно, лучший вариант, если временная сложность имеет большое значение; для N = 100 подход к сортировке займет около 461 шага по сравнению со 100 для подхода с предварительно созданным списком.

person Martijn Pieters    schedule 09.02.2015
comment
Я не вижу причин использовать решение sorted - person jamylak; 10.02.2015

arrow_upward
6
arrow_downward

Как насчет назначения предварительно выделенному B:

>>> A = [0, 4, 1, 3, 2]
>>> B = [0] * len(A)
>>> for k, v in enumerate(A): B[v] = k
>>> B
[0, 2, 4, 3, 1]

Это будет O(n).

person bereal    schedule 09.02.2015

arrow_upward
0
arrow_downward 

A = [0, 4, 1, 3, 2]

B = [None]*len(A)

for i, x in enumerate(A):
    B[x] = i

print B

разрешение: [0, 2, 4, 3, 1]

person Andrey    schedule 09.02.2015
comment
обертывание [None]*len(A) в list(...) ничего не дает - person jamylak; 10.02.2015

arrow_upward
0
arrow_downward

Это очень наивно;

[ [ x[0] for x in enumerate(A) if x[1] == i][0] for i in range(len(A)) ]

Это работает идеально,

[A.index(A.index(i)) for i in A]

Это лучше;

[A.index(i[0]) for i in enumerate(A)]

Этот превосходит другой;

[A.index(i) for i in range(len(A))]

Доказательство;

import random as r
for l in [ r.sample(range(5),5) for n in range(5) ]:
    A = l
    B = [A.index(A.index(i)) for i in A]
    print "A is : ", A
    print "B is : ", B
    print "Are B's elements indices of A? : ", A == [B.index(B.index(i)) for i in B]
    print
person Nizam Mohamed    schedule 09.02.2015
comment
Это чрезвычайно неэффективно. Это квадратичный подход O(N^2); если вы сделаете это со списком из 100 элементов, вы сделаете 100 000 сравнений. Для списка с 1 000 000 элементов это будет 1 000 000 000 000 сравнений. - person Martijn Pieters; 09.02.2015
comment
@martijn-pieters спасибо за комментарии. Я обновил свой пост, есть еще комментарии? - person Nizam Mohamed; 10.02.2015
comment
list.index() - это все еще O(N) шаг. Вам кажется, что это всего лишь одна команда, но Python все равно должен просмотреть список, чтобы найти первое совпадение и вернуть индекс. - person Martijn Pieters; 10.02.2015