Des combinaisons sans l'aide de “itertools.les combinaisons”

Ce que j'avais besoin de faire est de créer des combinaisons de deux éléments à la fois.

si une liste contient: seq = ['A', 'B', 'C']
la sortie serait com = [['A', 'B'], ['A', 'C'], ['B', 'C']]

tout cela sans "itertools.les combinaisons" la méthode.

J'avais l'habitude d'utiliser ce code pour les permutations. Mais comment pourrais-je modifier le code pour le faire fonctionner avec les combinaisons?

def permute(seq):

    if len(seq) <= 1:
        perms = [seq]
    else:
        perms = []
        for i in range(len(seq)):
            sub = permute(seq[:i]+seq[i+1:]) 
            for p in sub:    
                perms.append(seq[i:i+1]+p)

return perms
Pourquoi sans itertools?
L'équivalent de code source pour combinations est sur le itertools page de documentation. Il suffit de copier-coller dans votre fichier.
Oui, je ne peux pas utiliser d'autres méthodes. Merci, je vais jeter un oeil.

OriginalL'auteur user3104548 | 2013-12-24

  1. 8

    Si vous ne souhaitez pas utiliser itertools, puis utilisez le documenté pur Python équivalent:

    def combinations(iterable, r):
    # combinations('ABCD', 2) --> AB AC AD BC BD CD
    # combinations(range(4), 3) --> 012 013 023 123
    pool = tuple(iterable)
    n = len(pool)
    if r > n:
        return
    indices = range(r)
    yield tuple(pool[i] for i in indices)
    while True:
        for i in reversed(range(r)):
            if indices[i] != i + n - r:
                break
        else:
            return
        indices[i] += 1
        for j in range(i+1, r):
            indices[j] = indices[j-1] + 1
        yield tuple(pool[i] for i in indices)
    Quel est le Big O temps la complexité de ce système? Je pense que c'est O(r * (n! / (r! (n - r)!))): le while boucles nCr fois, et tuple(pool[i] for i in indices) fait de chaque boucle ont O(r) travail. Donc, cette solution itérative est beaucoup plus efficace que le retour en arrière récursif solution, je pense que c'est O(n^r).
    Je n'ai pas fait une analyse de la complexité; d'un coup d'oeil, je pense que vous avez obtenu la complexité correcte. Il est certainement bien au-dessous de O(nr).

    OriginalL'auteur Martijn Pieters

  2. 5

    C'est trivial à faire directement:

    def comb2(s):
    for i, v1 in enumerate(s):
        for j in range(i+1, len(s)):
            yield [v1, s[j]]

    Alors:

    print list(comb2(['A', 'B', 'C']))

    affiche:

    [['A', 'B'], ['A', 'C'], ['B', 'C']]

    La seule chose qui rend les combinaisons à tous difficile de traiteur pour un seul-à-runtime nombre d'éléments à prendre à un moment. Tant que vous savez que nombre à l'avance, un nombre fixe de boucles imbriquées qu'au plus profond de fait le travail de façon évidente.

    OriginalL'auteur Tim Peters

  3. 3
    def combo2(lst,n):
    if n==0:
        return [[]]
    l=[]
    for i in range(0,len(lst)):
        m=lst[i]
        remLst=lst[i+1:]
        for p in combo2(remLst,n-1):
            l.append([m]+p)
    return l

    D'entrée:

    combo2(list('ABC'),2)

    De sortie:

    [['A', 'B'], ['A', 'C'], ['B', 'C']]

    OriginalL'auteur SixenseMan

  4. 1

    Voici une traduction approximative de l'récursive de code C++ dans un réponse à une question similaire:

    def combinations(sequence, length, NULL=object()):
    """ Find all combinations of the specified length from a sequence. """
    if length <= 0:
        combos = [NULL]
    else:
        combos = []
        for i, item in enumerate(sequence, 1):
            rem_items = sequence[i:]
            rem_combos = combinations(rem_items, length-1)
            combos.extend(item if combo is NULL else [item, combo]
                            for combo in rem_combos)
    return combos

print(combinations(['A', 'B', 'C'], 2))

    De sortie:

    [['A', 'B'], ['A', 'C'], ['B', 'C']]

    OriginalL'auteur martineau