About
from typing import List class Solution:
ans = []
ds = []
def recurPermute(self, nums: List[int], freq: List[int]):
if len(self.ds) == len(nums):
self.ans.append(self.ds.copy())
return
for i in range(len(nums)):
if not freq[i]:
self.ds.append(nums[i])
freq[i] = 1
self.recurPermute(nums, freq)
freq[i] = 0
self.ds.pop()
def permute(self, nums: List[int]) -> List[List[int]]:
self.ans = []
self.ds = []
freq = [0] * len(nums)
self.recurPermute(nums, freq)
return self.ansif __name__ == "__main__": obj = Solution() v = [1, 2, 3] sum = obj.permute(v) print("All Permutations are ") for i in range(len(sum)): for j in range(len(sum[i])): print(sum[i][j], end=" ") print()
class Solution: def isSafe1(self, row, col, board, n):
# check upper element
duprow = row
dupcol = col
while row >= 0 and col >= 0:
if board[row][col] == 'Q':
return False
row -= 1
col -= 1
col = dupcol
row = duprow
while col >= 0:
if board[row][col] == 'Q':
return False
col -= 1
row = duprow
col = dupcol
while row < n and col >= 0:
if board[row][col] == 'Q':
return False
row += 1
col -= 1
return True
def solve(self, col, board, ans, n):
if col == n:
ans.append(list(board))
return
for row in range(n):
if self.isSafe1(row, col, board, n):
board[row] = board[row][:col] + 'Q' + board[row][col+1:]
self.solve(col+1, board, ans, n)
board[row] = board[row][:col] + '.' + board[row][col+1:]
def solveNQueens(self, n):
ans = []
board = ['.'*n for _ in range(n)]
self.solve(0, board, ans, n)
return ansn = 4 obj = Solution() ans = obj.solveNQueens(n) for i in range(len(ans)): print(f"Arrangement {i+1}") for j in range(len(ans[0])): print(ans[i][j]) print()
from typing import List
def isValid(board: List[List[str]], row: int, col: int, c: str) -> bool: for i in range(9): if board[i][col] == c: return False if board[row][i] == c: return False if board[3 (row // 3) + i // 3][3 (col // 3) + i % 3] == c: return False return True
def solveSudoku(board: List[List[str]]) -> bool: for i in range(len(board)): for j in range(len(board[0])): if board[i][j] == ".": for c in "123456789": if isValid(board, i, j, c): board[i][j] = c if solveSudoku(board): return True else: board[i][j] = "." return False return True
if __name__ == "__main__": board = [ ["9", "5", "7", ".", "1", "3", ".", "8", "4"], ["4", "8", "3", ".", "5", "7", "1", ".", "6"], [".", "1", "2", ".", "4", "9", "5", "3", "7"], ["1", "7", ".", "3", ".", "4", "9", ".", "2"], ["5", ".", "4", "9", "7", ".", "3", "6", "."], ["3", ".", "9", "5", ".", "8", "7", ".", "1"], ["8", "4", "5", "7", "9", ".", "6", "1", "3"], [".", "9", "1", ".", "3", "6", ".", "7", "5"], ["7", ".", "6", "1", "8", "5", "4", ".", "9"], ] solveSudoku(board) for i in range(9): for j in range(9): print(board[i][j], end=" ") print()
def isSafe(node, color, graph, n, col): for k in range(n): if k != node and graph[k][node] == 1 and color[k] == col: return False return True
def solve(node, color, m, N, graph): if node == N: return True
for i in range(1, m + 1):
if isSafe(node, color, graph, N, i):
color[node] = i
if solve(node + 1, color, m, N, graph):
return True
color[node] = 0
return FalseFunction to determine if graph can be coloured with at most M colours such
that no two adjacent vertices of graph are coloured with same colour.
def graphColoring(graph, m, N): color = [0] * N if solve(0, color, m, N, graph): return True return False
if __name__ == '__main__': N = 4 m = 3
graph = [[0 for i in range(101)] for j in range(101)]
# Edges are (0, 1), (1, 2), (2, 3), (3, 0), (0, 2)
graph[0][1] = 1
graph[1][0] = 1
graph[1][2] = 1
graph[2][1] = 1
graph[2][3] = 1
graph[3][2] = 1
graph[3][0] = 1
graph[0][3] = 1
graph[0][2] = 1
graph[2][0] = 1
print(1 if graphColoring(graph, m, N) else 0)from typing import List
class Solution:
def findPathHelper(self, i: int, j: int, a: List[List[int]], n: int, ans: List[str], move: str, vis: List[List[int]]):
if i == n - 1 and j == n - 1:
ans.append(move)
return
# downward
if i + 1 < n and not vis[i + 1][j] and a[i + 1][j] == 1:
vis[i][j] = 1
self.findPathHelper(i + 1, j, a, n, ans, move + 'D', vis)
vis[i][j] = 0
# left
if j - 1 >= 0 and not vis[i][j - 1] and a[i][j - 1] == 1:
vis[i][j] = 1
self.findPathHelper(i, j - 1, a, n, ans, move + 'L', vis)
vis[i][j] = 0
# right
if j + 1 < n and not vis[i][j + 1] and a[i][j + 1] == 1:
vis[i][j] = 1
self.findPathHelper(i, j + 1, a, n, ans, move + 'R', vis)
vis[i][j] = 0
# upward
if i - 1 >= 0 and not vis[i - 1][j] and a[i - 1][j] == 1:
vis[i][j] = 1
self.findPathHelper(i - 1, j, a, n, ans, move + 'U', vis)
vis[i][j] = 0
def findPath(self, m: List[List[int]], n: int) -> List[str]:
ans = []
vis = [[0 for _ in range(n)] for _ in range(n)]
if m[0][0] == 1:
self.findPathHelper(0, 0, m, n, ans, "", vis)
return ansif __name__ == '__main__': n = 4
m = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 1, 0, 0], [0, 1, 1, 1]]
obj = Solution()
result = obj.findPath(m, n)
if len(result) == 0:
print(-1)
else:
for i in range(len(result)):
print(result[i], end=" ")
print()from queue import PriorityQueue
class Job: def __init__(self,id,deadline,penalty): self.id=id self.deadline=deadline self.penalty=penalty def __lt__(self,other): return self.penalty > other.penalty
def jobSequencing(jobArray,maxDeadine): queue = PriorityQueue() for i in jobArray: queue.put(i) job_final_sequence = [-1]*maxDeadine while not queue.empty(): job = queue.get() for i in range(job.deadline-1,-1,-1): if(job_final_sequence[i]==-1): job_final_sequence[i] = job.id break return job_final_sequence
jobs = [Job("a", 2, 100), Job("b", 1, 19), Job("c", 2, 27), Job("d", 1, 25), Job("e", 3, 15),Job("f", 2, 100)] maxDeadline = max(job.deadline for job in jobs) result = jobSequencing(jobs,maxDeadline) print(result)
class Item: def __init__(self,value,weight): self.value = value self.weight = weight
def __lt__(self,other): return self.weight < other.weight
class Node: def __init__(self,level,value,weight,cost,content): self.level = level self.value = value self.weight = weight self.cost = cost self.content = content def bound(u,n,V,items): cost_bound = u.cost j = u.level + 1 total_value = u.value while j<len(items) and total_value + items[j].value < V: cost_bound += items[j].weight total_value += items[j].value j+=1 return cost_bound
def knapsack(items,V): n = len(items) queue = [] v = Node(-1,0,0,0,[]) queue.append(v) min_cost = float('inf') best_items = [] while queue: v = queue.pop() if (v.level == -1): u = Node(0,0,0,0,[]) else: u = Node(v.level+1,v.value,v.weight,v.cost,v.content.copy()) if u.level == n or u.value >= V: continue u.value +=items[u.level].value u.weight +=items[u.level].weight u.cost +=items[u.level].weight u.content.append(items[u.level]) if (u.value >= V and u.cost < min_cost): min_cost = u.cost best_items = u.content if bound(u,n,V,items) < min_cost: queue.append(u)
u2 = Node(u.level,v.value,v.weight,v.cost,v.content.copy()) if bound(u2,n,V,items) < min_cost: queue.append(u2) return min_cost,best_items
items = [Item(60, 10), Item(100, 20), Item(120, 30)] V = 180 min_cost, items_chosen = knapsack(items, V) print("Minimum cost to achieve value =", V, "is", min_cost) print("Items chosen:", [(item.value, item.weight) for item in items_chosen])