Comment diviser une liste en paires de toutes les façons possibles

Question

J'ai une liste (disons 6 éléments pour simplifier)

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

et je veux le diviser en paires dans TOUS des moyens possibles. Je montre quelques configurations :

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

et ainsi de suite. Ici (a, b) = (b, a) et l'ordre des paires n'est pas important, c'est-à-dire

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

Le nombre total de ces configurations est de 1*3*5*...*(N-1) où N est la longueur de ma liste.

Comment puis-je écrire un générateur en Python qui me donne toutes les configurations possibles pour un objet arbitraire ? N ?

Answer 1

Jetez un coup d'œil à 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)]

Answer 2

Je ne pense pas qu'il existe une fonction dans la bibliothèque standard qui fasse exactement ce dont vous avez besoin. Il suffit d'utiliser itertools.combinations permet d'obtenir une liste de toutes les paires individuelles possibles, mais ne résout pas le problème de toutes les combinaisons de paires valides.

Vous pouvez facilement résoudre ce problème avec :

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

Mais vous obtiendrez des doublons, car il traite (a,b) et (b,a) comme différents, et donne également tous les ordres de paires. Finalement, je me suis dit qu'il était plus facile de coder cela à partir de zéro que d'essayer de filtrer les résultats, donc voici la fonction correcte.

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

Il est récursif, ce qui pose des problèmes de pile avec une longue liste, mais il fait autrement ce dont vous avez besoin.

\>>> for x in all\_pairs(\[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)\]

Answer 3

Que pensez-vous de ceci ?

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

Answer 4

Conceptuellement similaire à la réponse de @shang, mais il ne suppose pas que les groupes sont de taille 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)))

Cela donne :

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

Answer 5

Mon patron ne sera probablement pas content que j'aie passé un peu de temps sur ce problème amusant, mais voici une solution sympa qui ne nécessite pas de récursion, et qui utilise itertools.product . C'est expliqué dans la docstring :). Les résultats semblent corrects, mais je n'ai pas trop testé.

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

Bravo !