import numpy as np

def fgp_transform(instance, signalize, discretize, guard,
                  band=("low", 0, 10), mask_type="soft",
                  threshold=None, seed=42):
    # 1) map instance -> numeric signal
    s = signalize(instance)                 # domain-specific
    # 2) forward DFT
    S = np.fft.fft(s)
    # 3) guided band mask in frequency domain
    S_t = apply_guided_mask(S, band=band, mode=mask_type)
    # 4) inverse + discrete remapping
    s_inv = np.fft.ifft(S_t).real
    inst_p = discretize(s_inv, threshold)
    # 5) semantics guard (fail/rollback if violated)
    if not guard(inst_p):
        raise ValueError("Combinatorial semantics violated.")
    return inst_p

import networkx as nx
import numpy as np

def lgp_transform(G, discretize, guard, k=3, use_heat_kernel=False, beta=0.3):
    # 1) Build Laplacian (combinatorial; normalized variants are also possible)
    L = nx.laplacian_matrix(G).astype(float).toarray()
    # 2) Eigendecomposition (symmetric => eigh)
    eigvals, eigvecs = np.linalg.eigh(L)

    if use_heat_kernel:
        # Heat kernel smoothing: U exp(-beta Lambda) U^T x
        # Here we illustrate node-wise features x as the all-ones vector
        x = np.ones((L.shape[0], 1))
        H = eigvecs @ np.diag(np.exp(-beta * eigvals)) @ eigvecs.T
        x_smooth = H @ x
        G_smooth = discretize(x_smooth, params={})
    else:
        # Low-frequency reconstruction using the smallest-k eigenvectors
        U_k = eigvecs[:, :k]
        P = U_k @ U_k.T  # projector onto low-frequency subspace
        # Example: project adjacency rows/columns (domain-specific choices apply)
        A = nx.to_numpy_array(G)
        A_smooth = P @ A @ P
        G_smooth = discretize(A_smooth, params={})

    # 3) Semantics guard: must preserve combinatorial constraints
    if not guard(G_smooth):
        raise ValueError("Combinatorial semantics violated by LGP output.")
    return G_smooth

import numpy as np

# Example distribution of structural states
p = np.array([0.1, 0.3, 0.4, 0.2])

# Compute entropy (Boltzmann constant k = 1)
S = -np.sum(p * np.log(p))

def extract_data(I, M, include_failures=True, seed=42, levels=[0.1, 0.5, 0.9]):
    InitRandomSeed(seed)

    # curves (before / after)
    c0 = ComputeSolvabilityCurve(I)
    I1 = ApplyPreprocessing(I, M)
    c1 = ComputeSolvabilityCurve(I1)

    # transition features (after)
    r_star = FindCriticalThreshold(c1)
    d_r    = MeasureTransitionWidth(c1)
    slope  = ComputeMidpointSlope(c1)
    succ   = EvaluateSuccessRates(c1, levels)
    ent    = CalculateEntropy(c1)
    sfeat  = ExtractStructuralFeatures(I1)

    # optional failure analytics (after)
    fails=fent=fpat=fcause=None
    if include_failures:
        fails  = IdentifyFailureRegions(c1)
        fent   = CalculateFailureEntropyGradient(c1, fails)
        fpat   = ClassifyFailurePatterns(c1, fails)
        fcause = EstimateFailureCauses(I1, c1, fails)

    # impact (before vs after)
    impact = CompareBeforeAfter(c0, c1, r_star, d_r, slope, succ)

    rec = {
        "instance": GetInstanceId(I),
        "problem_type": GetProblemType(I),
        "method": GetMethodId(M),
        "seed": seed,
        "r_star": r_star, "delta_r": d_r, "slope": slope,
        "success": succ, "entropy": ent,
        "structural_features": sfeat,
        "impact": impact,
        "fail_regions": fails, "fail_entropy_grad": fent,
        "fail_patterns": fpat, "fail_causes": fcause
    }
    SaveRecord(rec, format="CSV/JSON")
    return rec

import random
import matplotlib.pyplot as plt

# --- 1. Experimental Configuration ---
# A fixed seed is set to ensure that the same pseudo-random sequence is generated
# on every run, guaranteeing the reproducibility of the experimental results.
random.seed(42)

# Define key parameters for the experiment to generate problem instances.
# These parameters directly influence the complexity and solvability landscape.
ARRAY_SIZE = 20          # N: The number of elements in each problem instance array.
ELEMENT_MAX = 40         # R: The maximum integer value for each element (values are in the range [1, R]).
NUM_TRIALS = 50          # M: The number of random problem instances to test for each target sum.
T_RANGE = range(200, 601, 20)  # T_min to T_max: The range of target sums to be tested (the x-axis of the plot).

# --- 2. Data Collection and Experiment Execution ---
# A list to store the measured success rate for each target sum in T_RANGE.
success_rates = []

# Main experimental loop: iterate through each target sum T in the predefined range.
for T in T_RANGE:
    success_count = 0

    # Inner loop: run the experiment for a fixed number of trials to get a statistically
    # significant success rate for the current target sum T.
    for _ in range(NUM_TRIALS):
        # Generate a random problem instance (an array of integers).
        arr = [random.randint(1, ELEMENT_MAX) for _ in range(ARRAY_SIZE)]

        # Dynamic Programming approach to solve the Subset Sum problem.
        # A set 'dp' is used to efficiently track all possible subset sums that can be formed.
        dp = {0}

        # Iterate through each number in the generated array.
        for num in arr:
            # Create a new set to store the updated reachable sums to avoid
            # modifying the set while iterating over it.
            new_dp = set(dp)
            for prev_sum in dp:
                if prev_sum + num <= T:
                    new_dp.add(prev_sum + num)
            # Update the set of reachable sums for the next iteration.
            dp = new_dp

        # Check if the target sum T is present in the set of reachable sums.
        if T in dp:
            success_count += 1

    # Calculate the success rate (probability of a solution existing) for the current T.
    success_rate = success_count / NUM_TRIALS
    success_rates.append(success_rate)

import random
import matplotlib.pyplot as plt

# --- 1. Experimental Configuration and Reproducibility ---
# A fixed seed is set to ensure that the same pseudo-random sequence is generated
# on every run, guaranteeing the reproducibility of the experimental results.
random.seed(42)

# Define key parameters for generating problem instances.
# These parameters directly influence the complexity and solvability landscape.
ARRAY_SIZE = 20          # N: The number of elements in each problem instance array.
ELEMENT_MAX = 40         # R: The maximum integer value for each element (range: [1, R]).
NUM_TRIALS = 50          # M: The number of random instances to test for each target sum T.
T_RANGE = range(200, 601, 20)  # T_min to T_max: The range of target sums to be tested (x-axis).

# --- 2. Data Collection and Experiment Execution ---
# A list to store the measured success rate for each target sum in T_RANGE.
success_rates = []

# Iterate through the range of target sums to conduct the main experiment.
for T in T_RANGE:
    success_count = 0

    # Run a fixed number of trials to obtain a statistically meaningful success rate.
    for _ in range(NUM_TRIALS):
        # Generate a random problem instance (an array of integers).
        arr = [random.randint(1, ELEMENT_MAX) for _ in range(ARRAY_SIZE)]

        # Dynamic Programming approach to solve the Subset Sum problem.
        # A set 'dp' efficiently tracks all possible subset sums that can be formed.
        dp = {0}

        # Iterate through each number in the generated array.
        for num in arr:
            # Create a new set to store the updated reachable sums to avoid
            # modifying the set while iterating over it.
            next_dp = set(dp)
            for prev_sum in dp:
                # Add the new sum to the set if it does not exceed the target T.
                if prev_sum + num <= T:
                    next_dp.add(prev_sum + num)
            # Update the set for the next iteration.
            dp = next_dp

        # Check if the target sum T is present in the set of reachable sums.
        if T in dp:
            success_count += 1

    # Calculate the success rate (probability of a solution existing) for the current T.
    success_rate = success_count / NUM_TRIALS
    success_rates.append(success_rate)

import numpy as np
import matplotlib.pyplot as plt
from scipy.fft import fft, ifft

# --- Experiment Configuration ---
# Fix the seed for reproducibility
np.random.seed(42)

# Size of the array to be generated randomly
array_size = 20
# Maximum value for elements in the array
element_max = 40
# Number of trials for each target sum (T)
num_trials = 100
# The range of target sums (T) to be tested
T_range = list(range(200, 601, 20))
# Fourier filter parameter
filter_k = 3

# --- 1. Raw Experiment Function ---
def run_raw_experiment():
    """
    Calculates the success rate of the subset sum problem using raw (unfiltered) arrays.
    """
    raw_rates = []
    for T in T_range:
        success_count = 0
        for _ in range(num_trials):
            # Generate a new random array for each trial
            arr = np.random.randint(1, element_max + 1, array_size)

            # Initialize a set for dynamic programming to store possible subset sums
            dp = set()
            dp.add(0)

            # Iterate through all elements of the current array
            for num in arr:
                # Add new sums that do not exceed T
                dp |= {prev_sum + num for prev_sum in dp if prev_sum + num <= T}

            # Check if the target sum T is in the set of possible sums
            if T in dp:
                success_count += 1
        raw_rates.append(success_count / num_trials)
    return np.array(raw_rates)

# --- 2. Fourier-based Structural Intervention Function ---
def run_fourier_experiment():
    """
    Calculates the success rate of the subset sum problem using arrays smoothed by a Fourier filter.
    """
    rates = []
    for T in T_range:
        success_count = 0
        for _ in range(num_trials):
            # Structural smoothing: Generate an array to which Fourier transform can be applied
            arr = np.random.randint(1, element_max + 1, array_size)
            fft_values = fft(arr)

            # Low-pass filtering: Remove high-frequency components to smooth the signal
            filtered_fft = fft_values.copy()
            # Set high-frequency components from filter_k onwards to zero
            filtered_fft[filter_k:] = 0

            # Reconstruct the smoothed array using inverse Fourier transform
            smoothed_arr = np.real(ifft(filtered_fft))

            # Adjust the element range back to [1, element_max] and convert to integer type
            smoothed_arr = np.clip(smoothed_arr, 1, element_max).astype(int)

            # Solve the subset sum problem with the smoothed array
            dp = set()
            dp.add(0)
            for num in smoothed_arr:
                dp |= {prev_sum + num for prev_sum in dp if prev_sum + num <= T}

            # Check if the target sum T is in the set
            if T in dp:
                success_count += 1
        rates.append(success_count / num_trials)
    return np.array(rates)

import numpy as np
import matplotlib.pyplot as plt
from tqdm import tqdm

# --- 1. Experimental Configuration and Reproducibility ---
# A fixed seed is set for both the 'random' and 'numpy' libraries to ensure
# that the same sequence of pseudo-random numbers is generated on every run,
# which is critical for the reproducibility of experimental results.
np.random.seed(42)

# Define key parameters for generating problem instances.
array_size = 20          # N: The number of elements in each problem instance array.
element_max = 40         # R: The maximum integer value for each element (range: [1, R]).
num_trials = 100         # M: The number of random instances to test for each target sum T.
T_range = list(range(200, 601, 20))  # T_min to T_max: The range of target sums to be tested (x-axis).

# Laplace smoothing parameter: The number of times local averaging is applied.
# A higher 'k' value results in a more significant smoothing effect, simulating a
# stronger diffusion of structural properties.
laplace_k = 3

# --- 2. Raw Experiment Function ---
def run_raw_experiment():
    """
    Executes the experiment on the original, unprocessed problem instances.
    It measures the success rate of the Subset Sum problem using a standard
    dynamic programming approach. This serves as the baseline for comparison.
    """
    raw_rates = []
    # Use tqdm for a progress bar, which is useful for long-running experiments.
    for T in tqdm(T_range, desc="Raw"):
        success_count = 0
        for _ in range(num_trials):
            # Generate a random array of integers for the Subset Sum problem.
            arr = np.random.randint(1, element_max + 1, array_size)

            # Dynamic programming approach to find all possible subset sums.
            # A set is used for efficient lookup and insertion.
            dp = {0}
            for num in arr:
                # Efficiently update the set of reachable sums.
                dp |= {s + num for s in dp if s + num <= T}

            # Check if the target sum is in the set of reachable sums.
            if T in dp:
                success_count += 1
        raw_rates.append(success_count / num_trials)
    return np.array(raw_rates)

# --- 3. Laplace Preprocessing Experiment Function ---
def run_laplace_experiment():
    """
    Executes the experiment on problem instances that have been preprocessed
    with Laplace-inspired smoothing. It measures the change in success rate
    due to this structural intervention.
    """
    laplace_rates = []
    for T in tqdm(T_range, desc="Laplace"):
        success_count = 0
        for _ in range(num_trials):
            # Generate the initial raw array.
            arr = np.random.randint(1, element_max + 1, array_size)

            # --- Laplace Smoothing ---
            # This loop iteratively applies a local averaging filter.
            # It models a diffusion process, smoothing out local fluctuations
            # and revealing a more global structural trend.
            for _ in range(laplace_k):
                smoothed = arr.copy()
                for i in range(1, len(arr) - 1):
                    # Each element is replaced by the mean of its neighbors (including itself).
                    smoothed[i] = int(np.mean([arr[i - 1], arr[i], arr[i + 1]]))
                arr = smoothed

            # Ensure all values remain within the valid range after smoothing.
            arr = np.clip(arr, 1, element_max).astype(int)

            # Solve the preprocessed Subset Sum instance using dynamic programming.
            dp = {0}
            for num in arr:
                dp |= {s + num for s in dp if s + num <= T}

            if T in dp:
                success_count += 1
        laplace_rates.append(success_count / num_trials)
    return np.array(laplace_rates)

import numpy as np
import matplotlib.pyplot as plt
from tqdm import tqdm

# --- 1. Experimental Configuration and Reproducibility ---
# A fixed seed is set for the 'numpy' library to ensure that the same sequence of
# pseudo-random numbers is generated on every run. This is crucial for the
# reproducibility of experimental results.
np.random.seed(42)

# Define key parameters for generating problem instances.
array_size = 20          # N: The number of elements in each problem instance array.
element_max = 40         # R: The maximum integer value for each element (range: [1, R]).
num_trials = 100         # M: The number of random instances to test for each target sum T.
T_range = list(range(200, 601, 20))  # T_min to T_max: The range of target sums (x-axis).

# Laplacian mask parameter: a scaling factor to control the strength of the filter.
# This factor determines how much the local structural changes are emphasized.
laplacian_strength = 0.5

# --- 2. Raw Experiment Function ---
def run_raw_experiment():
    """
    Executes the experiment on the original, unprocessed problem instances.
    It calculates the success rate of the Subset Sum problem using a standard
    dynamic programming approach. This provides the baseline for comparison.
    """
    raw_rates = []
    # Use tqdm for a progress bar, which is useful for tracking progress.
    for T in tqdm(T_range, desc="Raw"):
        success_count = 0
        for _ in range(num_trials):
            # Generate a new random array for each trial.
            arr = np.random.randint(1, element_max + 1, array_size)

            # Dynamic programming approach to find all possible subset sums.
            # A set is used for efficient storage and lookup.
            dp = {0}
            for num in arr:
                # Efficiently update the set of reachable sums without exceeding T.
                dp |= {prev_sum + num for prev_sum in dp if prev_sum + num <= T}

            # Check if the target sum T is present in the set of reachable sums.
            if T in dp:
                success_count += 1
        raw_rates.append(success_count / num_trials)
    return np.array(raw_rates)

# --- 3. Laplacian Mask Experiment Function ---
def run_laplacian_mask_experiment():
    """
    Calculates the success rate of the subset sum problem using arrays
    that have been preprocessed with a Laplacian mask filter. This
    filter is a discrete second-order derivative that detects rapid
    changes in the array's values.
    """
    rates = []
    for T in tqdm(T_range, desc="Laplacian Mask"):
        success_count = 0
        for _ in range(num_trials):
            # Generate the initial raw array.
            arr = np.random.randint(1, element_max + 1, array_size)

            # --- Laplacian Mask Filter ---
            # Compute a discrete approximation of the second derivative.
            # This highlights local fluctuations and structural boundaries.
            laplacian_arr = np.zeros_like(arr, dtype=float)
            # The mask is a [1, -2, 1] kernel applied to the array.
            laplacian_arr[1:-1] = arr[2:] - 2 * arr[1:-1] + arr[:-2]

            # Enhance the original array by adding the Laplacian output,
            # scaled by the 'laplacian_strength' parameter. This amplifies
            # the local variations detected by the mask.
            filtered_arr = arr + laplacian_strength * laplacian_arr

            # Ensure the filtered array elements remain within the valid range
            # and convert them back to integers.
            filtered_arr = np.clip(filtered_arr, 1, element_max).astype(int)

            # Solve the preprocessed Subset Sum instance using dynamic programming.
            dp = {0}
            for num in filtered_arr:
                dp |= {prev_sum + num for prev_sum in dp if prev_sum + num <= T}

            if T in dp:
                success_count += 1
        rates.append(success_count / num_trials)
    return np.array(rates)

import numpy as np
import matplotlib.pyplot as plt
from tqdm import tqdm
from scipy.stats import entropy

# --- 1. Experimental Configuration and Reproducibility ---
# A fixed seed is set for the 'numpy' library to ensure that the same sequence of
# pseudo-random numbers is generated on every run. This is crucial for the
# reproducibility of experimental results.
np.random.seed(42)

# Define key parameters for generating problem instances.
array_size = 20          # N: The number of elements in each problem instance array.
element_max = 40         # R: The maximum integer value for each element (range: [1, R]).
num_trials = 100         # M: The number of random instances to test for each target sum T.
T_range = list(range(200, 601, 20))  # T_min to T_max: The range of target sums (x-axis).

# --- 2. Raw Experiment Function ---
def run_raw_experiment():
    """
    Executes the experiment on the original, unprocessed problem instances.
    It calculates the success rate of the Subset Sum problem using a standard
    dynamic programming approach. This provides the baseline for comparison.
    """
    raw_rates = []
    # Use tqdm for a progress bar, which is useful for tracking progress.
    for T in tqdm(T_range, desc="Raw"):
        success_count = 0
        for _ in range(num_trials):
            # Generate a new random array for each trial.
            arr = np.random.randint(1, element_max + 1, array_size)

            # Dynamic programming approach to find all possible subset sums.
            # A set is used for efficient storage and lookup.
            dp = {0}
            for num in arr:
                # Efficiently update the set of reachable sums without exceeding T.
                dp |= {prev_sum + num for prev_sum in dp if prev_sum + num <= T}

            # Check if the target sum T is present in the set of reachable sums.
            if T in dp:
                success_count += 1
        raw_rates.append(success_count / num_trials)
    return np.array(raw_rates)

# --- 3. Entropy Guided Preprocessing Experiment Function ---
def run_entropy_experiment():
    """
    Calculates the success rate of the subset sum problem using arrays
    that have been preprocessed with a entropy guided method. This method
    re-samples the array based on a distribution derived from its entropy, aiming
    to create a more ordered or less disordered problem structure.
    """
    thermo_rates = []
    for T in tqdm(T_range, desc="Entropy"):
        success_count = 0
        for _ in range(num_trials):
            # Generate a new random array.
            arr = np.random.randint(1, element_max + 1, array_size)

            # --- Entropy Guided Preprocessing ---
            # 1. Calculate a histogram to represent the distribution of elements.
            hist, _ = np.histogram(arr, bins=np.arange(1, element_max + 2))

            # 2. Normalize the histogram to get a probability distribution.
            if np.sum(hist) > 0:
                p = hist / np.sum(hist)
            else:
                # Handle cases where histogram is all zeros by creating a uniform distribution.
                p = np.ones(element_max) / element_max

            # 3. Calculate the entropy of the distribution.
            arr_entropy = entropy(p)

            # 4. Use the entropy to guide the re-sampling process.
            # The 'skew factor' is designed to reduce the entropy by favoring
            # values that are already more common.
            normalized_entropy = arr_entropy / np.log(element_max + 1)
            skew_factor = 1.0 - normalized_entropy

            # Create a new, less disordered probability distribution for resampling.
            # This skews the distribution towards values that were more frequent
            # in the original array.
            resample_dist = p + (1-p) * skew_factor
            resample_dist = resample_dist / np.sum(resample_dist)

            # 5. Resample a new array from this less disordered distribution.
            # The range for resampling is now corrected to match the bins.
            processed_arr = np.random.choice(
                np.arange(1, element_max + 1),
                size=array_size,
                p=resample_dist
            )

            # Solve the subset sum problem with the processed array.
            dp = {0}
            for num in processed_arr:
                dp |= {s + num for s in dp if s + num <= T}

            if T in dp:
                success_count += 1
        thermo_rates.append(success_count / num_trials)
    return np.array(thermo_rates)

