# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# +
# Permutation of a list of items (anagram)

test_set = [1,2,3] 
def permutate(number_set, results = None, solutions = None): # to not to store the mutable default arguments in memory
    if results == None: results = []
    if solutions == None: solutions = []
    if len(number_set) == 0: 
        results.append(solutions)
        return
    for i, n in enumerate(number_set):
        remaining = number_set[:i] + number_set[i+1:]
        if remaining != None:
            permutate(remaining, results, solutions + [n])
    return results 

permutate(test_set)       
    

# +
# The breakdown of all elements in any permutation possible. Note the base case does not have a return

numbers = [1,2,3]
def perm_of_any_combination(numbers, results = None, picked_items = None):
    if results == None: results = []
    if picked_items == None: picked_items = []
    if len(picked_items) > 0: 
        results.append(picked_items) 
    for i, n in enumerate(numbers):
        remaining = numbers[:i] + numbers[i+1:]
        if remaining != None:
            perm_of_any_combination(remaining, results, picked_items + [n])
    return results 

print(perm_of_any_combination(numbers))


# +
# Permutations of all subset sum lists to reach a target 
# (All ways to reach an element while using each element only once)

import numpy as np
numbers = [1,2,3,4,5,6] 

def subset_sum_permutation(numbers, target, results = None, partial_sum = None):
    if results == None: results = []
    if partial_sum == None: partial_sum = []
    if sum(partial_sum) == target: 
        results.append(partial_sum) 
        return
    for i, n in enumerate(numbers):
        remaining = numbers[:i] + numbers[i+1:]
        if remaining != None:
            subset_sum_permutation(remaining, target, results, partial_sum + [n])
    return results 
subset_sum_permutation(numbers, 7)       
    

# +
# Combinations of subset sum list to reach a target 

numbers = [1,2,3,4,5,6] 
def subset_sum_combination(numbers, target, results = None, partial_sum = None):
    if results == None: results = []
    if partial_sum == None: partial_sum = []
    if sum(partial_sum) == target: 
        results.append(partial_sum) 
        return
    for i, n in enumerate(numbers):
        remaining = numbers[i+1:]
        if remaining != None:
            subset_sum_combination(remaining, target, results, partial_sum + [n])
    return results 
subset_sum_combination(numbers, 6)       
    

# +
# All possible moves to reach a target with repetitions allowed

numbers = [1,2,3,4] 
print(numbers)

def all_ways_to_reach_target(numbers, target, results = None, partial_sum = None):
    if results == None: results = []
    if partial_sum == None: partial_sum = []
    if sum(partial_sum) > target: return
    if sum(partial_sum) == target: 
        results.append(partial_sum) 
        return
    for i, n in enumerate(numbers):
        all_ways_to_reach_target(numbers, target, results, partial_sum + [n])
    return results 
all_ways_to_reach_target(numbers, 5)  



# +
# Permutation of all subsequences with length k using each element once

test_set = ['a','b','c'] 
def subsequence_with_length_k(numbers, k, results = None, picked_items = None):
    if results == None: results = []
    if picked_items == None: picked_items = []
    if len(picked_items) == k: 
        results.append(picked_items) 
        return
    for i, n in enumerate(numbers):
        remaining = numbers[:i] + numbers[i+1:]
        if remaining != None:
            subsequence_with_length_k(remaining, k, results, picked_items + [n])
    return results
solution = subsequence_with_length_k(test_set, 2) 

print(solution)
print(["".join(i) for i in solution]) 


# +
# Combination of all subsequences with length k

test_set = ['a','b','c'] 
def comb_subsequence_with_length_k(numbers, k, results = None, picked_items = None):
    if results == None: results = []
    if picked_items == None: picked_items = []
    if len(picked_items) == k: 
        results.append(picked_items)
        return
    for i, n in enumerate(numbers):
        remaining = numbers[i+1:]
        if remaining != None:
            comb_subsequence_with_length_k(remaining, k, results, picked_items + [n])
    return results
solution = comb_subsequence_with_length_k(test_set, 2) 

print(solution)
print(["".join(i) for i in solution]) 


