UPDATE:
There are now four answers including my own answer, pairs3.
The following script checks and benchmarks the solutions.
import timeit
import gc
from itertools import product, combinations, chain
from pprint import pprint as pp
""" This script checks and benchmarks the solutions. """
# Solution offered by @saquintes
def pairs1(list1, list2):
return list(set((tuple(sorted(t)) for t in product(list1, list2)
if t[0] != t[1])))
# Solution offered by @constantstranger
def pairs2(list1, list2):
cache = set()
return [(cache.add((x,y)), (x,y))[-1] for x in list1 for y in list2
if not (x==y or (y,x) in cache)]
# My solution
def pairs3(list1, list2):
res = dict()
for x,y in product(list1,list2):
if not (x == y or res.get((y,x))):
res[(x,y)] = 1
return list(res.keys())
# This is the very clever and exceedingly fast
# solution offered by @Kelly Bundy.
# (See @Kelly Bundy's post for a version that returns an iterator!)
def pairs4(list1, list2):
a = {*list1}
b = {*list2}
ab = a & b
return [
*product(a, b-a),
*product(a-b, ab),
*combinations(ab, 2)
]
def check(fn, list1, list2):
""" Prints the output of function fn """
print('\nFunction', fn.__name__, 'output:')
res = fn(list1, list2)
pp(res)
def run_checks(functions):
""" Passes lists to each function in functions and prints the results """
for fn in functions:
print('\n------------------------------------------------\n')
print('Function:', fn.__name__, '\n')
print('Combinations of a list with itself:')
list1 = ['A', 'B', 'C']
list2 = ['A', 'B', 'C']
print('list1:', list1)
print('list2:', list2)
check(fn, list1, list1)
print('\nCombinations of Two lists with a common element:')
list1 = ['A', 'B', 'C']
list2 = ['A', 'D', 'E']
print('list1:', list1)
print('list2:', list2)
check(fn, list1, list2)
def benchmark(fn, list1, list2, iterations):
def callit():
fn(list1, list2)
gc.collect()
t = timeit.timeit(callit, number=iterations)
print('Function', fn.__name__, 'time:', f'{t:.2f} secs')
def run_benchmarks(functions, list1, list2, iterations):
print('\nRunning', f'{iterations}', 'iterations per run repeated 3 times\n')
for fn in functions:
benchmark(fn, list1, list2, iterations)
benchmark(fn, list1, list2, iterations)
benchmark(fn, list1, list2, iterations)
print()
print('\n-------------- Check performance --------------\n')
list1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
list2 = [0, 1, 2, 3, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35]
print('list1:', list1)
print('list2:', list2)
run_benchmarks([pairs1, pairs2, pairs3, pairs4], list1, list2, 100000)
print('-------------- Check correctness --------------\n')
run_checks([pairs1, pairs2, pairs3, pairs4])
Output:
-------------- Check performance --------------
list1: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
list2: [0, 1, 2, 3, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35]
Running 100000 iterations per run repeated 3 times
Function pairs1 time: 20.61 secs
Function pairs1 time: 20.53 secs
Function pairs1 time: 20.54 secs
Function pairs2 time: 10.69 secs
Function pairs2 time: 10.69 secs
Function pairs2 time: 10.68 secs
Function pairs3 time: 9.87 secs
Function pairs3 time: 9.87 secs
Function pairs3 time: 9.89 secs
Function pairs4 time: 1.44 secs
Function pairs4 time: 1.44 secs
Function pairs4 time: 1.44 secs
-------------- Check correctness --------------
------------------------------------------------
Function: pairs1
Combinations of a list with itself:
list1: ['A', 'B', 'C']
list2: ['A', 'B', 'C']
Function pairs1 output:
[('B', 'C'), ('A', 'C'), ('A', 'B')]
Combinations of Two lists with a common element:
list1: ['A', 'B', 'C']
list2: ['A', 'D', 'E']
Function pairs1 output:
[('C', 'E'),
('B', 'D'),
('A', 'B'),
('A', 'E'),
('B', 'E'),
('C', 'D'),
('A', 'C'),
('A', 'D')]
------------------------------------------------
Function: pairs2
Combinations of a list with itself:
list1: ['A', 'B', 'C']
list2: ['A', 'B', 'C']
Function pairs2 output:
[('A', 'B'), ('A', 'C'), ('B', 'C')]
Combinations of Two lists with a common element:
list1: ['A', 'B', 'C']
list2: ['A', 'D', 'E']
Function pairs2 output:
[('A', 'D'),
('A', 'E'),
('B', 'A'),
('B', 'D'),
('B', 'E'),
('C', 'A'),
('C', 'D'),
('C', 'E')]
------------------------------------------------
Function: pairs3
Combinations of a list with itself:
list1: ['A', 'B', 'C']
list2: ['A', 'B', 'C']
Function pairs3 output:
[('A', 'B'), ('A', 'C'), ('B', 'C')]
Combinations of Two lists with a common element:
list1: ['A', 'B', 'C']
list2: ['A', 'D', 'E']
Function pairs3 output:
[('A', 'D'),
('A', 'E'),
('B', 'A'),
('B', 'D'),
('B', 'E'),
('C', 'A'),
('C', 'D'),
('C', 'E')]
------------------------------------------------
Function: pairs4
Combinations of a list with itself:
list1: ['A', 'B', 'C']
list2: ['A', 'B', 'C']
Function pairs4 output:
[('A', 'C'), ('A', 'B'), ('C', 'B')]
Combinations of Two lists with a common element:
list1: ['A', 'B', 'C']
list2: ['A', 'D', 'E']
Function pairs4 output:
[('A', 'E'),
('A', 'D'),
('C', 'E'),
('C', 'D'),
('B', 'E'),
('B', 'D'),
('C', 'A'),
('B', 'A')]
