How to select element from two complex number lists to get minimum magnitude for their sum

Let's slightly reinterpret your problem.

Instead of strictly choosing one element from either of the two lists, start with an initial state where you've selected all elements from list1. The sum of this selection is your offset value, which we'll call C. Next, create a new list called list3, defined as list3 = list2 - list1. With this formulation, your problem becomes choosing any number of elements from list3 whose sum closely approximates -C. This is precisely the Subset Sum Problem.

Although this is computationally intensive, there are several significantly more efficient methods than brute-force. A well-known approach mentioned in the above article (also suggested by @Robert) is the "meet-in-the-middle" technique.

This technique splits the original set into two subsets and calculates all possible combinations within each subset. Although this part is brute-force, it becomes practical because each subset is half the original size. Once all combinations have been calculated, the next step is to select one item from each subset that most cancel each other out. Several methods exist for this, but I prefer using scipy's KDTree for simplicity.

Here's a naive implementation to help understand the logic. (Note: this won't work for n=51)

def meetinthemiddlenaive(list1, list2):
    # Split the lists into two halves.
    n = len(list1)
    halfn = n // 2
    list1head, list1tail = list1[:halfn], list1[halfn:]
    list2head, list2tail = list2[:halfn], list2[halfn:]
    # Calculate all combinations and their sums of each half.
    # This is technically a brute-force approach, but the length of the lists are small enough to be feasible.
    headcombinations = [(sum(c), c) for c in itertools.product(zip(list1_head, list2_head))]
    tail_combinations = [(sum(c), c) for c in itertools.product(zip(list1tail, list2tail))]
    # Build a KDTree and search for the nearest points between the two halves.
    def asrealxy(c):
        # Convert a complex number to a real value pair (x, y).
        # This is required for the KDTree to work correctly.
        return c.real, c.imag
    headpoints = np.array([asrealxy(p) for p,  in headcombinations])
    tailpoints = np.array([asrealxy(p) for p,  in tailcombinations])
    headtree = KDTree(headpoints)
    distances, headindexes = headtree.query(-tailpoints)
    #                                         ^ Searching for the zero-sum combinations.
    # The above searches for a list of nearest neighbors for each point in head.
    # So, we need to find the nearest one in that list.
    tailindex = distances.argmin()
    headindex = headindexes[tailindex]
    bestcombination = headcombinations[headindex][1] + tailcombinations[tailindex][1]
    return abs(sum(bestcombination)), list(bestcombination)

Although computationally improved, this naive implementation is still inefficient and memory-intensive. I'll skip the details since it's a programming detail, but I've further optimized this using moreitertools and numba.

import itertools
import math
import random
import time
import moreitertools
import numpy as np
from numba import jit
from scipy.spatial import KDTree
def generatelist(n):
    return [complex(random.uniform(-10, 10), random.uniform(-10, 10)) for  in range(n)]
def baseline(list1, list2):
    assert len(list1) == len(list2)
    n = len(list1)
    minmagnitude = math.inf
    bestcombination = None
    for choice in itertools.product([0, 1], repeat=n):
        current = [list1[i] if bit == 0 else list2[i] for i, bit in enumerate(choice)]
        total = sum(current)
        mag = abs(total)
        if mag < minmagnitude:
            minmagnitude = mag
            bestcombination = current
    return minmagnitude, bestcombination
def meetinthemiddlenaive(list1, list2):
    # Split the lists into two halves.
    n = len(list1)
    halfn = n // 2
    list1head, list1tail = list1[:halfn], list1[halfn:]
    list2head, list2tail = list2[:halfn], list2[halfn:]
    # Calculate all combinations and their sums of each half.
    # This is technically a brute-force approach, but the length of the lists are small enough to be feasible.
    headcombinations = [(sum(c), c) for c in itertools.product(*zip(list1head, list2head))]
    tailcombinations = [(sum(c), c) for c in itertools.product(zip(list1_tail, list2_tail))]
    # Build a KDTree and search for the nearest points between the two halves.
    def as_real_xy(c):
        # Convert a complex number to a real value pair (x, y).
        # This is required for the KDTree to work correctly.
        return c.real, c.imag
    head_points = np.array([as_real_xy(p) for p, _ in head_combinations])
    tail_points = np.array([as_real_xy(p) for p, _ in tail_combinations])
    head_tree = KDTree(head_points)
    distances, head_indexes = head_tree.query(-tail_points)
    #                                         ^ Searching for the zero-sum combinations.
    # The above searches for a list of nearest neighbors for each point in head.
    # So, we need to find the nearest one in that list.
    tail_index = distances.argmin()
    head_index = head_indexes[tail_index]
    best_combination = head_combinations[head_index][1] + tail_combinations[tail_index][1]
    return abs(sum(best_combination)), list(best_combination)
@jit(cache=True)
def product_sum(arr_x, arr_y):
    """Calculate the sum of all combinations of two lists.
    Equivalent to: [sum(current) for current in itertools.product(zip(arrx, arry))]
    """
    n = len(arrx)
    totalcombinations = 1 > (n - j - 1)) & 1:
                currentsum += arry[j]
            else:
                currentsum += arrx[j]
        out[i] = currentsum
    return out
def meetinthemiddleoptimized(list1, list2):
    n = len(list1)
    halfn = n // 2
    list1head, list1tail = list1[:halfn], list1[halfn:]
    list2head, list2tail = list2[:halfn], list2[halfn:]
    # Keeping the combinations themselves consumes a lot of memory, so we only keep the sums.
    headpoints = productsum(np.array(list1head), np.array(list2head))
    tailpoints = productsum(np.array(list1tail), np.array(list2tail))
    def asrealxy(arr):
        # Equivalent to np.array([(p.real, p.imag) for p in arr]) but much faster.
        return arr.view(f"f{arr.real.itemsize}").reshape(-1, 2)
    headtree = KDTree(asrealxy(headpoints), balancedtree=False)  # Set False if the inputs are mostly random.
    distances, headindexes = headtree.query(-asrealxy(tailpoints), workers=-1)  # -1 to use all CPUs.
    tailindex = distances.argmin()
    headindex = headindexes[tailindex]
    # nthproduct is equivalent to itertools.product(...)[index].
    # With this, we can directly obtain the combination without iterating through all combinations.
    headcombination = moreitertools.nthproduct(headindex, *zip(list1head, list2head))
    tailcombination = moreitertools.nthproduct(tailindex, *zip(list1tail, list2tail))
    bestcombination = headcombination + tailcombination
    return abs(sum(bestcombination)), list(bestcombination)
def test():
    for n in range(2, 15):
        for seed in range(10):
            random.seed(seed)
            list1 = generatelist(n)
            list2 = generatelist(n)
            expected = baseline(list1, list2)
            actual = meetinthemiddlenaive(list1, list2)
            assert expected == actual, f"Naive results do not match! {n=}, {seed=}"
            actual = meetinthemiddleoptimized(list1, list2)
            assert expected == actual, f"Optimized results do not match! {n=}, {seed=}"
    print("All tests passed!")
def benchmark():
    n = 51
    random.seed(0)
    list1 = generatelist(n)
    list2 = generatelist(n)
    started = time.perfcounter()
     = meetinthemiddleoptimized(list1, list2)
    elapsed = time.perf_counter() - started
    print(f"n={n}, elapsed={elapsed:.0f} sec")
if name == "main":
    test()
    benchmark()

This solution solved n=51 in less than 30 seconds on my PC.