# +
# All possible permutations of length j with repetitions of any element allowed

test_set = ['a','b','c'] 
def permutations_with_length_k(numbers, k, results = None, picked_items = None):
    if results == None: results = []
    if picked_items == None: picked_items = []
    if len(picked_items) == k: 
        results.append(picked_items) 
        return
    for i, n in enumerate(numbers):
        permutations_with_length_k(numbers, k, results, picked_items + [n])
    return results
solution = permutations_with_length_k(test_set, 2) 

print(solution)
print(["".join(i) for i in solution]) 


# +
# Checking if sum of any combination of elements in an array of integers is equal to the target

def find_target(target, list_of_items):
    if target in list_of_items: return True
    if len(list_of_items) == 0 : return False
    for i in range(len(list_of_items)):
        result = find_target(target - list_of_items[i], list_of_items[:i] + list_of_items[i+1:])
    return result    
find_target(11, [1,2,3,4,5])


# +
# Find the min distance with recursion in a a densely connected directed graph in matrix representation

# prepare a random test matrix
import numpy as np
np.random.seed(0)
def test_graph(n): # n vertices
    test_graph_set = np.random.randn(n,n)*100
    # 0 the source so that it is acyclic
    for i in range(n):
        test_graph_set[i][:i+1] = np.inf
    test_graph_set = np.around(test_graph_set, decimals = 2)
    test_graph_set = np.abs(test_graph_set)
    return test_graph_set

test_set = test_graph(5) 
print(test_set)


def minCostRec(cost, s, d): 
    if s == d or s+1 == d: return cost[s][d] 
    min_cost = cost[s][d] 
    for i in range(s+1, d): 
        c = minCostRec(cost,s, i) + minCostRec(cost, i, d) 
        if c < min_cost: 
            min_cost = c 
    return min_cost
  

cost = test_set

print('The minimum cost to reach station 0 to all stations:')
for i in range(1, len(cost[0])):
    print('from first station to:', i)
    print(minCostRec(cost, 0, i))

# -

#     # OTHER AVAILABLE ONLINE SOLUTIONS TO THESE PROBLEMS
#     
#     # Best way to reach t
#     S = [1,2,3]
#     t = 3
#     def all_ways_to_reach_t(S, t):
#         all_solutions = []
#         if t == 0: return [[]]
#         for s in [s for s in S if s <= t]:
#             for g in all_ways_to_reach_t(S, t-s):
#                 if g != None:
#                     each_solution = g + [s] 
#                     all_solutions.append(each_solution)
#         return all_solutions
#     all_ways_to_reach_t(S,t)

#     # Best way to permutate
#     numbers = [1,2,3]
#
#     def permutation(S): # this function will shuffle all the items and output all permutations by USING ALL ELEMENTS
#         all_solutions = []
#         if len(S) == 0: return [[]]
#         for i, s in enumerate(S):
#             for g in permutation(S[:i] + S[i+1:]):
#                 solution = g + [s]
#                 all_solutions.append(solution)
#         return all_solutions
#
#     permutation(numbers)
#

#     # Partition the permutations according to their first element.
#     # Each permutation = first element + [permutation of all but first element]
#     # We will return a list of possible sets of size N
#     # if N = 1: list of lists of size 1, e.g.: [[3]], len(results) = N! = 1
#     # if N = 0: list of lists of size 0, e.g.: [[]], len(results) = N! = 0! = 1
#     # if N = 2: list of lists of size 2, e.g.: [[1,2], [2,1]], len(results) = N! = 2! = 2
#     def scratch_permutation(S):
#         result = []
#         # If there is no element in the set, return [[]]
#         if len(S) == 0: return [[]]
#         # Otherwise, write the partitioning by first element:
#         for i, future_first_item in enumerate(S):
#             # What are the remaining items to shuffle?
#             remain = S[:i] + S[i+1:]
#             # Create the list of all permutations of that remaining set
#             remain_perm = scratch_permutation(remain)
#             # Assemble the new permutations by sticking first_item in front of all of them
#             for end_perm in remain_perm:
#                 result.append([future_first_item] + end_perm)
#         return result
#
#     scratch_permutation([1,2,4])
#     

