Updates from January, 2017 Toggle Comment Threads | Keyboard Shortcuts

  • loctv 8:27 pm on January 3, 2017 Permalink | Reply
    Tags: ,   

    Find all possible outcomes of a given expression 

    *Source: Geeks4Geeks

    Given an arithmetic expression, find all possible outcomes of this expression. Different outcomes are evaluated by putting brackets at different places.

    We may assume that the numbers are single digit numbers in given expression.

    Example:

    Input:  1+3*2
    Output: 8  7
    Explanation
    (1 + 3)*2     = 80
    (1 + (3 * 2)) = 70
    
    Input:  1*2+3*4
    Output: 14 20 14 20 20
     (1*(2+(3*4))) =  14
     (1*((2+3)*4)) =  20 
     ((1*2)+(3*4)) =  14
     ((1*(2+3))*4) =  20
     ((1*2)+3)*4)  =  20

    The idea is to iterate through every operator in given expression. For every operator, evaluate all possible values of its left and right sides. Apply current operator on every pair of left side and right side values and add all evaluated values to the result.

    1) Initialize result 'res' as empty.
    2) Do following for every operator 'x'.
        a) Recursively evaluate all possible values on left of 'x'.
           Let the list of values be 'l'.  
        a) Recursively evaluate all possible values on right of 'x'.
           Let the list of values be 'r'.
        c) Loop through all values in list 'l'  
               loop through all values in list 'r'
                   Apply current operator 'x' on current items of 
                   'l' and 'r' and add the evaluated value to 'res'   
    3) Return 'res'.

    Implementation: Python2.7

    """
        Calculate all possible outcomes of a given expression
        Constraint: All numbers in the expression must be 1-digit number
    """
    def evaluate(number1, operator, number2):
        """
            return value of number1 operator number2
            example: 1 + 2
        """
        expression = str(number1) + ' ' + operator + ' ' +  str(number2)
        return eval(expression)
    
    def evaluate_all(expression, low, high):
        """
            Evaluate all possible values of the expression
        """
        res = [] #store all possible outcomes
        if low == high: #only one character, it must be a digit
            res.append(int(expression[low]))
            return res
    
        #if there are only 3 characters
        #middle one must be operator and corner ones must be operands
        if low == (high-2):
            res.append(evaluate(expression[low], expression[low+1], expression[low+2]))
            return res
    
        #every i refers to an operator
        for i in range(low+1, high+1, 2):
            #left refers to all the possible values
            #in the left of operator expression[i]
            left = evaluate_all(expression, low, i-1)
            #right refers to all the possible values
            #in the right of operator expression[i]
            right = evaluate_all(expression, i+1, high)
            print left, expression[i], right
            #take above evaluated all possible
            #values in left side of 'i'
            for s1 in range(len(left)):
                #take above evaluated all possible
                #values in right side of 'i'
                for s2 in range(len(right)):
                    res.append(evaluate(left[s1], expression[i], right[s2]))
        return res
    
    if __name__ == '__main__':
        EXPR = '1*2+3*4'
        ALL_POSSIBLE_OUTCOMES = evaluate_all(EXPR, 0, len(EXPR)-1)
        for outcome in ALL_POSSIBLE_OUTCOMES:
            print outcome
    
    
    Advertisements
     
  • loctv 7:53 pm on January 3, 2017 Permalink | Reply
    Tags: ,   

    Using merge sort to solve ‘Counting Inversions Problem’ 

    Describe: Given a list contains n numbers, count all inversions in that list.
    Example: [4, 2, 3, 5, 1]
    There are 6 inversions
    4-2
    4-3
    4-1
    2-1
    3-1
    5-1

    The easiest way is using two for-loops, but the complexity is O(n^2), which is unacceptable with a list of large amount of numbers.
    There is more efficient and faster way is using merge sort. If you still haven’t know merge sort yet, please check out this. Using merge sort, we can simultaneously count the number of inversions and sort data. The complexity of this method is equal with complexity of merge sort itself.

    Here’s the pseudocode.

    screen-shot-2017-01-03-at-7-40-03-pm

    Example: [4, 2, 3, 5, 1]

    *LEFT = [4,2]
    -left = 4
    -right = 2
    -merge([4], [2]) = [2,4] : 1 inversion (2 jumps over 4)
    *RIGHT = [3,5,1]
    -left = 3
    -right = [5,1]
    –left = 5
    –right = 1
    –merge([5], [1]) = [1,5] : 1 inversion (1 jumps over 5)
    -merge([3], [1,5]) = [1,3,5] : 1 inversion (1 jumps over 3)
    *MERGE([2,4], [1,3,5]) = [1,2,3,4,5]
    res = []
    step1:
    right[0] res = [1], left = [2,4], right = [3,5]
    step2:
    left[0] res = [1,2], left = [4], right = [3,5]
    step3:
    right[0] res = [1,2,3], left=[4], right=[5]
    There will be no more inversion since [4] < [5]
    Total of inversions: 1+1+1+2+1 = 6

    Implementation: Python2.7

    """
        Using merge sort algorithm to count inversions in a list of data
        @author: loctv
        @time: 05:51PM January 3, 2017 (+7)
    """
    
    def sort_and_count(data):
        """
            repeatedly divide data into two parts
            return (number_of_inversions, sorted_data)
        """
        if len(data) == 1: #data contains only 1 element
            return (0, data)
        #divide data into two parts
        left_side = data[:len(data)//2]
        right_side = data[len(data)//2:]
        #recursive call on two parts
        print left_side, right_side
        left_count, left_side = sort_and_count(left_side)
        right_count, right_side = sort_and_count(right_side)
        total_count, sorted_data = merge_and_count(left_side, right_side)
        return total_count + left_count + right_count, sorted_data
    
    def merge_and_count(left, right):
        """
            merge left and right
            count the number of inversions while merging two sides
        """
        result, count_inversion = [], 0
        while len(left) > 0 and len(right) > 0:
            if left[0] < right[0]:
                result.append(left[0])
                del left[0]
            else: #inversions appear
                result.append(right[0])
                #number of inversion = the number of element in left side
                count_inversion += len(left)
                del right[0]
        #append the rest elements in either left or right side into result
        while len(left) > 0:
            result.append(left[0])
            del left[0]
        while len(right) > 0:
            result.append(right[0])
            del right[0]
        return count_inversion, result
    
    if __name__ == '__main__':
        DATA = [4, 2, 3, 5, 1]
        INVERSIONS, SORTED_DATA = sort_and_count(DATA)
        print INVERSIONS, SORTED_DATA
    
    
     
  • loctv 5:49 pm on January 3, 2017 Permalink | Reply
    Tags: ,   

    Merge Sort (Python implementation) 

    Pseudocode:

    merge_sort(L):
        if L contain only 1 element:
            return L
        #divide L into two parts
        LEFT = half left of L 
        RIGHT = half right of L
        #recursive call for two parts  
        LEFT = merge_sort(LEFT)
        RIGHT = merge_sort(RIGHT)
        #merge two part together
        result = merge(LEFT, RIGHT)
        return result 
    
    merge(LEFT, RIGHT):
        result = empty list
        while LEFT and RIGHT contain more than one element:
            append the smallest element in LEFT or RIGHT into result 
            remove it (reduce size of LEFT or RIGHT)
        #in case there are some elements left inside LEFT or RIGHT
        while LEFT contain more than one element:
            append the first element of LEFT into result 
            remove it out of LEFT 
        while RIGHT contain more than one lement:
            append the first eleemnt of RIGHT into result
            remove it out of RIGHT
        return result
    

    Example: [4,2,3,5,1]
    *LEFT = [4,2]
    -left = 4
    -right = 2
    -merge = [2,4]
    *RIGHT = [3,5,1]
    -left = 3
    -right = [5,1]
    –left = 5
    –rigt = 1
    –merge = [1,5]
    -merge = [1,3,5]
    *merge([2,4], [1,3,5])
    result: 1,2,3,4,5

    Implementation: Python2.7

    """
        Stimulate merge sort algorithm
        @author: loctv
        @time: 05:33PM January 3, 2017 (+7)
    """
    
    def merge_sort(data):
        """
            Sort function, repeatedly divide a list of values in two part untill there is only one left
        """
        if len(data) == 1: #base case, data contains only one value
            return data
        #divide data into two parts
        left_side = data[:len(data)//2] #left
        right_side = data[len(data)//2:] #and right
        left_side = merge_sort(left_side) #recursive call to left side
        right_side = merge_sort(right_side) #recursive call to right side
        sorted_data = merge(left_side, right_side) #merge two sides together
        return sorted_data # return sorted list
    
    def merge(left_side, right_side):
        """
            Merge method of merge-sort algorithm
        """
        result = []
        while len(left_side) > 0 and len(right_side) > 0:
            #append the smallest value in to result
            if left_side[0] < right_side[0]:
                result.append(left_side[0])
                del left_side[0]
            else:
                result.append(right_side[0])
                del right_side[0]
        #append the remain values on either left or right side
        while len(left_side) > 0:
            result.append(left_side[0])
            del left_side[0]
        while len(right_side) > 0:
            result.append(right_side[0])
            del right_side[0]
        return result
    
    if __name__ == '__main__':
        DATA = [4, 2, 3, 5, 1]
        DATA = merge_sort(DATA)
        print DATA
    
    
     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel