Python: 1668293 1579182 1,5244,04 1450842 1093195 ruchów
Główną metodą jest main_to_help_bestprzenoszenie wybranych elementów ze stosu głównego na stos pomocniczy. Ma flagę, everythingktóra określa, czy chcemy przenieść wszystko do określonego destination, czy też chcemy zachować tylko największydestination podczas gdy reszta w drugim pomocniku.
Załóżmy, że przechodzimy do dstużywania pomocnikahelper , funkcję można z grubsza opisać następująco:
- Znajdź pozycje największych elementów
- Przenieś wszystko na najwyżej umieszczony element
helper rekurencyjnie
- Przenieś największy element do
dst
- Wciśnij z powrotem
helperdo głównego
- Powtarzaj 2-4, aż pojawią się największe elementy
dst
- za. Jeśli
everythingjest ustawiony, rekurencyjnie przenieś elementy w main do dst
b. W przeciwnym razie rekurencyjnie przenieś elementy w głównym dohelper
Algorytm sortowania głównego ( sort2w moim kodzie) wywoła następnie za main_to_help_bestpomocą everythingset to False, a następnie przeniesie największy element z powrotem do main, a następnie przeniesie wszystko z pomocnika z powrotem do main, utrzymując go posortowane.
Więcej objaśnień zawartych w komentarzach w kodzie.
Zasadniczo zastosowałem następujące zasady:
- Zachowaj jednego pomocnika, aby zawierał maksymalną liczbę elementów
- Zachowaj innego pomocnika, aby zawierał inne elementy
- Nie rób niepotrzebnych ruchów tak często, jak to możliwe
Zasada 3 jest realizowana przez nie liczenie ruchu, jeśli źródłem jest poprzedni cel (tj. Właśnie przenieśliśmy główny do help1, a następnie chcemy przejść z help1 do help2), a ponadto zmniejszamy liczbę ruchów o 1, jeśli przesuwają go z powrotem do pierwotnej pozycji (tj. główny do help1, a następnie help1 do main). Ponadto, jeśli wszystkie poprzednie nruchy przenoszą tę samą liczbę całkowitą, możemy faktycznie zmienić ich kolejność n. Wykorzystujemy to również w celu dalszego zmniejszenia liczby ruchów.
Jest to ważne, ponieważ znamy wszystkie elementy na głównym stosie, więc można to interpretować jako widzenie w przyszłości, że cofniemy element z powrotem, nie powinniśmy wykonywać tego ruchu.
Przykładowy przebieg (stosy są wyświetlane od dołu do góry - więc pierwszy element jest na dole):
Długość 1
Przenosi: 0
Zadania: 6
Maks .: 0 ([1])
Średnia: 0,000
Długość 2
Przenosi: 60
Zadania: 36
Maks .: 4 ([1, 2])
Średnia: 1,667
Długość 3
Przenosi: 1030
Zadania: 216
Maks .: 9 ([2, 3, 1])
Średnia: 4,769
Długość 4
Przenosi: 11765
Zadania: 1296
Maks .: 19 ([3, 4, 2, 1])
Średnia: 9,078
Długość 5
Przenosi: 112325
Zadania: 7776
Maks .: 33 ([4, 5, 3, 2, 1])
Średnia: 14,445
Długość 6
Przenosi: 968015
Zadania: 46656
Maks .: 51 ([5, 6, 4, 3, 2, 1])
Średnia: 20,748
--------------
Ogólny
Przenosi: 1093195
Zadania: 55986
Średnia: 19,526
Widzimy, że najgorszym przypadkiem jest umieszczenie największego elementu na drugim dnie, podczas gdy pozostałe są sortowane. W najgorszym przypadku możemy zobaczyć, że algorytmem jest O (n ^ 2).
Liczba ruchów jest oczywiście minimalna n=1i n=2jak widać z wyniku, i uważam, że jest to również minimalna wartość dla większych wartości n, chociaż nie mogę tego udowodnić.
Więcej wyjaśnień znajduje się w kodzie.
from itertools import product
DEBUG = False
def sort_better(main, help1, help2):
# Offset denotes the bottom-most position which is incorrect
offset = len(main)
ref = list(reversed(sorted(main)))
for idx, ref_el, real_el in zip(range(len(main)), ref, main):
if ref_el != real_el:
offset = idx
break
num_moves = 0
# Move the largest to help1, the rest to help2
num_moves += main_to_help_best(main, help1, help2, offset, False)
# Move the largest back to main
num_moves += push_to_main(help1, main)
# Move everything (sorted in help2) back to main, keep it sorted
num_moves += move_to_main(help2, main, help1)
return num_moves
def main_to_help_best(main, dst, helper, offset, everything=True):
"""
Moves everything to dst if everything is true,
otherwise move only the largest to dst, and the rest to helper
"""
if offset >= len(main):
return 0
max_el = -10**10
max_idx = -1
# Find the location of the top-most largest element
for idx, el in enumerate(main[offset:]):
if el >= max_el:
max_idx = idx+offset
max_el = el
num_moves = 0
# Loop from that position downwards
for max_idx in range(max_idx, offset-1, -1):
# Processing only at positions with largest element
if main[max_idx] < max_el:
continue
# The number of elements above this largest element
top_count = len(main)-max_idx-1
# Move everything above this largest element to helper
num_moves += main_to_help_best(main, helper, dst, max_idx+1)
# Move the largest to dst
num_moves += move(main, dst)
# Move back the top elements
num_moves += push_to_main(helper, main, top_count)
# Here, the largest elements are in dst, the rest are in main, not sorted
if everything:
# Move everything to dst on top of the largest
num_moves += main_to_help_best(main, dst, helper, offset)
else:
# Move everything to helper, not with the largest
num_moves += main_to_help_best(main, helper, dst, offset)
return num_moves
def verify(lst, moves):
if len(moves) == 1:
return True
moves[1][0][:] = lst
for src, dst, el in moves[1:]:
move(src, dst)
return True
def equal(*args):
return len(set(str(arg.__init__) for arg in args))==1
def move(src, dst):
dst.append(src.pop())
el = dst[-1]
if not equal(dst, sort.lst) and list(reversed(sorted(dst))) != dst:
raise Exception('HELPER NOT SORTED: %s, %s' % (src, dst))
cur_len = len(move.history)
check_idx = -1
matched = False
prev_src, prev_dst, prev_el = move.history[check_idx]
# As long as the element is the same as previous elements,
# we can reorder the moves
while el == prev_el:
if equal(src, prev_dst) and equal(dst, prev_src):
del(move.history[check_idx])
matched = True
break
elif equal(src, prev_dst):
move.history[check_idx][1] = dst
matched = True
break
elif equal(dst, prev_src):
move.history[check_idx][0] = src
matched = True
break
check_idx -= 1
prev_src, prev_dst, prev_el = move.history[check_idx]
if not matched:
move.history.append([src, dst, el])
return len(move.history)-cur_len
def push_to_main(src, main, amount=-1):
num_moves = 0
if amount == -1:
amount = len(src)
if amount == 0:
return 0
for i in range(amount):
num_moves += move(src, main)
return num_moves
def push_to_help(main, dst, amount=-1):
num_moves = 0
if amount == -1:
amount = len(main)
if amount == 0:
return 0
for i in range(amount):
num_moves += move(main, dst)
return num_moves
def help_to_help(src, dst, main, amount=-1):
num_moves = 0
if amount == -1:
amount = len(src)
if amount == 0:
return 0
# Count the number of largest elements
src_len = len(src)
base_el = src[src_len-amount]
base_idx = src_len-amount+1
while base_idx < src_len and base_el == src[base_idx]:
base_idx += 1
# Move elements which are not the largest to main
num_moves += push_to_main(src, main, src_len-base_idx)
# Move the largest to destination
num_moves += push_to_help(src, dst, base_idx+amount-src_len)
# Move back from main
num_moves += push_to_help(main, dst, src_len-base_idx)
return num_moves
def move_to_main(src, main, helper, amount=-1):
num_moves = 0
if amount == -1:
amount = len(src)
if amount == 0:
return 0
# Count the number of largest elements
src_len = len(src)
base_el = src[src_len-amount]
base_idx = src_len-amount+1
while base_idx < src_len and base_el == src[base_idx]:
base_idx += 1
# Move elements which are not the largest to helper
num_moves += help_to_help(src, helper, main, src_len-base_idx)
# Move the largest to main
num_moves += push_to_main(src, main, base_idx+amount-src_len)
# Repeat for the rest of the elements now in the other helper
num_moves += move_to_main(helper, main, src, src_len-base_idx)
return num_moves
def main():
num_tasks = 0
num_moves = 0
for n in range(1, 7):
start_moves = num_moves
start_tasks = num_tasks
max_move = -1
max_main = []
for lst in map(list,product(*[[1,2,3,4,5,6]]*n)):
num_tasks += 1
if DEBUG: print lst, [], []
sort.lst = lst
cur_lst = lst[:]
move.history = [(None, None, None)]
help1 = []
help2 = []
moves = sort_better(lst, help1, help2)
if moves > max_move:
max_move = moves
max_main = cur_lst
num_moves += moves
if DEBUG: print '%s, %s, %s (moves: %d)' % (cur_lst, [], [], moves)
if list(reversed(sorted(lst))) != lst:
print 'NOT SORTED: %s' % lst
return
if DEBUG: print
# Verify that the modified list of moves is still valid
verify(cur_lst, move.history)
end_moves = num_moves - start_moves
end_tasks = num_tasks - start_tasks
print 'Length %d\nMoves: %d\nTasks: %d\nMax: %d (%s)\nAverage: %.3f\n' % (n, end_moves, end_tasks, max_move, max_main, 1.0*end_moves/end_tasks)
print '--------------'
print 'Overall\nMoves: %d\nTasks: %d\nAverage: %.3f' % (num_moves, num_tasks, 1.0*num_moves/num_tasks)
# Old sort method, which assumes we can only see the top of the stack
def sort(main, max_stack, a_stack):
height = len(main)
largest = -1
num_moves = 0
a_stack_second_el = 10**10
for i in range(height):
if len(main)==0:
break
el = main[-1]
if el > largest: # We found a new maximum element
if i < height-1: # Process only if it is not at the bottom of main stack
largest = el
if len(a_stack)>0 and a_stack[-1] < max_stack[-1] < a_stack_second_el:
a_stack_second_el = max_stack[-1]
# Move aux stack to max stack then reverse the role
num_moves += help_to_help(a_stack, max_stack, main)
max_stack, a_stack = a_stack, max_stack
if DEBUG: print 'Moved max_stack to a_stack: %s, %s, %s (moves: %d)' % (main, max_stack, a_stack, num_moves)
num_moves += move(main, max_stack)
if DEBUG: print 'Moved el to max_stack: %s, %s, %s (moves: %d)' % (main, max_stack, a_stack, num_moves)
elif el == largest:
# The maximum element is the same as in max stack, append
if i < height-1: # Only if the maximum element is not at the bottom
num_moves += move(main, max_stack)
elif len(a_stack)==0 or el <= a_stack[-1]:
# Current element is the same as in aux stack, append
if len(a_stack)>0 and el < a_stack[-1]:
a_stack_second_el = a_stack[-1]
num_moves += move(main, a_stack)
elif a_stack[-1] < el <= a_stack_second_el:
# Current element is larger, but smaller than the next largest element
# Step 1
# Move the smallest element(s) in aux stack into max stack
amount = 0
while len(a_stack)>0 and a_stack[-1] != a_stack_second_el:
num_moves += move(a_stack, max_stack)
amount += 1
# Step 2
# Move all elements in main stack that is between the smallest
# element in aux stack and current element
while len(main)>0 and max_stack[-1] <= main[-1] <= el:
if max_stack[-1] < main[-1] < a_stack_second_el:
a_stack_second_el = main[-1]
num_moves += move(main, a_stack)
el = a_stack[-1]
# Step 3
# Put the smallest element(s) back
for i in range(amount):
num_moves += move(max_stack, a_stack)
else: # Find a location in aux stack to put current element
# Step 1
# Move all elements into max stack as long as it will still
# fulfill the Hanoi condition on max stack, AND
# it should be greater than the smallest element in aux stack
# So that we won't duplicate work, because in Step 2 we want
# the main stack to contain the minimum element
while len(main)>0 and a_stack[-1] < main[-1] <= max_stack[-1]:
num_moves += move(main, max_stack)
# Step 2
# Pick the minimum between max stack and aux stack, move to main
# This will essentially sort (in reverse) the elements into main
# Don't move to main the element(s) found before Step 1, because
# we want to move them to aux stack
while True:
if len(a_stack)>0 and a_stack[-1] < max_stack[-1]:
num_moves += move(a_stack, main)
elif max_stack[-1] < el:
num_moves += move(max_stack, main)
else:
break
# Step 3
# Move all elements in main into aux stack, as long as it
# satisfies the Hanoi condition on aux stack
while max_stack[-1] == el:
num_moves += move(max_stack, a_stack)
while len(main)>0 and main[-1] <= a_stack[-1]:
if main[-1] < a_stack[-1] < a_stack_second_el:
a_stack_second_el = a_stack[-1]
num_moves += move(main, a_stack)
if DEBUG: print main, max_stack, a_stack
# Now max stack contains largest element(s), aux stack the rest
num_moves += push_to_main(max_stack, main)
num_moves += move_to_main(a_stack, main, max_stack)
return num_moves
if __name__ == '__main__':
main()