import numpy as np
import matplotlib.pyplot as plt
from tqdm import tqdm

# --- 1. Experiment Configuration and Reproducibility ---
# A fixed seed is set for the 'numpy' library to ensure that the same sequence of
# pseudo-random numbers is generated on every run. This is crucial for the
# reproducibility of experimental results.
np.random.seed(42)

# Define key parameters for generating problem instances.
array_size = 20          # N: The number of elements in each problem instance array.
element_max = 40         # R: The maximum integer value for each element (range: [1, R]).
num_trials = 100         # M: The number of random instances to test for each target sum T.
T_range = list(range(200, 601, 20))  # T_min to T_max: The range of target sums (x-axis).

# --- 2. Raw Experiment Function (DO NOT MODIFY) ---
def run_raw_experiment():
    """
    Executes the experiment on the original, unprocessed problem instances.
    It calculates the success rate of the Subset Sum problem using a standard
    dynamic programming approach. This provides the baseline for comparison.
    """
    raw_rates = []
    # Use tqdm for a progress bar, which is useful for tracking progress.
    for T in tqdm(T_range, desc="Raw"):
        success_count = 0
        for _ in range(num_trials):
            # Generate a new random array for each trial.
            arr = np.random.randint(1, element_max + 1, array_size)

            # Dynamic programming approach to find all possible subset sums.
            # A set is used for efficient storage and lookup.
            dp = {0}
            for num in arr:
                # Efficiently update the set of reachable sums without exceeding T.
                dp |= {s + num for s in dp if s + num <= T}

            # Check if the target sum T is present in the set of reachable sums.
            if T in dp:
                success_count += 1
        raw_rates.append(success_count / num_trials)
    return np.array(raw_rates)

# --- 3. Entropy Guided Preprocessing Function (Softmax-inspired) ---
def run_entropy_experiment(temperature=1.5):
    """
    Calculates the success rate of the subset sum problem using arrays
    that have been preprocessed with a softmax-inspired Entropy method.
    The method transforms the array to emphasize larger values, which can
    change the problem's solvability landscape.
    """
    thermo_rates = []
    # Use tqdm for a progress bar for this experiment as well.
    for T in tqdm(T_range, desc="Entropy"):
        success_count = 0
        for _ in range(num_trials):
            # Generate a new random array for this trial.
            arr = np.random.randint(1, element_max + 1, array_size)

            # --- Entropy Preprocessing ---
            # 1. Apply a softmax-inspired transformation. The 'temperature' parameter
            # controls the sharpness of the distribution. A lower temperature
            # makes larger values stand out more significantly.
            exp_arr = np.exp(arr / temperature)

            # 2. Normalize the values to create a probability distribution.
            prob_arr = exp_arr / np.sum(exp_arr)

            # 3. Scale the probability distribution back to the original range of values.
            # This step generates a new array where larger original values
            # are more likely to be represented by larger scaled values.
            scaled_arr = np.round(prob_arr * array_size * element_max).astype(int)

            # Solve the subset sum problem with the preprocessed (scaled) array.
            dp = {0}
            for num in scaled_arr:
                dp |= {s + num for s in dp if s + num <= T}

            # Check for a solution.
            if T in dp:
                success_count += 1
        thermo_rates.append(success_count / num_trials)
    return np.array(thermo_rates)
    

!pip install python-sat[pblib,aiger]

# --- Import Required Packages ---
# Import all necessary libraries for the experiment.
import random
import time
import numpy as np
import matplotlib.pyplot as plt
from pysat.solvers import Glucose3
from tqdm import tqdm
from scipy.stats import entropy
import copy

# --- 1. Experimental Configuration and Reproducibility ---
# A fixed seed is set for both the 'random' and 'numpy' libraries
# to ensure that the same sequence of pseudo-random numbers is generated
# on every run, guaranteeing the reproducibility of the experimental results.
random.seed(42)
np.random.seed(42)

# Define key parameters for the experiment.
# These parameters are chosen to investigate the phase transition region of the 3-SAT problem.
n = 60  # The number of boolean variables. A classic size for observing phase transitions.
# Constraint density (r = m/n) values to be tested. The density is the ratio of clauses to variables.
r_values = np.arange(2.0, 6.1, 0.2)
# Number of random SAT instances generated for each (n, r) setting.
instances_per_setting = 100

# Dictionary to store the experimental results for each method.
# It will store the satisfiability ratio and average solving time.
results = {
    'Raw': {'sat_ratio': [], 'avg_time': []},
    'Fourier': {'sat_ratio': [], 'avg_time': []},
    'Laplace': {'sat_ratio': [], 'avg_time': []},
    'Entropy': {'sat_ratio': [], 'avg_time': []}
}

# --- 2. Preprocessing Functions ---

def apply_fourier_low_pass(clauses):
    """
    Applies a low-pass Fourier filter to the SAT clauses.
    This method reinterprets the problem instance as a signal and uses
    frequency-domain analysis to smooth out high-frequency (noisy or local)
    components, aiming to reveal the underlying macroscopic structure.

    Args:
        clauses (list): A list of clauses, where each clause is a list of literals.

    Returns:
        list: The preprocessed list of clauses.
    """
    if not clauses:
        return []

    # Flatten the clauses into a single list of literals, separating signs.
    flattened_literals = [lit for clause in clauses for lit in clause]
    signs = np.array([np.sign(lit) for lit in flattened_literals])
    abs_values = np.array([abs(lit) for lit in flattened_literals], dtype=float)

    # Perform a Fast Fourier Transform (FFT) on the absolute literal values.
    fft_vals = np.fft.fft(abs_values)

    # Create a simple low-pass filter mask. This filter keeps only the lowest 10%
    # of frequency components, effectively removing high-frequency noise.
    cutoff = int(len(fft_vals) * 0.1)
    filter_mask = np.zeros_like(fft_vals)
    filter_mask[:cutoff] = 1
    filter_mask[-cutoff:] = 1  # The filter is symmetric for real-valued signals.

    # Apply the mask and perform the inverse Fourier transform (IFFT).
    filtered_fft_vals = fft_vals * filter_mask
    smoothed_abs_values = np.real(np.fft.ifft(filtered_fft_vals))

    # Reconstruct the clauses by rounding the smoothed values and re-applying
    # the original signs. Values are clipped to stay within the valid range [1, n].
    reconstructed_literals = np.round(np.clip(smoothed_abs_values, 1, n)).astype(int)
    reconstructed_literals = [val * sign for val, sign in zip(reconstructed_literals, signs)]

    # Re-assemble the flattened list of literals into clauses.
    new_clauses = []
    literal_idx = 0
    for clause in clauses:
        new_clause = []
        for _ in clause:
            new_clause.append(reconstructed_literals[literal_idx])
            literal_idx += 1
        new_clauses.append(new_clause)

    return new_clauses

def apply_laplace_smoothing(clauses, iterations=3):
    """
    Applies an iterative local averaging (Laplace-inspired smoothing)
    to the SAT clauses. This method models the problem as a discrete
    field and applies a diffusion-like process to smooth out local
    variations, thereby highlighting more global structural trends.

    Args:
        clauses (list): A list of clauses, where each clause is a list of literals.
        iterations (int): The number of times to apply the smoothing filter.

    Returns:
        list: The preprocessed list of clauses.
    """
    if not clauses:
        return []

    # Flatten the clauses and handle signs separately.
    flattened_literals = [lit for clause in clauses for lit in clause]
    signs = np.array([np.sign(lit) for lit in flattened_literals])
    arr = np.array([abs(lit) for lit in flattened_literals], dtype=float)

    # Apply smoothing repeatedly for a fixed number of iterations.
    for _ in range(iterations):
        smoothed_arr = arr.copy()
        for i in range(1, len(arr) - 1):
            # Each element is replaced by the average of its local neighbors,
            # analogous to a discretized Laplacian operator.
            smoothed_arr[i] = (arr[i-1] + arr[i] + arr[i+1]) / 3
        arr = smoothed_arr

    # Reconstruct the clauses with the smoothed values.
    reconstructed_literals = np.round(np.clip(arr, 1, n)).astype(int)
    reconstructed_literals = [val * sign for val, sign in zip(reconstructed_literals, signs)]

    # Re-assemble the flattened list of literals into clauses.
    new_clauses = []
    literal_idx = 0
    for clause in clauses:
        new_clause = []
        for _ in clause:
            new_clause.append(reconstructed_literals[literal_idx])
            literal_idx += 1
        new_clauses.append(new_clause)

    return new_clauses

def apply_entropy_resampling(clauses):
    """
    Applies an entropy-guided resampling method to the SAT clauses.
    This method is inspired by Entropy principles, where entropy measures
    the disorder of a system. By reducing the entropy of the literal distribution,
    this preprocessing aims to make the problem structure more regular and less random.

    Args:
        clauses (list): A list of clauses, where each clause is a list of literals.

    Returns:
        list: The preprocessed list of clauses.
    """
    if not clauses:
        return []

    # Flatten the clauses and handle signs separately.
    flattened_literals = [lit for clause in clauses for lit in clause]
    signs = np.array([np.sign(lit) for lit in flattened_literals])
    arr = np.array([abs(lit) for lit in flattened_literals])

    # Calculate the histogram and probability distribution of literals.
    hist, _ = np.histogram(arr, bins=np.arange(1, n + 2))
    p = hist / np.sum(hist)

    # Calculate the Shannon entropy of the literal distribution.
    arr_entropy = entropy(p)
    # Normalize the entropy for a defined range.
    normalized_entropy = arr_entropy / np.log(n + 1) if n > 0 else 0
    # The skew factor is based on the normalized entropy.
    skew_factor = 1.0 - normalized_entropy
    # Create a new, skewed probability distribution that favors less-random values.
    resample_dist = p + (1-p) * skew_factor
    resample_dist = resample_dist / np.sum(resample_dist)

    # Resample literals from the new, regularized distribution.
    reconstructed_literals = np.random.choice(
        np.arange(1, n + 1),
        size=len(flattened_literals),
        p=resample_dist
    )

    reconstructed_literals = [val * sign for val, sign in zip(reconstructed_literals, signs)]

    # Re-assemble the flattened list of literals into clauses.
    new_clauses = []
    literal_idx = 0
    for clause in clauses:
        new_clause = []
        for _ in clause:
            new_clause.append(reconstructed_literals[literal_idx])
            literal_idx += 1
        new_clauses.append(new_clause)

    return new_clauses

# Function: Generate a random 3-SAT instance
def generate_3sat_instance(n, m):
    """
    Generates a random 3-SAT CNF instance with n variables and m clauses.
    This is a standard procedure for creating instances in the study of NP problems.

    Args:
        n (int): The number of variables.
        m (int): The number of clauses.

    Returns:
        list: A list of clauses representing the CNF formula.
    """
    clauses = []
    for _ in range(m):
        # Randomly sample 3 distinct variables.
        vars = random.sample(range(1, n + 1), 3)
        clause = []
        for v in vars:
            # Assign a random sign (positive or negative literal) to each variable.
            clause.append(-v if random.random() < 0.5 else v)
        clauses.append(clause)
    return clauses

# --- 3. Main Experimental Loop ---
# Iterate through each constraint density 'r' to explore the solvability landscape.
for r in tqdm(r_values, desc=f"Running for n={n}"):
    m = int(r * n)

    # Run the experiment for each preprocessing method and the 'Raw' baseline.
    for method in results.keys():
        sat_count = 0
        total_time = 0.0

        # Perform multiple trials for a given (n, m) setting to get a robust average.
        for _ in range(instances_per_setting):
            # Generate the initial raw instance.
            cnf = generate_3sat_instance(n, m)

            # Apply the selected preprocessing method. 'deepcopy' ensures that
            # the original instance remains unaltered for other methods.
            processed_cnf = copy.deepcopy(cnf)
            if method == 'Fourier':
                processed_cnf = apply_fourier_low_pass(processed_cnf)
            elif method == 'Laplace':
                processed_cnf = apply_laplace_smoothing(processed_cnf)
            elif method == 'Entropy':
                processed_cnf = apply_entropy_resampling(processed_cnf)

            # The SAT solver requires integer literals.
            processed_cnf_int = [[int(literal) for literal in clause] for clause in processed_cnf]

            # Initialize and run the Glucose3 SAT solver.
            solver = Glucose3()
            for clause in processed_cnf_int:
                solver.add_clause(clause)

            start = time.time()
            sat = solver.solve()
            elapsed = time.time() - start

            if sat:
                sat_count += 1
            total_time += elapsed
            solver.delete()

        # Compute and save the average statistics for this (n, r) setting.
        sat_ratio = sat_count / instances_per_setting
        avg_time = total_time / instances_per_setting
        results[method]['sat_ratio'].append(sat_ratio)
        results[method]['avg_time'].append(avg_time)
        

