Giter VIP home page Giter VIP logo

Comments (8)

SeverinJB avatar SeverinJB commented on July 23, 2024 2

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"]))

from 2018-2019.

EleonoraPeruch avatar EleonoraPeruch commented on July 23, 2024 1 
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

from 2018-2019.

delfimpandiani avatar delfimpandiani commented on July 23, 2024 1

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.

from 2018-2019.

simayguzel avatar simayguzel commented on July 23, 2024 
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 2018-2019.

delfimpandiani avatar delfimpandiani commented on July 23, 2024

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!

from 2018-2019.

SeverinJB avatar SeverinJB commented on July 23, 2024

@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.

from 2018-2019.

essepuntato avatar essepuntato commented on July 23, 2024

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"]))

from 2018-2019.

MilenaCorbellini avatar MilenaCorbellini commented on July 23, 2024

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'], ({})))

from 2018-2019.

Related Issues (20)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.