почему обмен не происходит, когда индексы равны 0 и 1? - PullRequest
Новая
       33

почему обмен не происходит, когда индексы равны 0 и 1?

1 голос
/ 26 апреля 2019

У меня есть неупорядоченный массив, состоящий из последовательных целых чисел [1, 2, 3, ..., n] без каких-либо дубликатов. Разрешено менять любые два элемента. Мне нужно найти минимальное количество перестановок, необходимое для сортировки массива в порядке возрастания.

Начиная с первого элемента списка, я пытаюсь расположить их в правильном положении (например, если первый элемент равен 7, он должен быть на 6-й позиции списка). Чтобы перейти по одному в списке, я делаю копию и делаю обмен во втором списке. 

a = [4,3,1,2]
b = a[:]
swap = 0
for p in a:
  if (p!= b[p-1]):
    b[p-1], b[b.index(p)] =  b[b.index(p)], b[p-1]
    swap+=1
print(swap)

этот код работает, за исключением случая, когда мне нужно поменять местами два элемента в списке, позиция которых равна 0 или 1, в данном случае. что я не понимаю почему ?? так как я не превышаю лимит.

Может кто-нибудь объяснить мне, почему это происходит?

Например, если я напечатаю p, два индекса, где происходит свопинг, обновленный список b и обновленное количество свопов: 

p = 4
idx1= 3 idx2= 0
b= [2, 3, 1, 4]
swap = 1
p = 3
idx1= 2 idx2= 1
b= [2, 1, 3, 4]
swap = 2
p = 1
idx1= 0 idx2= 1
b= [2, 1, 3, 4]
swap = 3
p = 2
idx1= 1 idx2= 0
b= [1, 2, 3, 4]
swap = 4

В этом случае вы можете видеть, что для p = 1, когда индексы равны 0 и 1, обмен не происходит.

Я изменил порядок b [p-1], b [b.index (p)], и у меня больше нет той же проблемы, но я не понимаю причину.

1 Ответ

0 голосов
/ 04 мая 2019

Я сталкивался с той же проблемой раньше и застрял на некоторое время.Причиной этого является порядок множественного присвоения. 

b[p-1], b[b.index(p)] =  b[b.index(p)], b[p-1]

На самом деле множественное присвоение не является точным назначением одновременно.За этим следует упаковать и распаковать механизм.поэтому сначала он изменит b[p-1], а b.index(p) в b[b.index(p)] найдет новый индекс, равный p-1, если регистр p=1 idx1=0 idx2=1

, если вы измените порядок назначения, он будет работатьхорошо. 

b[b.index(p)], b[p - 1] = b[p - 1], b[b.index(p)]

или сначала рассчитать idx: 

idx1, idx2 = p - 1, b.index(p)
b[idx1], b[idx2] = b[idx2], b[idx1]

Я рекомендую вторую версию, потому что первая версия будет делать index дважды.стоит вдвое дороже, чем вторая версия.

Вы можете обратиться к моему связанному вопросу здесь: Кстати, я думаю, что механизм множественного назначения в Python

Ваш алгоритм здесь неэффективен, чтобы уменьшить время подкачки, но используйте операцию O (n) index, а также скопируйте массив здесь.Я думаю, что вы можете использовать ту же идею, просто поменяйте местами в массиве orignal.

...