ভার্টেক্স কভার ও সেট কভার অ্যাপ্রক্সিমেশন

import random
from itertools import combinations

def approx_vertex_cover(edges):
    # ম্যাক্সিমাল-ম্যাচিং-ভিত্তিক ২-অ্যাপ্রক্সিমেশন
    remaining = set(edges)
    cover = set()
    while remaining:
        u, v = next(iter(remaining))       # যেকোনো একটি এখনো-না-কভার-হওয়া এজ
        cover.add(u)
        cover.add(v)
        remaining = {(a, b) for (a, b) in remaining if a != u and a != v and b != u and b != v}
    return cover

def brute_force_vertex_cover(n, edges):
    # সাবসেট সাইজ ০, ১, ২, ... ক্রমান্বয়ে বাড়িয়ে প্রথম বৈধ কভার খোঁজা -- এটিই সত্যিকারের ন্যূনতম
    vertices = list(range(n))
    for k in range(len(vertices) + 1):
        for subset in combinations(vertices, k):
            s = set(subset)
            if all(u in s or v in s for u, v in edges):
                return s
    return set(vertices)

def random_graph(rng, n, edge_prob):
    edges = []
    for u in range(n):
        for v in range(u + 1, n):
            if rng.random() < edge_prob:
                edges.append((u, v))
    return edges

rng = random.Random(7)
worst_ratio = 0.0
print(f"{'trial':>5} | {'n':>3} | {'edges':>6} | {'ALG':>4} | {'OPT':>4} | {'ratio':>6}")
for trial in range(15):
    n = rng.randint(4, 8)
    edge_prob = rng.choice([0.3, 0.4, 0.5, 0.6])
    edges = random_graph(rng, n, edge_prob)
    if not edges:
        continue
    approx = approx_vertex_cover(edges)
    opt = brute_force_vertex_cover(n, edges)
    ratio = len(approx) / len(opt)
    worst_ratio = max(worst_ratio, ratio)
    print(f"{trial:>5} | {n:>3} | {len(edges):>6} | {len(approx):>4} | {len(opt):>4} | {ratio:>6.2f}")
    assert len(approx) <= 2 * len(opt), "২-অ্যাপ্রক্সিমেশন বাউন্ড ভঙ্গ হয়েছে!"

print(f"\nসর্বোচ্চ পর্যবেক্ষিত ratio (ALG/OPT): {worst_ratio:.2f} -- সবসময় <= 2.00")

import random
from itertools import combinations

def greedy_set_cover(universe, subsets):
    universe = set(universe)
    covered = set()
    chosen = []
    remaining_subsets = list(subsets)
    while covered != universe and remaining_subsets:
        best = max(remaining_subsets, key=lambda s: len(set(s) - covered))
        chosen.append(best)
        covered |= set(best)
        remaining_subsets.remove(best)
    return chosen

def brute_force_set_cover(universe, subsets):
    universe = set(universe)
    n = len(subsets)
    for k in range(1, n + 1):
        for combo in combinations(range(n), k):
            union = set()
            for idx in combo:
                union |= set(subsets[idx])
            if union == universe:
                return [subsets[idx] for idx in combo]
    return list(subsets)

def random_set_cover_instance(rng, universe_size, num_subsets):
    universe = list(range(universe_size))
    subsets = []
    for _ in range(num_subsets):
        size = rng.randint(1, universe_size)
        subsets.append(tuple(rng.sample(universe, size)))
    # নিশ্চিত করা যে ইউনিয়ন পুরো ইউনিভার্স কভার করে (নাহলে কোনো বৈধ কভারই নেই)
    covered = set()
    for s in subsets:
        covered |= set(s)
    if covered != set(universe):
        subsets.append(tuple(universe))
    return universe, subsets

rng = random.Random(3)
print(f"{'trial':>5} | {'universe':>8} | {'greedy #sets':>12} | {'OPT #sets':>9} | {'ratio':>6}")
for trial in range(8):
    universe, subsets = random_set_cover_instance(rng, universe_size=rng.randint(4, 6), num_subsets=rng.randint(3, 6))
    greedy = greedy_set_cover(universe, subsets)
    opt = brute_force_set_cover(universe, subsets)
    ratio = len(greedy) / len(opt)
    print(f"{trial:>5} | {len(universe):>8} | {len(greedy):>12} | {len(opt):>9} | {ratio:>6.2f}")

print("\nএই ছোট ইনস্ট্যান্সগুলোতে গ্রিডি প্রায়ই অপটিমামের কাছাকাছি -- কিন্তু লক্ষ্য করুন এখানে কোনো")
print("assert ratio <= 2 নেই, কারণ সাধারণ সেট কভারে এমন ধ্রুবক গ্যারান্টি প্রমাণিতভাবেই নেই।")