Неожиданное поведение кода python при решении задачи хакерского ранга под названием Lily's Homework.

Question

Ссылка на задачу: https://www.hackerrank.com/challenges/lilys-homework/forum

Резюме: Мы должны найти минимальный номер. свопов, необходимых для преобразования массива в отсортированный массив. Его можно отсортировать по возрастанию или убыванию. Итак, вот массив, который я хочу отсортировать:

arr = [3, 4, 2, 5, 1]

Мы сортируем его в порядке возрастания, нам нужно 4 обмена и 2 обмена в порядке убывания.

По убыванию: -Swap 5 и 3, а затем поменять местами 3 и 2

Теперь я написал код python для решения этого тестового примера. Вот код:

arr = [3, 4, 2, 5, 1]
arr2 = arr[:]

count = 0; count2 = 0; n = len(arr)

registry = {}
for i in range(n):
    registry[arr[i]] = i

sorted_arr = sorted(arr)


#######################first for loop starts#########################
#find no. of swap required when we sort arr is in ascending order.
for i in range(n-1):

    if arr[i] != sorted_arr[i]:        
        index = registry[sorted_arr[i]]

        registry[sorted_arr[i]],registry[arr[i]]= i, index
        temp = arr[i]
        arr[i],arr[index]=sorted_arr[i],temp

        count = count + 1    
###################first for loop ends#######################

# re-initalising registry and sorted_arr for descending problem.
registry = {}
for i in range(n):
    registry[arr2[i]] = i

sorted_arr = sorted(arr2)
sorted_arr.reverse()

print(arr2)             #unsorted array
print(registry)         #dictionary which stores the index of the array arr2
print(sorted_arr)       #array in descending order.


#find no. of swap required when array is in descending order.
for i in range(n-1):
    print('For iteration i = %i' %i)
    if arr2[i] != sorted_arr[i]:
        print('\tTrue')
        index = registry[sorted_arr[i]]

        registry[sorted_arr[i]],registry[arr[i]]= i, index
        temp = arr2[i]
        arr2[i],arr2[index]=sorted_arr[i],temp

        print('\t '+ str(arr2))
        count2 = count2 + 1

    else:
        print('\tfalse')
        print('\t '+ str(arr2))



print('######Result######')
print(arr)
print(count)

print(arr2)
print(count2)

Вот проблема: когда я запускаю код, второй для l oop, т.е. для l oop по убыванию дает неправильное значение count, равное 3. Но , когда я комментирую первый для l oop, то есть для l oop для возрастания он дает правильное значение count, которое равно 2.

Я хочу знать, почему для l oop 2 изменяется вывод когда присутствует l oop 1.

Вывод, который я получаю, когда l oop 1 НЕ комментируется.

arr2: [3, 4, 2, 5, 1]
Registry: {3: 0, 4: 1, 2: 2, 5: 3, 1: 4}
sorted_arr: [5, 4, 3, 2, 1]
For iteration i = 0
    True
     [5, 4, 2, 3, 1]
For iteration i = 1
    false
     [5, 4, 2, 3, 1]
For iteration i = 2
    True
     [2, 4, 3, 3, 1]
For iteration i = 3
    True
     [2, 4, 3, 2, 1]
######Result######
[1, 2, 3, 4, 5]
4
[2, 4, 3, 2, 1]
3

Answer 1

Ошибка находится во втором l oop, где у вас:

registry[sorted_arr[i]],registry[arr[i]]= i, index

Это должно быть:

registry[sorted_arr[i]],registry[arr2[i]]= i, index

Как правило, работать с такие переменные arr и arr2. Вместо этого создайте две функции и передайте arr в качестве аргумента вызова функции. Затем функция должна сделать локальную копию этого массива ([:]) перед его изменением. Все остальные переменные должны быть локальными по отношению к функции. Таким образом, два алгоритма используют свою собственную область видимости переменных, и отсутствует риск случайной «утечки» неправильной переменной в другой алгоритм.