## 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

```

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

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)

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

```

## 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