Pairwise Combinations Generator

Question

Below is an algorithm to generate all pairwise combinations for a set of random variables. See here for an explanation of what constitutes a minimal all-pairs set. The algorithm below works but I feel that it is inefficient. Any suggestions would be welcome.

from operator import itemgetter
from itertools import combinations, product, zip_longest, chain, permutations


def pairwise(*variables, **kwargs):
    num_vars = len(variables)

    #Organize the variable states into pairs for comparisons
    indexed_vars = sorted(
        ([(index, v) for v in vals] for index, vals in enumerate(variables)),
        key=len,
        reverse=True)

    var_combos = combinations(range(num_vars), 2)
    var_products = (product(indexed_vars[i], indexed_vars[j]) for i, j in var_combos)
    vars = chain.from_iterable(zip_longest(*var_products))

    #Initialize the builder list
    builders = []
    seen_pairs = set()

    #Main algorithm loop
    for pair in vars:
        if not pair or pair in seen_pairs:
            continue

        d_pair = dict(pair)

        #Linear search through builders to find an empty slot
        #First pass: look for sets that have intersections
        for builder in builders:
            intersection = builder.keys() & d_pair.keys()
            if len(intersection) == 1:
                v = intersection.pop()
                if builder[v] == d_pair[v]:
                    builder.update(d_pair)
                    #Update seen pairs
                    seen_pairs.update(combinations(builder.items(), 2))
                    break
        else:
            #Second Pass
            for builder in builders:
                intersection = builder.keys() & d_pair.keys()
                if not len(intersection):
                    builder.update(d_pair)
                    #Update seen pairs
                    seen_pairs.update(combinations(builder.items(), 2))
                    break
            else:
                #No empty slots/pairs identified. Make a new builder
                builders.append(d_pair)
                seen_pairs.add(pair)

    #Fill in remaining values
    complete_set = set(range(num_vars))
    defaults = {var[0][0]: var[0][1] for var in indexed_vars}

    for builder in builders:
        if len(builder) == num_vars:
            yield tuple(val for index, val in sorted(builder.items()))
        else:
            for key in complete_set - builder.keys():
                builder[key] = defaults[key]
            yield tuple(val for index, val in sorted(builder.items()))

Usage Example:

u_vars = [
    [1, 2, 3, 4],
    ["A", "B", "C"],
    ["a", "b"],
    ]

result = list(pairwise(*u_vars))
print(result) #prints list of length 12

Answer 1

This is not generating correct pairwise combinations.

Input data

[['Requests'],
    ['Create','Edit'],
    ['Contact Name','Email','Phone','Subject','Description','Status','Product Name','Request Owner','Created By','Modified By','Request Id','Resolution','To Address','Account Name','Priority','Channel','Category','Sub Category'],
    ['None','is','isn\'t','contains','doesn\'t contain','starts with','ends with','is empty','is not empty'],
    ['Contact Name','Email','Phone','Subject','Description','Status','Product Name','Request Owner','Mark Spam','Resolution','To Address','Due Date','Priority','Channel','Category','Sub Category']]

Result by Microsoft PICT

http://pastebin.com/cZdND9UA

Result by your code http://pastebin.com/EC6xv4vG

This generates only for NONE in most of cases such as this

Requests Create Account Name None Category Requests Create Account Name None Channel Requests Create Account Name None Description Requests Create Account Name None Due Date