i wrote this algorithm that returns the shortest sequence using operations to sort a list of numbers.
is sorted by always reversing the order of the first n elements of the list and removing the first element from the list.
def wenden(arr, n):
#dreht die Ersten n elemente um
i = 0
while i < n // 2:
arr[i], arr[n - i-1] = arr[n - i-1], arr[i]
i += 1
arr.pop(0)
return arr
def ist_Sortirt(arr):
for i in range(len(arr) - 1):
if arr[i] > arr[i+1]:
return False
return True
def best_sort(arr):
flips = []
if not ist_Sortirt(arr):
for i in range(1, len(arr)-1):
sort_lis = wenden(arr, i + 1)
flipi = [i+1]
flipi.append(best_sort(sort_lis))
flips.append(flipi)
ret = 0
for i in range(1, len(flips)-1):
if len(flips[i]) < len(flips[ret]):
ret = i
return flips[ret]
else:
return []
I have tested the script with different input lists, a list with the phrases should be output, but I always get a list index out of range error at return flips[ret] in best_sort() if the input is longer than 3 numbers
input: [2,1,3,6]
Traceback (most recent call last):
File "D:\programming\Aufgabe3a.py", line 69, in <module>
print(best_sort(pfannkuchen))
File "D:\programming\Aufgabe3a.py", line 47, in best_sort
flipi.append(best_sort(sort_lis))
File "D:\programming\Aufgabe3a.py", line 53, in best_sort
return flips[ret]
IndexError: list index out of range
>Solution :
I fixed the issue.
Try it now.
def wenden(arr, n):
i = 0
while i < n // 2:
arr[i], arr[n - i - 1] = arr[n - i - 1], arr[i]
i += 1
arr.pop(0)
return arr
def ist_Sortirt(arr):
for i in range(len(arr) - 1):
if arr[i] > arr[i + 1]:
return False
return True
def best_sort(arr):
if len(arr) <= 1:
return []
flips = []
if not ist_Sortirt(arr):
for i in range(len(arr)):
sort_lis = copy.deepcopy(arr)
sort_lis = wenden(sort_lis, i + 1)
flipi = [i + 1]
flipi.append(best_sort(sort_lis))
flips.append(flipi)
ret = 0
for i in range(1, len(flips)):
if len(flips[i]) < len(flips[ret]):
ret = i
return flips[ret]
else:
return []