gistfile1.py

import random

def hard_partition_pairs(n: int):
    """
    Construct n positive ints (n even) with a unique equal-sum bipartition
    where each subset contains n/2 elements.

    Returns
    -------
    A, B : lists
        The unique (up to swapping) perfect partition.
    """
    assert n % 2 == 0 and n >= 4, "n must be an even integer ≥ 4"

    k = n // 2                       # number of pairs

    # ----- Step 1: craft super‑increasing pair‑differences -----------------
    diffs = [1]                      # d0 = 1
    for i in range(1, k - 1):        # d1 … d(k‑2) double each time
        diffs.append(diffs[-1] * 2)
    diffs.append(sum(diffs))         # dk‑1  =  sum(d0 … d(k‑2))

    # Now the only way ∑(±diff_i) = 0 is   [+…+ −]   (or the global swap).

    # ----- Step 2: assign concrete positive values -------------------------
    t = diffs[-1] + 1                # base so that every low = t − diff > 0
    A, B = [], []

    for i, d in enumerate(diffs):
        high, low = t + d, t - d
        if i == k - 1:               # last pair carries the balancing minus
            A.append(low)            #  …so A gets the smaller element here
            B.append(high)
        else:                        # all earlier pairs are '+'
            A.append(high)
            B.append(low)

    return A, B



n = 100
A, B = hard_partition_pairs(n)

print('sum(A) =',sum(A), ' sum(B) =', sum(B), 'same ?', sum(A)==sum(B))

lst = A + B
random.shuffle(lst)



# Try to solve
result = pseudo_random_partition(lst, max_attempts=100_000_000)
if result:
    left, right = result
    print(f"Left (Group 1): {left}, sum = {sum(left)}")
    print(f"Right (Group 2): {right}, sum = {sum(right)}")
else:
    print("This set is unbalanced")