I made a small test suite for all the compliant solutions. I had to change the functions a bit to get them to work in Python 3. Interestingly, the fastest function in PyPy is the slowest function in Python 2/3 in some cases.
import itertools
import time
from collections import OrderedDict
def tokland_org(lst, n):
if not lst:
yield []
else:
for group in (((lst[0],) + xs) for xs in itertools.combinations(lst[1:], n-1)):
for groups in tokland_org([x for x in lst if x not in group], n):
yield [group] + groups
tokland = lambda x: tokland_org(x, 2)
def gatoatigrado(lst):
N = len(lst)
choice_indices = itertools.product(*[
range(k) for k in reversed(range(1, N, 2)) ])
for choice in choice_indices:
# calculate the list corresponding to the choices
tmp = list(lst)
result = []
for index in choice:
result.append( (tmp.pop(0), tmp.pop(index)) )
yield result
def shang(X):
lst = list(X)
if len(lst) < 2:
yield lst
return
a = lst[0]
for i in range(1,len(lst)):
pair = (a,lst[i])
for rest in shang(lst[1:i]+lst[i+1:]):
yield [pair] + rest
def smichr(X):
lst = list(X)
if not lst:
yield [tuple()]
elif len(lst) == 1:
yield [tuple(lst)]
elif len(lst) == 2:
yield [tuple(lst)]
else:
if len(lst) % 2:
for i in (None, True):
if i not in lst:
lst = lst + [i]
PAD = i
break
else:
while chr(i) in lst:
i += 1
PAD = chr(i)
lst = lst + [PAD]
else:
PAD = False
a = lst[0]
for i in range(1, len(lst)):
pair = (a, lst[i])
for rest in smichr(lst[1:i] + lst[i+1:]):
rv = [pair] + rest
if PAD is not False:
for i, t in enumerate(rv):
if PAD in t:
rv[i] = (t[0],)
break
yield rv
def adeel_zafar(X):
L = list(X)
if len(L) == 2:
yield [(L[0], L[1])]
else:
first = L.pop(0)
for i, e in enumerate(L):
second = L.pop(i)
for list_of_pairs in adeel_zafar(L):
list_of_pairs.insert(0, (first, second))
yield list_of_pairs
L.insert(i, second)
L.insert(0, first)
if __name__ =="__main__":
import timeit
import pprint
candidates = dict(tokland=tokland, gatoatigrado=gatoatigrado, shang=shang, smichr=smichr, adeel_zafar=adeel_zafar)
for i in range(1,7):
results = [ frozenset([frozenset(x) for x in candidate(range(i*2))]) for candidate in candidates.values() ]
assert len(frozenset(results)) == 1
print("Times for getting all permutations of sets of unordered pairs consisting of two draws from a 6-element deck until it is empty")
times = dict([(k, timeit.timeit('list({0}(range(6)))'.format(k), setup="from __main__ import {0}".format(k), number=10000)) for k in candidates.keys()])
pprint.pprint([(k, "{0:.3g}".format(v)) for k,v in OrderedDict(sorted(times.items(), key=lambda t: t[1])).items()])
print("Times for getting the first 2000 permutations of sets of unordered pairs consisting of two draws from a 52-element deck until it is empty")
times = dict([(k, timeit.timeit('list(islice({0}(range(52)), 800))'.format(k), setup="from itertools import islice; from __main__ import {0}".format(k), number=100)) for k in candidates.keys()])
pprint.pprint([(k, "{0:.3g}".format(v)) for k,v in OrderedDict(sorted(times.items(), key=lambda t: t[1])).items()])
"""
print("The 10000th permutations of the previous series:")
gens = dict([(k,v(range(52))) for k,v in candidates.items()])
tenthousands = dict([(k, list(itertools.islice(permutations, 10000))[-1]) for k,permutations in gens.items()])
for pair in tenthousands.items():
print(pair[0])
print(pair[1])
"""
They all seem to generate the exact same order, so the sets aren't necessary, but this way it's future proof. I experimented a bit with the Python 3 conversion, it is not always clear where to construct the list, but I tried some alternatives and chose the fastest.
Here are the benchmark results:
% echo "pypy"; pypy all_pairs.py; echo "python2"; python all_pairs.py; echo "python3"; python3 all_pairs.py
pypy
Times for getting all permutations of sets of unordered pairs consisting of two draws from a 6-element deck until it is empty
[('gatoatigrado', '0.0626'),
('adeel_zafar', '0.125'),
('smichr', '0.149'),
('shang', '0.2'),
('tokland', '0.27')]
Times for getting the first 2000 permutations of sets of unordered pairs consisting of two draws from a 52-element deck until it is empty
[('gatoatigrado', '0.29'),
('adeel_zafar', '0.411'),
('smichr', '0.464'),
('shang', '0.493'),
('tokland', '0.553')]
python2
Times for getting all permutations of sets of unordered pairs consisting of two draws from a 6-element deck until it is empty
[('gatoatigrado', '0.344'),
('adeel_zafar', '0.374'),
('smichr', '0.396'),
('shang', '0.495'),
('tokland', '0.675')]
Times for getting the first 2000 permutations of sets of unordered pairs consisting of two draws from a 52-element deck until it is empty
[('adeel_zafar', '0.773'),
('shang', '0.823'),
('smichr', '0.841'),
('tokland', '0.948'),
('gatoatigrado', '1.38')]
python3
Times for getting all permutations of sets of unordered pairs consisting of two draws from a 6-element deck until it is empty
[('gatoatigrado', '0.385'),
('adeel_zafar', '0.419'),
('smichr', '0.433'),
('shang', '0.562'),
('tokland', '0.837')]
Times for getting the first 2000 permutations of sets of unordered pairs consisting of two draws from a 52-element deck until it is empty
[('smichr', '0.783'),
('shang', '0.81'),
('adeel_zafar', '0.835'),
('tokland', '0.969'),
('gatoatigrado', '1.3')]
% pypy --version
Python 2.7.12 (5.6.0+dfsg-0~ppa2~ubuntu16.04, Nov 11 2016, 16:31:26)
[PyPy 5.6.0 with GCC 5.4.0 20160609]
% python3 --version
Python 3.5.2
So I say, go with gatoatigrado's solution.
