Structured Problem Solving and Decomposition Questions

import random
from collections import defaultdict
from functools import lru_cache

def approx_shapley(baseline, current, metric_fn, n_samples=1000, seed=None):
    """
    baseline, current: dict of feature -> value
    metric_fn: callable mapping dict(feature->value) -> scalar
    n_samples: number of permutation samples
    Returns: dict feature -> estimated Shapley contribution
    """
    if seed is not None:
        random.seed(seed)
    features = list(baseline.keys())
    m = len(features)

    # cache metric evaluations for partial assignments (frozenset of (feat,val))
    cache = {}

    def eval_partial(assign):
        # assign: dict of some features -> values; unspecified features assumed baseline
        # key uses sorted tuple for determinism
        key = tuple(sorted(assign.items()))
        if key in cache:
            return cache[key]
        # build full mapping: unspecified -> baseline
        full = {f: assign.get(f, baseline[f]) for f in features}
        val = metric_fn(full)
        cache[key] = val
        return val

    contributions = defaultdict(float)
    for _ in range(n_samples):
        perm = features[:] 
        random.shuffle(perm)
        # start with no features set (all baseline)
        prev_assign = {}
        prev_val = eval_partial(prev_assign)
        for feat in perm:
            # value if we include feat at its current value
            new_assign = dict(prev_assign)
            new_assign[feat] = current[feat]
            new_val = eval_partial(new_assign)
            marginal = new_val - prev_val
            contributions[feat] += marginal
            prev_assign = new_assign
            prev_val = new_val

    # average over samples
    for f in contributions:
        contributions[f] /= n_samples
    return dict(contributions)