!pip install python-sat[pblib,aiger]

# --- Import Required Packages ---
# Import all necessary libraries for the experiment.
import random
import time
import numpy as np
import matplotlib.pyplot as plt
from pysat.solvers import Glucose3
from tqdm import tqdm
from scipy.stats import entropy
import copy

# --- 1. Experimental Configuration and Reproducibility ---
# A fixed seed is set for both the 'random' and 'numpy' libraries
# to ensure that the same sequence of pseudo-random numbers is generated
# on every run, guaranteeing the reproducibility of the experimental results.
random.seed(42)
np.random.seed(42)

# Define key parameters for the experiment.
# These parameters are chosen to investigate the phase transition region of the 3-SAT problem.
n = 60  # The number of boolean variables. A classic size for observing phase transitions.
# Constraint density (r = m/n) values to be tested. The density is the ratio of clauses to variables.
r_values = np.arange(2.0, 6.1, 0.2)
# Number of random SAT instances generated for each (n, r) setting.
instances_per_setting = 100

# Dictionary to store the experimental results for each method.
# It will store the satisfiability ratio and average solving time.
results = {
    'Raw': {'sat_ratio': [], 'avg_time': []},
    'Fourier': {'sat_ratio': [], 'avg_time': []},
    'Laplace': {'sat_ratio': [], 'avg_time': []},
    'Entropy': {'sat_ratio': [], 'avg_time': []}
}

# --- 2. Preprocessing Functions ---

def apply_fourier_low_pass(clauses):
    """
    Applies a low-pass Fourier filter to the SAT clauses.
    This method reinterprets the problem instance as a signal and uses
    frequency-domain analysis to smooth out high-frequency (noisy or local)
    components, aiming to reveal the underlying macroscopic structure.

    Args:
        clauses (list): A list of clauses, where each clause is a list of literals.

    Returns:
        list: The preprocessed list of clauses.
    """
    if not clauses:
        return []

    # Flatten the clauses into a single list of literals, separating signs.
    flattened_literals = [lit for clause in clauses for lit in clause]
    signs = np.array([np.sign(lit) for lit in flattened_literals])
    abs_values = np.array([abs(lit) for lit in flattened_literals], dtype=float)

    # Perform a Fast Fourier Transform (FFT) on the absolute literal values.
    fft_vals = np.fft.fft(abs_values)

    # Create a simple low-pass filter mask. This filter keeps only the lowest 10%
    # of frequency components, effectively removing high-frequency noise.
    cutoff = int(len(fft_vals) * 0.1)
    filter_mask = np.zeros_like(fft_vals)
    filter_mask[:cutoff] = 1
    filter_mask[-cutoff:] = 1  # The filter is symmetric for real-valued signals.

    # Apply the mask and perform the inverse Fourier transform (IFFT).
    filtered_fft_vals = fft_vals * filter_mask
    smoothed_abs_values = np.real(np.fft.ifft(filtered_fft_vals))

    # Reconstruct the clauses by rounding the smoothed values and re-applying
    # the original signs. Values are clipped to stay within the valid range [1, n].
    reconstructed_literals = np.round(np.clip(smoothed_abs_values, 1, n)).astype(int)
    reconstructed_literals = [val * sign for val, sign in zip(reconstructed_literals, signs)]

    # Re-assemble the flattened list of literals into clauses.
    new_clauses = []
    literal_idx = 0
    for clause in clauses:
        new_clause = []
        for _ in clause:
            new_clause.append(reconstructed_literals[literal_idx])
            literal_idx += 1
        new_clauses.append(new_clause)

    return new_clauses

def apply_laplace_smoothing(clauses, iterations=3):
    """
    Applies an iterative local averaging (Laplace-inspired smoothing)
    to the SAT clauses. This method models the problem as a discrete
    field and applies a diffusion-like process to smooth out local
    variations, thereby highlighting more global structural trends.

    Args:
        clauses (list): A list of clauses, where each clause is a list of literals.
        iterations (int): The number of times to apply the smoothing filter.

    Returns:
        list: The preprocessed list of clauses.
    """
    if not clauses:
        return []

    # Flatten the clauses and handle signs separately.
    flattened_literals = [lit for clause in clauses for lit in clause]
    signs = np.array([np.sign(lit) for lit in flattened_literals])
    arr = np.array([abs(lit) for lit in flattened_literals], dtype=float)

    # Apply smoothing repeatedly for a fixed number of iterations.
    for _ in range(iterations):
        smoothed_arr = arr.copy()
        for i in range(1, len(arr) - 1):
            # Each element is replaced by the average of its local neighbors,
            # analogous to a discretized Laplacian operator.
            smoothed_arr[i] = (arr[i-1] + arr[i] + arr[i+1]) / 3
        arr = smoothed_arr

    # Reconstruct the clauses with the smoothed values.
    reconstructed_literals = np.round(np.clip(arr, 1, n)).astype(int)
    reconstructed_literals = [val * sign for val, sign in zip(reconstructed_literals, signs)]

    # Re-assemble the flattened list of literals into clauses.
    new_clauses = []
    literal_idx = 0
    for clause in clauses:
        new_clause = []
        for _ in clause:
            new_clause.append(reconstructed_literals[literal_idx])
            literal_idx += 1
        new_clauses.append(new_clause)

    return new_clauses

