Python Algorithm Implementations Collection
Posted on Mar 29, 2025 in Other university degrees and diplomas
Greedy Coin Change Algorithm
from sys import maxsize as infinite
def solve(coins, change):
change_list = []
while change > 0 and coins != [0] * len(coins):
max_coin = max(coins)
index = coins.index(max_coin)
if change >= coins[index]:
change_list.append(index + 1)
change -= coins[index]
coins[index] = 0
return change_list
Greedy Knapsack Algorithm
def solve(items, capacity):
taken = []
value = 0
items = sorted(
enumerate(items), key=lambda x: x[1][0] / x[1][1], reverse=True
)
for index, (v, w) in items:
if w <= capacity:
capacity -= w
value += v
taken.append(index + 1)
if capacity == 0:
break
return taken, value
Median Calculation (Quickselect)
from simple_stack import Stack
def solve(items, median_index):
stack = Stack()
stack.push((0, len(items) - 1))
while not stack.isEmpty():
low, high = stack.pop()
if low == high:
return items[low]
pivot = partition(items, low, high)
if pivot == median_index:
return items[pivot]
elif pivot > median_index:
stack.push((low, pivot - 1))
else:
stack.push((pivot + 1, high))
return -1
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
Dijkstra’s Algorithm Implementation
import networkx as nx
from sys import maxsize as infinite
from simple_queue import *
import heapq
def solve(graph, from_node, to_node):
priority_queue = []
distances = {node: float('inf') for node in graph.nodes}
distances[from_node] = 0
heapq.heappush(priority_queue, (0, from_node))
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
if current_distance > distances[current_node]:
continue
for neighbor in graph.successors(current_node):
weight = graph[current_node][neighbor]['weight']
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances[to_node] if distances[to_node] != float('inf') else -1
Shortest Path with Memoization
from networkx import *
def solve(graph, from_node, to_node):
value = 0
taken = []
mem = {from_node: ((None, from_node), 0)} # Assuming from_node is the base case
def dist(u, v):
# Check memoization table first
if v in mem:
return mem[v][1]
solutions = []
# Base case check moved to the top for clarity
# if v == from_node:
# return 0
# Check if node has predecessors
predecessors = list(graph.predecessors(v))
if not predecessors:
# Handle nodes with no predecessors (could be start or disconnected)
# This part might need adjustment based on graph structure/problem
# If it's not the start node, it might be unreachable this way
if v != from_node:
return float('inf') # Indicate unreachable
else:
return 0 # Start node distance is 0
for pred in predecessors:
# Recursive call: find distance to predecessor 'pred'
# Note: Original code had dist(v, pred), which seems incorrect.
# It should likely be finding the distance *to* the predecessor from the start.
# Let's assume dist(pred) is the intended logic (distance from from_node to pred).
# This requires the function signature/logic to be potentially different.
# Sticking to the original structure for now, but noting the potential issue.
# If dist(u, v) means shortest path from u to v, the logic needs rework.
# Assuming dist(v) means shortest path from from_node to v:
dist_to_pred = dist(from_node, pred) # Adjusted recursive call assumption
if dist_to_pred != float('inf'):
solutions.append(
((pred, v), dist_to_pred + graph[pred][v]['weight'])
)
if not solutions:
# If no valid path found from predecessors
mem[v] = ((None, v), float('inf'))
return float('inf')
minimum = min(solutions, key=lambda item: item[1])
mem[v] = minimum
return minimum[1]
# Initial call to calculate distance to the target node
final_dist = dist(from_node, to_node)
# Reconstruct path if a valid distance was found
if final_dist != float('inf'):
value = final_dist
curr = to_node
while curr is not None and curr != from_node:
taken.insert(0, curr)
if curr in mem:
pred, _ = mem[curr][0]
curr = pred
else:
# Should not happen if dist calculation is correct
break
if curr == from_node:
taken.insert(0, from_node)
else:
# Path reconstruction failed or incomplete
taken = []
value = -1 # Or indicate error
else:
value = -1 # Indicate no path found
taken = []
return value, taken
# Note: The logic in the original memoization code, especially the recursive call
# and path reconstruction, might need review for correctness based on the exact
# problem definition (shortest path from from_node to to_node).
# The provided fix attempts to follow the structure while addressing potential issues.
Longest Increasing Subsequence (Tabulation)
def solve_tabulation(items):
n = len(items)
if n == 0:
return 0, []
# dp[i] stores the length of the LIS ending at index i
dp = [1] * n
# predecessor[i] stores the index of the element before items[i] in the LIS ending at i
predecessor = [-1] * n
for i in range(n):
for j in range(i):
if items[i] > items[j]:
if dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
predecessor[i] = j
# Find the maximum length and the index where it ends
max_length = 0
end_index = -1
for i in range(n):
if dp[i] > max_length:
max_length = dp[i]
end_index = i
# Reconstruct the LIS using the predecessor array
taken_indices = []
current_index = end_index
while current_index != -1:
# Store 1-based index as in the original code's intent
taken_indices.append(current_index + 1)
current_index = predecessor[current_index]
taken_indices.reverse() # Reverse to get the correct order
return max_length, taken_indices
# Note: The original tabulation code seemed to implement a different logic
# than standard LIS tabulation. This version provides a standard LIS
# tabulation approach which seems more likely intended, returning the length
# and the 1-based indices of the elements in one such LIS.
Greedy Graph Coloring
def greedy_coloring(graph, order_nodes):
num_nodes = len(order_nodes)
node_colors = {} # Use dictionary for clarity {node: color}
node_to_index = {node: i for i, node in enumerate(order_nodes)}
# Assign colors based on the specified order
for i, node in enumerate(order_nodes):
neighbor_colors = set()
# Check colors of already colored neighbors
for neighbor in graph.neighbors(node):
if neighbor in node_colors:
neighbor_colors.add(node_colors[neighbor])
# Find the smallest available color (starting from 0)
current_color = 0
while current_color in neighbor_colors:
current_color += 1
node_colors[node] = current_color
# Return colors in the order of order_nodes
result_colors = [node_colors[node] for node in order_nodes]
return result_colors
# Note: The original greedy coloring logic had potential issues with iteration
# and color assignment. This revised version implements a standard greedy coloring
# algorithm based on the provided node order.
Recursive Branch and Bound (Knapsack)
from node import * # Assuming node.py defines the Node class appropriately
def solve_branch_and_bound_DFS(capacity, items, record_visiting_order=False):
visiting_order = []
# Ensure items have value and weight, maybe sort them by value/weight ratio?
# items = sorted(items, key=lambda x: x.value / x.weight, reverse=True) # Optional pre-sorting
root_node = Node(index=0, taken=[], value=0, room=capacity)
best_value = 0
best_taken = []
# Stack for DFS simulation if not using system recursion stack
stack = [root_node]
while stack:
current = stack.pop()
if record_visiting_order:
# Record based on item index being considered (0 to n-1)
# Or use a unique node ID if available
visiting_order.append(current.index)
# Pruning: If remaining capacity is negative, or estimate is worse than best found
# The Node class needs an estimate method (e.g., linear relaxation)
if current.room < 0 or current.estimate(items) <= best_value:
continue
# Update best solution found so far if current node is better
# Check if it's a potential leaf or represents a complete solution
if current.value > best_value:
best_value = current.value
best_taken = current.taken
# Note: Best solution might be updated even if not all items are considered,
# if the current partial solution is already better than any complete found so far.
# If there are more items to consider
if current.index < len(items):
# Branch 1: Exclude the current item
# Node for excluding item current.index
node_exclude = Node(current.index + 1,
current.taken,
current.value,
current.room)
# Only push if potentially promising (estimate > best_value)
if node_exclude.estimate(items) > best_value:
stack.append(node_exclude)
# Branch 2: Include the current item (if possible)
item = items[current.index]
if current.room >= item.weight:
# Node for including item current.index
node_include = Node(current.index + 1,
current.taken + [current.index + 1], # Store 1-based index
current.value + item.value,
current.room - item.weight)
# Only push if potentially promising (estimate > best_value)
# Also check if the immediate value is better, helps update best_value sooner
if node_include.value > best_value:
best_value = node_include.value
best_taken = node_include.taken
if node_include.estimate(items) > best_value:
stack.append(node_include)
return best_value, best_taken, visiting_order
# Note: This implements an iterative DFS using a stack instead of recursion.
# It assumes the 'Node' class has an 'estimate' method for bounding.
# The original recursive version is also valid but might hit recursion depth limits.
# The path reconstruction ('taken') and visiting order logic are adjusted.
# Assumes 'items' is a list of objects with 'value' and 'weight' attributes.
