some utilities for walking over all possible sets of pairs with a minimum number of creations / deletions

pairwise.py

import itertools, math


def pairwise_walk(items):
    '''
    given a list of items, return a list of instructions of which
    ordered pairs of relationships to add or remove, in order to
    go over every possible set of pairwise relationships existing
    or not existing while only adding or removing one at a time

    assumes that reflexive pairs of an item to itself should be excluded

    >>> pairwise_walk('abc')
    [('+', ('a', 'b')), ('+', ('a', 'c')), ('-', ('a', 'b')), ('+', ('b', 'c')),
     ('+', ('a', 'b')), ('-', ('a', 'c')), ('-', ('a', 'b'))]
    '''
    pairs = [
        pair for pair in itertools.product(items[:-1], items[1:])
        if pair[0] != pair[1]]
    walk = gray_walk(len(pairs))
    return [(step[0], pairs[step[1]]) for step in walk]


def gray_walk(n):
    '''
    given a number of elements n, returns a "gray walk"
    which uses gray encoding to add or remove one element'
    at a time such that each possible permutation of n
    is visited once

    (assuming you start from having no elements)

    elements are encoded as '+' or '-' for add or remove,
    and then the integer of the index

    >>> gray_walk(3)
    [('+', 0), ('+', 1), ('-', 0), ('+', 2), ('+', 0), ('-', 1), ('-', 0)]

    this should be interpreted as
    "add the 0th element, add the 1st element, remove the 0th element"
    '''
    # https://en.wikipedia.org/wiki/Gray_code
    gray_codes = [i ^ (i >> 1) for i in range(2**n)]
    # >>> ["{:03b}".format(i ^ (i >> 1)) for i in range(2**3)]
    # ['000', '001', '011', '010', '110', '111', '101', '100']
    walk = []
    for pre, post in zip(gray_codes[:-1], gray_codes[1:]):
        if post > pre:
            walk.append(('+', int(math.log(post - pre, 2))))
        if pre > post:
            walk.append(('-', int(math.log(pre - post, 2))))
    return walk