Lecture "Dynamic programming algorithms", exercise 2
essepuntato opened this issue · 8 comments
Write an algorithm for using the merge sort (introduced in the previous lecture) so as to use a dynamic programming approach in case the same list of books must be ordered twice or more times during the algorithm execution – see the informal example introduced in Section "Remembering solutions to sub-problems" of this lecture notes.
Accompany the implementation of the function with the appropriate test cases.
def test_merge_sort(input_list, expected):
result = merge_sort(input_list)
if result == expected:
return True
else:
return False
def merge_sort(input_list):
input_list_len = len(input_list)
if len(input_list) <= 1:
return input_list
else:
mid = input_list_len // 2
l = (merge_sort(input_list[0:mid]))
r = (merge_sort(input_list[mid:input_list_len]))
return merge(l,r)
def merge(l,r):
result = list()
while len(l) > 0 and len(r) > 0:
left_item = l[0]
right_item = r[0]
if left_item < right_item:
result.append(left_item)
l.remove(left_item)
else:
result.append(right_item)
r.remove(right_item)
result.extend(l)
result.extend(r)
return result
input_list = (["Coraline", "American Gods", "Neverwhere", "Neverwhere", "American Gods", "Coraline"])
print(test_merge_sort(["Coraline", "American Gods", "Neverwhere", "Neverwhere", "American Gods", "Coraline"],['American Gods', 'American Gods', 'Coraline', 'Coraline', 'Neverwhere', 'Neverwhere'])) #True
from merge import merge
# test for the algorithm
def test_merge_sort(books_list, expected, d=dict()):
result = merge_sort(books_list, d=dict())
if result == expected:
return True
else:
return False
def merge_sort(books_list, d=dict()):
books_list_len = len(books_list) # base case
if len(books_list)<= 1:
return books_list
else:
mid = books_list_len // 2 # divide step
left_books_list = books_list[0:mid]
right_books_list = books_list[mid:books_list_len]
# recursive step
left = merge_sort(books_list[0:mid])
right = merge_sort(books_list[mid:books_list_len])
# dictionary used as input in case the same list of books must be ordered more than one time
# dynamic programming approach
if left_books_list == right_books_list:
d[right] = left
return merge(left, right) # combine
print(test_merge_sort(["Coraline", "American Gods", "Neverwhere", "Neverwhere", "American Gods", "Coraline"], ["American Gods", "American Gods", "Coraline", "Coraline", "Neverwhere", "Neverwhere"], ({})))
print(test_merge_sort(["Heart of Darkness", "Wuthering Heights", "Twelfth Night", "Twelfth Night", "Wuthering Heights", "Heart of Darkness"], ["Heart of Darkness", "Heart of Darkness", "Twelfth Night", "Twelfth Night", "Wuthering Heights", "Wuthering Heights"], ({})))
# True
# True
Note:
This dynamic merge sort algorithm saves results for a partial list of an input list if the partial list itself was used as an input in the recursive part of the algorithm. For example, after having ordered [9, 6, 8, 7, 0], the result for the partial list [8, 7, 0] can be retrieved from the dictionary. However, the partial list [6, 8, 7] is not stored in the dictionary and has to be ordered itself. The difference is that the latter was never used as an input of the recursive merge_sort_dp(). Whereas the first partial list was used as an input.
+++ Dynamic Merge Sort with Test Cases +++
# Test Function
def test_merge_sort_dp(input_list, expected):
return expected == merge_sort_dp(input_list)
# Merge Algorithm
def merge_dp(left_list, right_list):
left = left_list.copy()
right = right_list.copy()
result = list()
while len(left) > 0 and len(right) > 0:
left_item = left[0]
right_item = right[0]
if left_item < right_item:
result.append(left_item)
left.remove(left_item)
else:
result.append(right_item)
right.remove(right_item)
result.extend(left)
result.extend(right)
return result
# Merge Sort Algorithm
def merge_sort_dp(input_list, d=dict()):
input_list_len = len(input_list)
key = ''.join(map(str, input_list))
if key not in d:
if len(input_list) <= 1:
d[key] = input_list
else:
mid = input_list_len // 2
left = merge_sort_dp(input_list[0:mid])
right = merge_sort_dp(input_list[mid:input_list_len])
d[key] = merge_dp(left, right)
return d[key]
# Test Cases
print(test_merge_sort_dp([3,4,1,5,2,9,6,8,7,0],[0,1,2,3,4,5,6,7,8,9]))
print(test_merge_sort_dp([9, 6, 8, 7, 0],[0, 6, 7, 8, 9]))
print(test_merge_sort_dp([8, 7, 0],[0, 7, 8]))
print(test_merge_sort_dp([3, 4, 1, 5, 2],[1, 2, 3, 4, 5]))
print(test_merge_sort_dp([3,4,1,5,2,9,6,8,7,0],[0,1,2,3,4,5,6,7,8,9]))
print(test_merge_sort_dp(["B","C","F","A","G","E","H","J","D","I"],["A","B","C","D","E","F","G","H","I","J"]))
print(test_merge_sort_dp(["B","C","A","E","D"],["A","B","C","D","E"]))
Note:
This dynamic merge sort algorithm saves results for a partial list of an input list if the partial list itself was used as an input in the recursive part of the algorithm. For example, after having ordered [9, 6, 8, 7, 0], the result for the partial list [8, 7, 0] can be retrieved from the dictionary. However, the partial list [6, 8, 7] is not stored in the dictionary and has to be ordered itself. The difference is that the latter was never used as an input of the recursive merge_sort_dp(). Whereas the first partial list was used as an input.+++ Dynamic Merge Sort with Test Cases +++
# Test Function def test_merge_sort_dp(input_list, expected): return expected == merge_sort_dp(input_list) # Merge Algorithm def merge_dp(left_list, right_list): left = left_list.copy() right = right_list.copy() result = list() while len(left) > 0 and len(right) > 0: left_item = left[0] right_item = right[0] if left_item < right_item: result.append(left_item) left.remove(left_item) else: result.append(right_item) right.remove(right_item) result.extend(left) result.extend(right) return result # Merge Sort Algorithm def merge_sort_dp(input_list, d=dict()): input_list_len = len(input_list) key = ''.join(map(str, input_list)) if key not in d: if len(input_list) <= 1: d[key] = input_list else: mid = input_list_len // 2 left = merge_sort_dp(input_list[0:mid]) right = merge_sort_dp(input_list[mid:input_list_len]) d[key] = merge_dp(left, right) return d[key] # Test Cases print(test_merge_sort_dp([3,4,1,5,2,9,6,8,7,0],[0,1,2,3,4,5,6,7,8,9])) print(test_merge_sort_dp([9, 6, 8, 7, 0],[0, 6, 7, 8, 9])) print(test_merge_sort_dp([8, 7, 0],[0, 7, 8])) print(test_merge_sort_dp([3, 4, 1, 5, 2],[1, 2, 3, 4, 5])) print(test_merge_sort_dp([3,4,1,5,2,9,6,8,7,0],[0,1,2,3,4,5,6,7,8,9])) print(test_merge_sort_dp(["B","C","F","A","G","E","H","J","D","I"],["A","B","C","D","E","F","G","H","I","J"])) print(test_merge_sort_dp(["B","C","A","E","D"],["A","B","C","D","E"]))
@SeverinJB Sevi, could you explain your thinking process behind editing the merge() algorithm definition, when you added
left = left_list.copy() right = right_list.copy()
in its definition? I am trying to understand why this is necessary to make your merge_sort_dp() work. As I tried your code without editing merge() in the way you did, and it doesn't work.
Would be awesome if you could explain your thinking process also in general!
My approach, based on a mix of Severin's and Eleonora's approaches but with a focus on labelling each of the 5 steps of dynamic programming.
STEP 1: base case - solution already exists
STEP 2: base case - easy-to-solve, approach directly
STEP 3: divide
STEP 4: conquer
STEP 5: combine
STEP 6: memorize
I created an ancillary function list_to_key() to handle the key label creations for each element in the dictionary separately.
# ____________MERGE_________________________
def merge(left_list, right_list):
left = left_list.copy()
right = right_list.copy()
result = list()
while len(left) > 0 and len(right) > 0:
left_item = left[0]
right_item = right[0]
if left_item < right_item:
result.append(left_item)
left.remove(left_item)
else:
result.append(right_item)
right.remove(right_item)
result.extend(left)
result.extend(right)
return result
#_______ANCILLARY FUNCT: LIST_TO_KEY()_______
def list_to_key(input_list):
key_list = list()
for item in input_list:
str_item = str(item)
key_list.append(str_item)
key_name = ""
for i in key_list:
key_name += str(i)
return key_name
#__________TEST_DYNAMIC _MSORT_________________
def test_dynamic_msort(input_list, expected, d=dict()):
result = dynamic_msort(input_list, d=dict())
if result == expected:
return True
else:
return False
#_____________DYNAMIC _MSORT_________________
def dynamic_msort(input_list, d=dict()):
len_input_list = len(input_list)
key = list_to_key(input_list)
if key in d: # STEP 1-base case: solution exists
return d[key]
elif len_input_list <= 1: # STEP 2-base case: address directly
d[key] = input_list
return d[key]
else: #recursive step
mid = len_input_list // 2 # STEP 3- divide
left_list = input_list[0:mid]
right_list = input_list[mid:len_input_list]
left = dynamic_msort(left_list) # STEP 4-conquer
right = dynamic_msort(right_list) # STEP 4conquer
merged_list = merge(left, right) # STEP 5 -combine
d[key] = merged_list # STEP 6- memorize
return d[key]
print(test_dynamic_msort([3,4,1,5,2,9,6,8,7,0],[0,1,2,3,4,5,6,7,8,9]))
print(test_dynamic_msort([9, 6, 8, 7, 0],[0, 6, 7, 8, 9]))
print(test_dynamic_msort([8, 7, 0],[0, 7, 8]))
print(test_dynamic_msort([3, 4, 1, 5, 2],[1, 2, 3, 4, 5]))
print(test_dynamic_msort([3,4,1,5,2,9,6,8,7,0],[0,1,2,3,4,5,6,7,8,9]))
print(test_dynamic_msort(["B","C","F","A","G","E","H","J","D","I"],["A","B","C","D","E","F","G","H","I","J"]))
print(test_dynamic_msort(["B","C","A","E","D"],["A","B","C","D","E"]))
# True
# True
# True
# True
# True
# True
# True
@SeverinJB I figured it out the merge() edit on my own! We need to use copies of the lists, because otherwise our dictionaries are corrupted every time we run the merge() function.
@SeverinJB Sevi, could you explain your thinking process behind editing the merge() algorithm definition, when you added
left = left_list.copy() right = right_list.copy()
@SeverinJB I figured it out the merge() edit on my own! We need to use copies of the lists, because otherwise our dictionaries are corrupted every time we run the merge() function.
Hi @delfimpandiani,
Sorry for not coming back to your questions earlier.
For clarification:
With copy_list = main_list only the reference is copied. It's like the computer is storing the list with a generic name "281x829yez", but there are now two human-readable names (copy_list and main_list) which can be used to address the list. Hence, when copy_list is modified main_list is simultaneously modified! The additional "copy()" in copy_list = main_list.copy() creates an actual copy of main_list and stores this copy in copy_list.
Hopefully, this helps.
Hi all,
Here my take on the exercise - source codes available online.
# Import the function 'merge' from the module 'merge' (file 'merge.py')
from merge import merge
# Test case for the algorithm
def test_merge_sort_dp(input_list, expected):
result = merge_sort_dp(input_list)
if expected == result:
return True
else:
return False
# Code of the algorithm
def merge_sort_dp(input_list, prev_l=list()):
result = find_solution(input_list, prev_l)
if result is None:
if len(input_list) <= 1:
result = input_list
store_solution(result, prev_l)
else:
input_list_len = len(input_list)
mid = input_list_len // 2
left = merge_sort_dp(input_list[0:mid], prev_l)
right = merge_sort_dp(input_list[mid:input_list_len], prev_l)
result = merge(left, right)
store_solution(result, prev_l)
return result
def find_solution(input_list, sol_list):
input_dic = create_list_dict(input_list)
for d, sol in sol_list:
if input_dic == d:
return list(sol)
def store_solution(input_list, solution_list):
d = create_list_dict(input_list)
solution_list.append((d, list(input_list)))
def create_list_dict(input_list):
d = {}
for el in input_list:
if el not in d:
d[el] = 0
d[el] = d[el] + 1
return d
print(test_merge_sort_dp([], []))
print(test_merge_sort_dp([1], [1]))
print(test_merge_sort_dp([3, 4, 1, 2, 9, 8, 2], [1, 2, 2, 3, 4, 8, 9]))
print(test_merge_sort_dp(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere"],
["American Gods", "Coraline", "Good Omens", "Neverwhere", "The Graveyard Book"]))
print(test_merge_sort_dp(["Coraline", "American Gods", "The Graveyard Book", "Good Omens", "Neverwhere", "American Gods",
"American Gods", "Good Omens", "The Graveyard Book", "American Gods", "Neverwhere", "Coraline"],
["American Gods", "American Gods","American Gods", "American Gods", "Coraline", "Coraline",
"Good Omens", "Good Omens", "Neverwhere", "Neverwhere", "The Graveyard Book", "The Graveyard Book"]))
I didn't see the solution of the exercise again. I tried to create an algoritm but I'm not sure of the efficiency, because it returns the result, but maybe it iterates in an unneccessary way. Could it work?
def test_merge(left_list, right_list, expected):
result = merge(left_list, right_list)
if expected == result:
return True
else:
return False
def merge(left_list, right_list):
result = list()
while len(left_list) > 0 and len(right_list) > 0:
left_item = left_list[0]
right_item = right_list[0]
if left_item < right_item:
result.append(left_item)
left_list.remove(left_item)
else:
result.append(right_item)
right_list.remove(right_item)
result.extend(left_list)
result.extend(right_list)
return result
def test_merge_sort(input_list, expected, d):
if merge_sort(input_list, d) == expected:
return True
else:
return False
def merge_sort(input_list, d):
input_list_len = len(input_list)
for item in input_list:
if item not in d:
if input_list_len <= 1:
d[merge] = input_list
else:
mid = input_list_len // 2
left = merge_sort(input_list[0:mid], d)
right = merge_sort(input_list[mid:input_list_len], d)
d[merge] = merge(left, right)
return d[merge]
print(test_merge_sort(["Coraline", "American Gods", "Neverwhere", "Neverwhere", "American Gods", "Coraline"],
['American Gods', 'American Gods', 'Coraline', 'Coraline', 'Neverwhere', 'Neverwhere'], ({})))