Cómo dividir una lista en pares de todas las formas posibles

Tengo una lista (digamos 6 elementos para simplificar)

L = [0, 1, 2, 3, 4, 5]

y quiero dividirlo en pares de TODAS las formas posibles. Muestro algunas configuraciones:

[(0, 1), (2, 3), (4, 5)]
[(0, 1), (2, 4), (3, 5)]
[(0, 1), (2, 5), (3, 4)]

y así. Aquí (a, b) = (b, a)y el orden de los pares no es importante, es decir

[(0, 1), (2, 3), (4, 5)] = [(0, 1), (4, 5), (2, 3)]

El número total de tales configuraciones es 1*3*5*...*(N-1)donde Nestá la longitud de mi lista.

¿Cómo puedo escribir un generador en Python que me brinde todas las configuraciones posibles para un arbitrario N?

Échale un vistazo itertools.combinations.

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

No creo que haya ninguna función en la biblioteca estándar que haga exactamente lo que necesitas. Con solo usar itertools.combinationspuede obtener una lista de todos los pares individuales posibles, pero en realidad no resuelve el problema de todas las combinaciones de pares válidas.

Podrías resolver esto fácilmente con:

import itertools
def all_pairs(lst):
    for p in itertools.permutations(lst):
        i = iter(p)
        yield zip(i,i)

Pero esto le dará duplicados ya que trata (a, b) y (b, a) como diferentes, y también da todos los ordenamientos de pares. Al final, pensé que es más fácil codificar esto desde cero que intentar filtrar los resultados, así que aquí está la función correcta.

def all_pairs(lst):
    if len(lst) < 2:
        yield []
        return
    if len(lst) % 2 == 1:
        # Handle odd length list
        for i in range(len(lst)):
            for result in all_pairs(lst[:i] + lst[i+1:]):
                yield result
    else:
        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:]):
                yield [pair] + rest

Es recursivo, por lo que se encontrará con problemas de pila con una lista larga, pero por lo demás hace lo que necesita.

>>> para x en all_pairs ([0,1,2,3,4,5]):
    imprimir 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)]

Qué tal esto:

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

o

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

Conceptualmente similar a la respuesta de @ shang, pero no supone que los grupos sean de tamaño 2:

import itertools

def generate_groups(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 generate_groups([x for x in lst if x not in group], n):
                yield [group] + groups

pprint(list(generate_groups([0, 1, 2, 3, 4, 5], 2)))

Esto produce:

[[(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)]]

Mi jefe probablemente no estará feliz de haber pasado un poco de tiempo en este divertido problema, pero aquí hay una buena solución que no necesita recursividad y utiliza itertools.product. Se explica en la cadena de documentos :). Los resultados parecen estar bien, pero no los he probado demasiado.

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

¡salud!

Pruebe la siguiente función de generador recursivo:

def pairs_gen(L):
    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 pairs_gen(L):
                list_of_pairs.insert(0, (first, second))
                yield list_of_pairs
            L.insert(i, second)
        L.insert(0, first)

Uso de ejemplo:

>>> for pairs in pairs_gen([0, 1, 2, 3, 4, 5]):
...     print pairs
...
[(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)]

Una función no recursiva para encontrar todos los pares posibles donde el orden no importa, es decir, (a, b) = (b, a)

def combinantorial(lst):
    count = 0
    index = 1
    pairs = []
    for element1 in lst:
        for element2 in lst[index:]:
            pairs.append((element1, element2))
        index += 1

    return pairs

Dado que no es recursivo, no experimentará problemas de memoria con listas largas.

Ejemplo de uso:

my_list = [1, 2, 3, 4, 5]
print(combinantorial(my_list))
>>>
[(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]

Hice una pequeña suite de pruebas para todas las soluciones compatibles. Tuve que cambiar un poco las funciones para que funcionaran en Python 3. Curiosamente, la función más rápida en PyPy es la función más lenta en Python 2/3 en algunos casos.

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

Todos parecen generar exactamente el mismo orden, por lo que los conjuntos no son necesarios, pero de esta manera es una prueba de futuro. Experimenté un poco con la conversión de Python 3, no siempre está claro dónde construir la lista, pero probé algunas alternativas y elegí la más rápida.

Estos son los resultados de la prueba comparativa:

% 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

Entonces digo, ve con la solución de gatoatigrado.

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

Uso:

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

Espero que esto ayude:

L = [0, 1, 2, 3, 4, 5]

[(i, j) para i en L para j en L]

salida:

[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5)]

Este código funciona cuando la longitud de la lista no es múltiplo de 2; emplea un truco para que funcione. Quizás haya mejores formas de hacer esto ... También asegura que los pares estén siempre en una tupla y que funcione si la entrada es una lista o una tupla.

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

L = [1, 1, 2, 3, 4]
answer = []
for i in range(len(L)):
    for j in range(i+1, len(L)):
        if (L[i],L[j]) not in answer:
            answer.append((L[i],L[j]))

print answer
[(1, 1), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

Espero que esto ayude

No es el más eficiente ni el más rápido, pero probablemente el más fácil. La última línea es una forma sencilla de deduplicar una lista en Python. En este caso, pares como (0,1) y (1,0) están en la salida. No estoy seguro de si consideraría esos duplicados o no.

l = [0, 1, 2, 3, 4, 5]
pairs = []
for x in l:
    for y in l:
        pairs.append((x,y))
pairs = list(set(pairs))
print(pairs)

Salida:

[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (3, 5), (4, 0), (4, 1), (4, 2), (4, 3), (4, 4), (4, 5), (5, 0), (5, 1), (5, 2), (5, 3), (5, 4), (5, 5)]