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

J'espère que cela vous aidera :

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

[(i,j) pour i dans L pour j dans L]

de la production :

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

Answer 2

Ce code fonctionne lorsque la longueur de la liste n'est pas un multiple de 2 ; il fait appel à un hack pour le faire fonctionner. Il existe peut-être de meilleures façons de procéder... Il garantit également que les paires sont toujours dans un tuple et qu'il fonctionne, que l'entrée soit 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

Answer 3

J'ajoute ma propre contribution, qui s'appuie sur les excellentes solutions fournies par @shang et @tokland. Mon problème était que dans un groupe de 12 personnes, je voulais également voir toutes les paires possibles lorsque la taille des paires ne se divise pas parfaitement avec la taille du groupe. Par exemple, pour une liste d'entrée de 12, je veux voir toutes les paires possibles avec 5 éléments.

Ce bout de code et cette petite modification devraient résoudre ce problème :

import itertools

def generate_groups(lst, n):
    if not lst:
        yield []
    else:

        if len(lst) % n == 0:

            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

        else:

            for group in (((lst[0],) + xs) for xs in itertools.combinations(lst[1:], n-1)):
                group2 = [x for x in lst if x not in group]
                for grp in (((group2[0],) + xs2) for xs2 in itertools.combinations(group2[1:], n-1)):
                    yield [group] + [grp]

Ainsi, dans ce cas, si j'exécute le bout de code suivant, j'obtiens les résultats ci-dessous. Le dernier bout de code permet de vérifier que je n'ai pas d'éléments qui se chevauchent.

i = 0
for x in generate_groups([1,2,3,4,5,6,7,8,9,10,11,12], 5):
    print(x)
    for elem in x[0]:
        if elem in x[1]:
            print('break')
            break

>>>
[(1, 2, 3, 4, 5), (6, 7, 8, 9, 10)]
[(1, 2, 3, 4, 5), (6, 7, 8, 9, 11)]
[(1, 2, 3, 4, 5), (6, 7, 8, 9, 12)]
[(1, 2, 3, 4, 5), (6, 7, 8, 10, 11)]
[(1, 2, 3, 4, 5), (6, 7, 8, 10, 12)]
[(1, 2, 3, 4, 5), (6, 7, 8, 11, 12)]
[(1, 2, 3, 4, 5), (6, 7, 9, 10, 11)]
...

Answer 4

Ce n'est pas le plus efficace ni le plus rapide, mais c'est probablement le plus facile. La dernière ligne est une façon simple de déduire une liste en Python. Dans ce cas, des paires comme (0,1) et (1,0) sont dans la sortie. Je ne suis pas sûr que vous considériez ces paires comme des doublons ou non.

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)

Sortie :

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