# Pairwise Combinations Generator

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)

#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


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