def apply_entropy_resampling(clauses):
    """
    Applies an entropy-guided resampling method to the SAT clauses.
    This method is inspired by Entropy principles, where entropy measures
    the disorder of a system. By reducing the entropy of the literal distribution,
    this preprocessing aims to make the problem structure more regular and less random.

    Args:
        clauses (list): A list of clauses, where each clause is a list of literals.

    Returns:
        list: The preprocessed list of clauses.
    """
    if not clauses:
        return []

    # Flatten the clauses and handle signs separately.
    flattened_literals = [lit for clause in clauses for lit in clause]
    signs = np.array([np.sign(lit) for lit in flattened_literals])
    arr = np.array([abs(lit) for lit in flattened_literals])

    # Calculate the histogram and probability distribution of literals.
    hist, _ = np.histogram(arr, bins=np.arange(1, n + 2))
    p = hist / np.sum(hist)

    # Calculate the Shannon entropy of the literal distribution.
    arr_entropy = entropy(p)
    # Normalize the entropy for a defined range.
    normalized_entropy = arr_entropy / np.log(n + 1) if n > 0 else 0
    # The skew factor is based on the normalized entropy.
    skew_factor = 1.0 - normalized_entropy
    # Create a new, skewed probability distribution that favors less-random values.
    resample_dist = p + (1-p) * skew_factor
    resample_dist = resample_dist / np.sum(resample_dist)

    # Resample literals from the new, regularized distribution.
    reconstructed_literals = np.random.choice(
        np.arange(1, n + 1),
        size=len(flattened_literals),
        p=resample_dist
    )

    reconstructed_literals = [val * sign for val, sign in zip(reconstructed_literals, signs)]

    # Re-assemble the flattened list of literals into clauses.
    new_clauses = []
    literal_idx = 0
    for clause in clauses:
        new_clause = []
        for _ in clause:
            new_clause.append(reconstructed_literals[literal_idx])
            literal_idx += 1
        new_clauses.append(new_clause)

    return new_clauses

# Function: Generate a random 3-SAT instance
def generate_3sat_instance(n, m):
    """
    Generates a random 3-SAT CNF instance with n variables and m clauses.
    This is a standard procedure for creating instances in the study of NP problems.

    Args:
        n (int): The number of variables.
        m (int): The number of clauses.

    Returns:
        list: A list of clauses representing the CNF formula.
    """
    clauses = []
    for _ in range(m):
        # Randomly sample 3 distinct variables.
        vars = random.sample(range(1, n + 1), 3)
        clause = []
        for v in vars:
            # Assign a random sign (positive or negative literal) to each variable.
            clause.append(-v if random.random() < 0.5 else v)
        clauses.append(clause)
    return clauses

# --- 3. Main Experimental Loop ---
# Iterate through each constraint density 'r' to explore the solvability landscape.
for r in tqdm(r_values, desc=f"Running for n={n}"):
    m = int(r * n)

    # Run the experiment for each preprocessing method and the 'Raw' baseline.
    for method in results.keys():
        sat_count = 0
        total_time = 0.0

        # Perform multiple trials for a given (n, m) setting to get a robust average.
        for _ in range(instances_per_setting):
            # Generate the initial raw instance.
            cnf = generate_3sat_instance(n, m)

            # Apply the selected preprocessing method. 'deepcopy' ensures that
            # the original instance remains unaltered for other methods.
            processed_cnf = copy.deepcopy(cnf)
            if method == 'Fourier':
                processed_cnf = apply_fourier_low_pass(processed_cnf)
            elif method == 'Laplace':
                processed_cnf = apply_laplace_smoothing(processed_cnf)
            elif method == 'Entropy':
                processed_cnf = apply_entropy_resampling(processed_cnf)

            # The SAT solver requires integer literals.
            processed_cnf_int = [[int(literal) for literal in clause] for clause in processed_cnf]

            # Initialize and run the Glucose3 SAT solver.
            solver = Glucose3()
            for clause in processed_cnf_int:
                solver.add_clause(clause)

            start = time.time()
            sat = solver.solve()
            elapsed = time.time() - start

            if sat:
                sat_count += 1
            total_time += elapsed
            solver.delete()

        # Compute and save the average statistics for this (n, r) setting.
        sat_ratio = sat_count / instances_per_setting
        avg_time = total_time / instances_per_setting
        results[method]['sat_ratio'].append(sat_ratio)
        results[method]['avg_time'].append(avg_time)
        

# !pip install numpy matplotlib tqdm

# --- Import Required Libraries ---
# Import all essential libraries for the experiment.
import numpy as np
import matplotlib.pyplot as plt
import itertools
from tqdm import tqdm
import random
import copy
from scipy.stats import entropy

# --- 1. Experimental Configuration and Reproducibility ---
# A fixed random seed is set for both the 'random' and 'numpy' libraries.
# This is a critical step for ensuring that the sequence of pseudo-random numbers
# is identical on every run, which guarantees the reproducibility and scientific
# validity of the experimental results.
random.seed(42)
np.random.seed(42)

# --- 2. Preprocessing Functions (Adapted for Hypergraphs) ---

def apply_fourier_low_pass(hyperedges, n):
    """
    Applies a low-pass Fourier filter to the hypergraph vertex indices.
    This method models the problem instance as a one-dimensional signal and uses
    frequency-domain analysis to remove high-frequency, local variations. The goal
    is to smooth the problem structure and reveal its underlying macroscopic organization.

    Args:
        hyperedges (list): A list of hyperedges, where each hyperedge is a tuple of vertex indices.
        n (int): The total number of vertices in the hypergraph.

    Returns:
        list: The preprocessed list of hyperedges.
    """
    if not hyperedges:
        return []

    # Flatten the hyperedges into a single list of vertex indices.
    flattened_vertices = [v for edge in hyperedges for v in edge]

    # Perform a Fast Fourier Transform (FFT) on the vertex indices.
    fft_vals = np.fft.fft(np.array(flattened_vertices, dtype=float))

    # Create a simple low-pass filter mask. This filter retains only the lowest 10%
    # of frequency components, effectively removing high-frequency noise.
    cutoff = int(len(fft_vals) * 0.1)
    filter_mask = np.zeros_like(fft_vals)
    filter_mask[:cutoff] = 1
    filter_mask[-cutoff:] = 1 # The filter is symmetric for real-valued signals.

    # Apply the filter and perform the inverse Fourier transform (IFFT).
    filtered_fft_vals = fft_vals * filter_mask
    smoothed_vertices = np.real(np.fft.ifft(filtered_fft_vals))

    # Reconstruct the vertices by rounding the smoothed values and clipping them
    # to stay within the valid range of vertex indices [0, n-1].
    reconstructed_vertices = np.round(np.clip(smoothed_vertices, 0, n-1)).astype(int)

    # Re-assemble the hyperedges from the smoothed vertex list.
    new_hyperedges = []
    vertex_idx = 0
    # Assuming k-uniform hypergraph, where k is the size of the first hyperedge.
    edge_size = len(hyperedges[0]) if hyperedges else 0
    for _ in range(len(hyperedges)):
        new_edge = tuple(reconstructed_vertices[vertex_idx:vertex_idx + edge_size])
        new_hyperedges.append(new_edge)
        vertex_idx += edge_size

    return new_hyperedges

