Trouver en python des combinaisons d'ensembles mutuellement exclusifs à partir des éléments d'une liste

la méthode utilisée dans le programme ci-dessous est similaire à quelques réponses précédentes en excluant les ensembles non disjoints et donc généralement pas tester toutes les combinaisons. Il diffère des réponses précédentes en excluant avec gourmandise tous les ensembles qu'il peut, aussi tôt que possible. Cela lui permet de fonctionner plusieurs fois plus rapidement que la solution de NPE. Voici une comparaison de temps des deux méthodes, en utilisant des données d'entrée avec 200, 400,... 1000 tailles-6 ensembles ayant des éléments dans la gamme de 0 à 20:

Set size =   6,  Number max =  20   NPE method
  0.042s  Sizes: [200, 1534, 67]
  0.281s  Sizes: [400, 6257, 618]
  0.890s  Sizes: [600, 13908, 2043]
  2.097s  Sizes: [800, 24589, 4620]
  4.387s  Sizes: [1000, 39035, 9689]

Set size =   6,  Number max =  20   jwpat7 method
  0.041s  Sizes: [200, 1534, 67]
  0.077s  Sizes: [400, 6257, 618]
  0.167s  Sizes: [600, 13908, 2043]
  0.330s  Sizes: [800, 24589, 4620]
  0.590s  Sizes: [1000, 39035, 9689]

Dans les données ci-dessus, la colonne de gauche montre les temps d'exécution en secondes. Les listes de nombres montrent combien de simples, doubles, ou triples syndicats se sont produits. Les constantes dans le programme spécifient les tailles et les caractéristiques des ensembles de données.

#!/usr/bin/python
from random import sample, seed
import time
nsets,   ndelta,  ncount, setsize  = 200, 200, 5, 6
topnum, ranSeed, shoSets, shoUnion = 20, 1234, 0, 0
seed(ranSeed)
print 'Set size = {:3d},  Number max = {:3d}'.format(setsize, topnum)

for casenumber in range(ncount):
    t0 = time.time()
    sets, sizes, ssum = [], [0]*nsets, [0]*(nsets+1);
    for i in range(nsets):
        sets.append(set(sample(xrange(topnum), setsize)))

    if shoSets:
        print 'sets = {},  setSize = {},  top# = {},  seed = {}'.format(
            nsets, setsize, topnum, ranSeed)
        print 'Sets:'
        for s in sets: print s

    # Method by jwpat7
    def accrue(u, bset, csets):
        for i, c in enumerate(csets):
            y = u + [c]
            yield y
            boc = bset|c
            ts = [s for s in csets[i+1:] if boc.isdisjoint(s)]
            for v in accrue (y, boc, ts):
                yield v

    # Method by NPE
    def comb(input, lst = [], lset = set()):
        if lst:
            yield lst
        for i, el in enumerate(input):
            if lset.isdisjoint(el):
                for out in comb(input[i+1:], lst + [el], lset | set(el)):
                    yield out

    # Uncomment one of the following 2 lines to select method
    #for u in comb (sets):
    for u in accrue ([], set(), sets):
        sizes[len(u)-1] += 1
        if shoUnion: print u
    t1 = time.time()
    for t in range(nsets-1, -1, -1):
        ssum[t] = sizes[t] + ssum[t+1]
    print '{:7.3f}s  Sizes:'.format(t1-t0), [s for (s,t) in zip(sizes, ssum) if t>0]
    nsets += ndelta

Edit: en fonction accrue, les arguments (u, bset, csets) sont utilisés comme suit:

• u = liste des ensembles dans l'union actuelle des ensembles

* bset = "big set" = valeur plate de u = éléments déjà utilisé

• ECEC = ensembles de candidats = liste des ensembles pouvant être inclus

Notez que si la première ligne de accrue est remplacé par

def accrue(csets, u=[], bset=set()):

et la septième ligne par

for v in accrue (ts, y, boc):

(c'est-à-dire, si les paramètres sont ré-ordonnés et les valeurs par défaut données pour u et bset) alors accrue peut être invoqué via [accrue(listofsets)] pour produire sa liste de compatibilité des syndicats.

Concernant ValueError: zero length field name in format erreur mentionnée dans un commentaire comme se produisant lors de l'utilisation de Python 2.6, essayez les solutions suivantes.

# change:
    print "Set size = {:3d}, Number max = {:3d}".format(setsize, topnum)
# to:
    print "Set size = {0:3d}, Number max = {1:3d}".format(setsize, topnum)

des modifications similaires (ajout de numéros de champ appropriés) peuvent être nécessaires dans d'autres formats du programme. Remarque, le quoi de neuf en 2.6 page dit "Appui à la str.la méthode format () a été rétroportée à Python 2.6". Bien qu'il ne précise pas si des noms ou des numéros de champ sont requis, il ne présente pas d'exemples sans eux. En revanche, l'une ou l'autre fonctionne en 2.7.3.