#     # Print all possible strings of length j. In other words: print all subsequences with lenght j
#
#     results = []
#     def print_k_permutations(set, prefix, k, j): 
#         n = len(set)
#         if (k == 0): 
#             return results
#         for i in range(n): 
#             newPrefix = prefix + set[i] 
#             if len(newPrefix) == j:
#                 results.append(newPrefix)
#             print_k_permutations(set, newPrefix, k - 1, j) 
#         return results
#
#     # print("First Test") 
#     # set1 = ['a', 'b'] 
#     # k1 = 2
#     # print_k_permutations(set1, '', k1, 2) 
#
#     print("\nSecond Test") 
#     set2 = ['a', 'b', 'c'] 
#     print_k_permutations(set2, '', 2, 2) 
#     

#     results = []
#     def print_k_perm_no_repetitions(set, prefix, k, j): 
#         n = len(set)
#         if (k == 0): 
#             return results
#         for i in range(n): 
#             newPrefix = prefix + set[i] 
#             remaining = set[:i] + set[i+1:]
#             if len(newPrefix) == j:
#                 results.append(newPrefix)
#             print_k_perm_no_repetitions(remaining, newPrefix, k - 1, j) 
#         return results
#
#     # print("First Test") 
#     # set1 = ['a', 'b'] 
#     # k1 = 2
#     # print_k_permutations(set1, '', k1, 2) 
#
#     print("\nSecond Test") 
#     set2 = ['a', 'b', 'c', 'd'] 
#     print_k_perm_no_repetitions(set2, '', 2, 2) 

#     results = []
#     def print_k_comb(set, prefix, k, j): 
#         n = len(set)
#         if (k == 0): 
#             return results
#         for i in range(n): 
#             newPrefix = prefix + set[i] 
#             remaining = set[i+1:]
#             if len(newPrefix) == j:
#                 results.append(newPrefix)
#             print_k_comb(remaining, newPrefix, k - 1, j) 
#         return results
#
#     # print("First Test") 
#     # set1 = ['a', 'b'] 
#     # k1 = 2
#     # print_k_permutations(set1, '', k1, 2) 
#
#     print("\nSecond Test") 
#     set2 = ['a', 'b', 'c', 'd'] 
#     print_k_comb(set2, '', 2, 2) 
#

#     # compute binomial coefficients (the number of ways to pick k items among n items) recursively
#     # That is: binom_coef(n, k) should be a sum that uses calls to binom_coef with n-1 instead of n
#     def binom(n, k):
#         if n < k:
#             return None
#         nom = 1
#         denom = 1
#         for i in range(k+1, n+1):  # 5 * 4 
#             nom = nom*i
#         for j in range(1, n-k+1):  # 2 * 1
#             denom = denom*j
#         return nom/denom
#
#     binom(5,3)  # 5*4*3*2*1 / [3*2*1 * 2*1]  simplify nominator ==  5*4 
#
#     # 123, 124, 125, 134, 135, 145, 234, 235, 245, 345

#     # now write a function to print out these items of the BINOMIAL COEFFICIENT
#     # output all combinations of 3 numbers picked from [1,2,3,4,5]
#     # no replacement, meaning no repeating numbers, n is the list, k is the length of combination
#     results = []
#     def print_k_comb(set, prefix, k, j): 
#         n = len(set)
#         if (k == 0): return results
#         for i in range(n): 
#             newPrefix = prefix + set[i] 
#             remaining = set[i+1:]
#             if len(newPrefix) == j:
#                 results.append(newPrefix)
#             print_k_comb(remaining, newPrefix, k - 1, j) 
#         return results
#
#
#     set2 = ['1', '2', '3', '4', '5'] 
#     print_k_comb(set2, '', 2, 2) 

#     def palindrome(a):
#         if len(a) <= 1: return True
#         if a[0] != a[-1]: 
#             return False
#         else:
#             return palindrome(a[1:-1])
#
#     palindrome('abckcba')
#     b = 'abccba'
#     print(b[1:-1]) # bccb  since [-1] is not included!!!



StarcoderdataJupyterScriptsDedupFiltered