# 1. Set Covering Algorithm
def set_covering(universe, subsets):
    print("All Available Subsets:")
    for name, elements in subsets.items():
        print(f"  {name}: {elements}")
    print("=" * 40)
    
    elements_to_cover = set(universe)
    selected_sets = []
    
    while elements_to_cover:
        best_set = max(subsets, key=lambda name:len(subsets[name] & elements_to_cover))
        if not (subsets[best_set] & elements_to_cover):
            break
        
        selected_sets.append(best_set)
        elements_to_cover -= subsets[best_set]
        
    print("Selected Sets to Cover Universe:")
    for i, name in enumerate(selected_sets, 1):
        print(f"  Selection {i}: {name} (covers {subsets[name]})")
    print("=" * 40)
    print(f"Total Sets Selected: {len(selected_sets)}")
    print("=" * 40)

universe_set = {1, 2, 3, 4, 5}
available_subsets = {'Set A': {1, 2, 3}, 'Set B': {2, 4}, 'Set C': {4, 5}, 'Set D': {1, 5}}
set_covering(universe_set, available_subsets)


# 2. Subset Sum Algorithm
def subset_sum(numbers, target):
    print(f"Available Numbers: {numbers} | Target Sum = {target}")
    print("=" * 40)
    
    def backtrack(index, current_sum, current_subset):
        if current_sum == target:
            return current_subset
        if current_sum > target or index >= len(numbers):
            return None
        return backtrack(index + 1, current_sum + numbers[index], current_subset + [numbers[index]]) or backtrack(index + 1, current_sum, current_subset)
        
    result = backtrack(0, 0, [])
    
    print("Selected Subset:")
    if result:
        print(f"  Elements: {result} (Sum = {sum(result)})")
    else:
        print("  No valid subset found!")
    print("=" * 40)
    print(f"Subset Sum Found: {result is not None}")
    print("=" * 40)

nums = [1, 3, 4, 5]
subset_sum(nums, 9)


# 3. Vertex Covering Algorithm
def vertex_cover(edges):
    print("All Available Graph Edges:")
    for i, (u, v) in enumerate(edges, 1):
        print(f"  Edge {i}: Node {u} -- Node {v}")
    print("=" * 40)
    
    remaining_edges = list(edges)
    cover = set()
    
    while remaining_edges:
        flat_vertices = [node for edge in remaining_edges for node in edge]
        best_vertex = max(set(flat_vertices), key=flat_vertices.count)
        
        cover.add(best_vertex)
        remaining_edges = [(u, v) for u, v in remaining_edges if u != best_vertex and v != best_vertex]
        
    print("Selected Vertex Cover Nodes:")
    for i, vertex in enumerate(sorted(cover), 1):
        print(f"  Cover Node {i}: Node {vertex}")
    print("=" * 40)
    print(f"Total Vertices in Cover: {len(cover)}")
    print("=" * 40)

graph_edges = [('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('B', 'D')]
vertex_cover(graph_edges)