def apply_laplace_smoothing(hyperedges, n, iterations=3):
    """
    Applies an iterative local averaging (Laplace-inspired smoothing)
    to the hypergraph vertex indices. This method models the problem as a discrete
    field and applies a diffusion-like process to smooth out local
    variations, thereby highlighting more global structural trends.

    Args:
        hyperedges (list): A list of hyperedges, where each hyperedge is a tuple of vertex indices.
        n (int): The total number of vertices in the hypergraph.
        iterations (int): The number of times to apply the smoothing filter.

    Returns:
        list: The preprocessed list of hyperedges.
    """
    if not hyperedges:
        return []

    # Flatten the hyperedges into a list of vertex indices.
    flattened_vertices = [v for edge in hyperedges for v in edge]
    arr = np.array(flattened_vertices, dtype=float)

    # Apply smoothing repeatedly for a fixed number of iterations.
    for _ in range(iterations):
        smoothed_arr = arr.copy()
        for i in range(1, len(arr) - 1):
            # Each element is replaced by the average of its local neighbors,
            # analogous to a discretized Laplacian operator.
            smoothed_arr[i] = (arr[i-1] + arr[i] + arr[i+1]) / 3
        arr = smoothed_arr

    # Reconstruct the vertices with a valid range [0, n-1].
    reconstructed_vertices = np.round(np.clip(arr, 0, n-1)).astype(int)

    # Re-assemble the hyperedges.
    new_hyperedges = []
    vertex_idx = 0
    edge_size = len(hyperedges[0]) if hyperedges else 0
    for _ in range(len(hyperedges)):
        new_edge = tuple(reconstructed_vertices[vertex_idx:vertex_idx + edge_size])
        new_hyperedges.append(new_edge)
        vertex_idx += edge_size

    return new_hyperedges

def apply_Entropy_resampling(hyperedges, n):
    """
    Applies an entropy-guided resampling method to the hypergraph vertex indices.
    This method is inspired by Entropy principles, where entropy measures
    the disorder of a system. By reducing the entropy of the literal distribution,
    this preprocessing aims to make the problem structure more regular and less random.

    Args:
        hyperedges (list): A list of hyperedges, where each hyperedge is a tuple of vertex indices.
        n (int): The total number of vertices in the hypergraph.

    Returns:
        list: The preprocessed list of hyperedges.
    """
    if not hyperedges:
        return []

    # Flatten the hyperedges into a list of vertex indices.
    flattened_vertices = [v for edge in hyperedges for v in edge]
    arr = np.array(flattened_vertices)
    num_literals = len(arr)

    # Calculate the histogram and probability distribution of vertex indices.
    hist, _ = np.histogram(arr, bins=np.arange(0, n + 1))
    p = hist / np.sum(hist)

    # Calculate the Shannon entropy of the vertex distribution.
    arr_entropy = entropy(p)
    # Normalize the entropy to a defined range [0, 1].
    normalized_entropy = arr_entropy / np.log(n) if n > 1 else 0
    # The skew factor is based on the normalized entropy.
    skew_factor = 1.0 - normalized_entropy
    # Create a new, skewed probability distribution that favors less-random values.
    resample_dist = p + (1-p) * skew_factor
    resample_dist = resample_dist / np.sum(resample_dist)

    # Resample vertices from the new, regularized distribution.
    reconstructed_vertices = np.random.choice(
        np.arange(0, n),
        size=num_literals,
        p=resample_dist
    )

    # Re-assemble the hyperedges from the new vertex list.
    new_hyperedges = []
    vertex_idx = 0
    edge_size = len(hyperedges[0]) if hyperedges else 0
    for _ in range(len(hyperedges)):
        new_edge = tuple(reconstructed_vertices[vertex_idx:vertex_idx + edge_size])
        new_hyperedges.append(new_edge)
        vertex_idx += edge_size

    return new_hyperedges

# --- 3. Function: Generate random k-uniform hypergraph ---
def generate_hypergraph(n, m, k):
    """
    Generates a random k-uniform hypergraph with n vertices and m hyperedges.
    Each hyperedge is a set of k distinct vertices. This function is a standard
    tool for creating instances for combinatorial studies.

    Args:
        n (int): The number of vertices.
        m (int): The number of hyperedges.
        k (int): The uniformity (size) of each hyperedge.

    Returns:
        list: A list of tuples, where each tuple represents a hyperedge.
    """
    hyperedges = set()
    while len(hyperedges) < m:
        # Randomly choose k distinct vertices from n vertices.
        edge = tuple(sorted(np.random.choice(n, k, replace=False)))
        hyperedges.add(edge)
    return list(hyperedges)

# --- 4. Function: Check 2-colorability via brute-force ---
def is_2_colorable(n, hyperedges):
    """
    Checks if a given hypergraph is 2-colorable by trying all possible 2-colorings
    of its vertices. This method is exact but has exponential complexity, making it
    suitable only for small values of n (e.g., n <= 15).

    Args:
        n (int): The number of vertices.
        hyperedges (list): A list of hyperedges.

    Returns:
        bool: True if at least one valid coloring exists, False otherwise.
    """
    # Iterate through all 2^n possible colorings.
    for coloring in itertools.product([0, 1], repeat=n):
        valid = True
        for edge in hyperedges:
            colors = set(coloring[v] for v in edge)
            if len(colors) < 2:  # Check for a monochromatic edge.
                valid = False
                break
        if valid:
            return True
    return False

# --- 5. Experiment Parameters ---
# Define the core parameters for the experiment.
n = 12 # Number of vertices (fixed).
k = 3  # Uniformity of the hyperedges (fixed to 3).
m_n_ratios = np.arange(0.5, 5.1, 0.2) # Constraint density values (m/n).
trials = 100 # Number of trials per (k, ratio) combination.

# Dictionary to store the success rates for each preprocessing method.
results = {
    'Raw': [],
    'Fourier': [],
    'Laplace': [],
    'Entropy': []
}

# --- 6. Main Experimental Loop ---
# This loop iterates through each constraint density to generate and test
# hypergraph instances, collecting statistics on their 2-colorability.
for ratio in tqdm(m_n_ratios, desc=f"Processing k={k}"):
    m = int(ratio * n)

    # Run the experiment for each preprocessing method.
    for method in results.keys():
        success_count = 0
        for _ in range(trials):
            # Generate a new raw hypergraph.
            hyperedges = generate_hypergraph(n, m, k)

            # Apply preprocessing based on the method. A deep copy is used
            # to ensure the original instance is not modified for other methods.
            processed_hyperedges = copy.deepcopy(hyperedges)
            if method == 'Fourier':
                processed_hyperedges = apply_fourier_low_pass(processed_hyperedges, n)
            elif method == 'Laplace':
                processed_hyperedges = apply_laplace_smoothing(processed_hyperedges, n)
            elif method == 'Entropy':
                processed_hyperedges = apply_Entropy_resampling(processed_hyperedges, n)

            # Check the 2-colorability of the processed instance.
            if is_2_colorable(n, processed_hyperedges):
                success_count += 1

        success_rate = success_count / trials
        results[method].append(success_rate)