performance – Loop through the nearest switch and deletion neighbours of a Boolean assignment

My goal is to look for nearest neighbours in a Boolean-assigned mapping (a Python dictionary). For this purpose I’m looping through the candidates, starting from those with the closest distance. The code will exit the loop once it finds a neighbour that meets additional criteria. My question here is for best practices to efficiently loop through the candidates.


The data structure is an assignment from variables to two truth values True and False. On these data structures, one can perform a “switch” operation by switching an assigned truth value, and a “deletion” operation by which one deletes a variable from the assignment. Each operation increases the distance to the assignment by 1. In the example below, integers are used as variables for reasons of simplicity.

I’m currently building the list of candidates by using the product of the powerset of an assignment’s keys. For an assignment, the powerset of keys will contain subsets of the assignment keys, and the product of the powerset will consist of tuples of elements from the powerset. For example, for the assignment a = {0: True, 1: False}, one tuple in the product of the powerset will be (0, 1). In this tuple, I take the keys in the first element to be those for which we perform the “deletion” operation. The keys in the second element are those on which the “switch” operation is performed. So in this example, the element 0 should be deleted, and 1 switched. Other examples for tuples would be (0, {}) or ({0,1}, {}).

The problem

While the code runs well in assignment sizes of up to 10, it quickly reaches very long computation times after that. In particular, with an assignment of 20 variables, the search takes several hours, e.g.:

a20 = {i: choice((True, False)) for i in range(20)}

Example neighbours for an assignment with size = 2

For example, the assignment a = {0: True, 1: False} has the following neighbours:

With distance 1:

{0: False, 1: False} # Assignment for 0 switched 
{0: True, 1: True} # Assignment for 1 switched
{1: False} # Assignment for 0 deleted
{0: True} # Assignment for 1 deleted

With distance 2:

{0: False, 1: True} # Assignments for 0 and 1 switched
{1: True} # Assignment for 0 deleted, for 1 switched
{0: False} # Assignment for 1 deleted, for 0 switched
{} # Assignments for 0 and 1 deleted

My current implementation

from itertools import chain, combinations, product
from random import choice

def switch_deletion_neighbourhood(assignment, distance):
    # powerset definition from more-itertools
    powerset = chain.from_iterable(combinations(assignment, r) for r in range(len(assignment)+1))
    # all items from P(assignment) x P(assignment) are potential neighbours,
    # but only if their intersection is empty and their union is equal to a distance.
    candidates = ((set(j) for j in list(i)) for i in product(list(powerset), repeat=2))
    for c in candidates:
        if (not (c(0) & c(1))) and (len(c(0) | c(1)) == distance):
            yield c

# Let a be a simple toy assignment
a = {i: choice((True, False)) for i in range(2)}

# The loop to find near neighbours
for d in range(1, len(a)+1):
    print(f"These are the dictionaries with distance {d}")
    for c in switch_deletion_neighbourhood(a, d) :
        candidate = {**{k: a(k) for k in a if k not in c(0)}, 
                     **{k: not a(k) for k in c(1)}}
        # print() here serves as a dummy operation on the candidate