Comment scinder une liste de paires de toutes les façons possibles

Prendre un coup d'oeil à itertools.combinaisons.

matt@stanley:~$ python
Python 2.6.5 (r265:79063, Apr 16 2010, 13:57:41) 
[GCC 4.4.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import itertools
>>> list(itertools.combinations(range(6), 2))
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]

Comment à ce sujet:

items = ["me", "you", "him"]
[(items[i],items[j]) for i in range(len(items)) for j in range(i+1, len(items))]

[('me', 'you'), ('me', 'him'), ('you', 'him')]

ou

items = [1, 2, 3, 5, 6]
[(items[i],items[j]) for i in range(len(items)) for j in range(i+1, len(items))]

[(1, 2), (1, 3), (1, 5), (1, 6), (2, 3), (2, 5), (2, 6), (3, 5), (3, 6), (5, 6)]

Mon patron ne va probablement pas à être heureux, j'ai passé un peu de temps sur ce problème amusant, mais voici une belle solution qui n'a pas besoin de la récursivité, et utilise itertools.product. C'est expliqué dans la docstring :). Les résultats semblent OK, mais je ne l'ai pas testé trop.

import itertools
def all_pairs(lst):
"""Generate all sets of unique pairs from a list `lst`.
This is equivalent to all _partitions_ of `lst` (considered as an indexed
set) which have 2 elements in each partition.
Recall how we compute the total number of such partitions. Starting with
a list
[1, 2, 3, 4, 5, 6]
one takes off the first element, and chooses its pair [from any of the
remaining 5].  For example, we might choose our first pair to be (1, 4).
Then, we take off the next element, 2, and choose which element it is
paired to (say, 3). So, there are 5 * 3 * 1 = 15 such partitions.
That sounds like a lot of nested loops (i.e. recursion), because 1 could
pick 2, in which case our next element is 3. But, if one abstracts "what
the next element is", and instead just thinks of what index it is in the
remaining list, our choices are static and can be aided by the
itertools.product() function.
"""
N = len(lst)
choice_indices = itertools.product(*[
xrange(k) for k in reversed(xrange(1, N, 2)) ])
for choice in choice_indices:
# calculate the list corresponding to the choices
tmp = lst[:]
result = []
for index in choice:
result.append( (tmp.pop(0), tmp.pop(index)) )
yield result

cheers!

def f(l):
if l == []:
yield []
return
ll = l[1:]
for j in range(len(ll)):
for end in f(ll[:j] + ll[j+1:]):
yield [(l[0], ll[j])] + end

Utilisation:

for x in f([0,1,2,3,4,5]):
print x
>>> 
[(0, 1), (2, 3), (4, 5)]
[(0, 1), (2, 4), (3, 5)]
[(0, 1), (2, 5), (3, 4)]
[(0, 2), (1, 3), (4, 5)]
[(0, 2), (1, 4), (3, 5)]
[(0, 2), (1, 5), (3, 4)]
[(0, 3), (1, 2), (4, 5)]
[(0, 3), (1, 4), (2, 5)]
[(0, 3), (1, 5), (2, 4)]
[(0, 4), (1, 2), (3, 5)]
[(0, 4), (1, 3), (2, 5)]
[(0, 4), (1, 5), (2, 3)]
[(0, 5), (1, 2), (3, 4)]
[(0, 5), (1, 3), (2, 4)]
[(0, 5), (1, 4), (2, 3)]

J'ai fait un petit test de suite pour toutes les solutions conformes. J'ai dû changer de fonctions un peu pour les faire travailler en Python 3. Fait intéressant, la manière la plus rapide de la fonction de PyPy est le plus lent de la fonction en Python 2/3 dans certains cas.

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])
"""

Ils semblent tous pour générer le même ordre, de sorte que les ensembles ne sont pas nécessaires, mais de cette façon c'est l'avenir. J'ai expérimenté un peu avec le Python 3 de la conversion, il n'est pas toujours clair de savoir où construire la liste, mais j'ai essayé quelques solutions de rechange et a choisi la manière la plus rapide.

Voici les résultats de la référence:

% 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

Donc, je dis, allez-y avec gatoatigrado de la solution.

Ce code fonctionne lorsque la longueur de la liste n'est pas un multiple de 2, elle emploie un hack pour le faire fonctionner. Peut-être il ya de meilleures façons de le faire...Il s'assure également que les paires sont toujours dans un n-uplet et qu'il fonctionne si l'entrée est une liste ou un tuple.

def all_pairs(lst):
"""Return all combinations of pairs of items of ``lst`` where order
within the pair and order of pairs does not matter.
Examples
========
>>> for i in range(6):
...  list(all_pairs(range(i)))
...
[[()]]
[[(0,)]]
[[(0, 1)]]
[[(0, 1), (2,)], [(0, 2), (1,)], [(0,), (1, 2)]]
[[(0, 1), (2, 3)], [(0, 2), (1, 3)], [(0, 3), (1, 2)]]
[[(0, 1), (2, 3), (4,)], [(0, 1), (2, 4), (3,)], [(0, 1), (2,), (3, 4)], [(0, 2)
, (1, 3), (4,)], [(0, 2), (1, 4), (3,)], [(0, 2), (1,), (3, 4)], [(0, 3), (1, 2)
, (4,)], [(0, 3), (1, 4), (2,)], [(0, 3), (1,), (2, 4)], [(0, 4), (1, 2), (3,)],
[(0, 4), (1, 3), (2,)], [(0, 4), (1,), (2, 3)], [(0,), (1, 2), (3, 4)], [(0,),
(1, 3), (2, 4)], [(0,), (1, 4), (2, 3)]]
Note that when the list has an odd number of items, one of the
pairs will be a singleton.
References
==========
http://stackoverflow.com/questions/5360220/
how-to-split-a-list-into-pairs-in-all-possible-ways
"""
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 = list(lst) + [i]
PAD = i
break
else:
while chr(i) in lst:
i += 1
PAD = chr(i)
lst = list(lst) + [PAD]
else:
PAD = False
a = lst[0]
for i in range(1, len(lst)):
pair = (a, lst[i])
for rest in all_pairs(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