Création de partitions d'ensembles de telle sorte que chaque partition ait la même longueur

Question

Selon le titre, j'essaie d'écrire une fonction qui renvoie une liste de tuples d'ensembles de longueur p, où chaque ensemble est une partition de l'ensemble S. e.g. equipartitions ({0,1,2,3}, 2) -> [({0, 1}, {2, 3}), ({0, 2}, {1, 3}), ({0, 3}, {1, 2})]. Cependant, j'ai quelques difficultés à le faire fonctionner correctement pour d'autres cas puisque itertools.products ne concaténera pas les tuples d'ensembles. Tout conseil ou aide sur la façon d'écrire ou de corriger la fonction serait grandement apprécié. Voici ma tentative jusqu'ici:

equipartitions_cache_d = {} 
def equipartitions(S,p): 
    global equipartitions_cache_d 
    if len(S) % p != 0: 
     raise ValueError("Set must be of a length which is a multiple of p") 
    if equipartitions_cache_d.get((frozenset(S),p)): 
     return equipartitions_cache_d[(frozenset(S),p)] 
    else: 
     if len(S) == p: 
      equipartitions_cache_d[(frozenset(S),p)] = [S] 
     else: 
      gens = [] 
      combs = [set(s) for s in itertools.combinations(S, p)] 
      for c in combs: 
       gens += [s for s in itertools.product([c], equipartitions(S-c,p))] 
      uniqgens = [] 
      for g in gens: 
       if not any([all([x in q for x in g]) for q in uniqgens]): 
        uniqgens.append(g) 
      equipartitions_cache_d[(frozenset(S),p)] = uniqgens 
     return equipartitions_cache_d[(frozenset(S),p)] 

Answer 1

Pas très efficace (prend beaucoup de temps pour les grandes entrées comme equipart(set(range(100), 5))) mais fonctionne.

def equipart(s, p): 
    import itertools 
    if len(s) % p != 0: 
     raise ValueError("Set must be of a length which is a multiple of p") 
    com = map(set, set(itertools.combinations(s, p))) 
    res = list() 
    for ia, a in enumerate(com): 
     for il, l in enumerate(res): 
      if not any([(a&x) for x in l]): 
       res[il] = res[il] + (a,) 
       break 
     else: 
      res.append((a,)) 
    res = filter(lambda x: len(x) == len(s)/p, res) 
    return res 

sortie:

In [94]: equipart({1,2,3,4,5,6}, 3) 
Out[94]: 
[({3, 4, 6}, {1, 2, 5}), 
({2, 3, 5}, {1, 4, 6}), 
({1, 2, 6}, {3, 4, 5}), 
({2, 3, 4}, {1, 5, 6}), 
({4, 5, 6}, {1, 2, 3}), 
({2, 3, 6}, {1, 4, 5}), 
({1, 3, 6}, {2, 4, 5}), 
({2, 4, 6}, {1, 3, 5}), 
({2, 5, 6}, {1, 3, 4}), 
({3, 5, 6}, {1, 2, 4})] 

In [95]: equipart({1,2,3,4,5,6}, 2) 
Out[95]: [({1, 2}, {5, 6}, {3, 4}), ({1, 3}, {4, 6}, {2, 5}), ({1, 6}, {2, 4}, {3, 5})] 

Edit:

Nouvelle méthode de sous-ensemble unique des plusieurs tuples.

def equipart(s, p): 
    import itertools 
    if len(s) % p != 0: 
     raise ValueError("Set must be of a length which is a multiple of p") 
    com = map(set, set(itertools.combinations(s, p))) 
    res = [x for x in itertools.combinations(com, len(s)/p) if set().union(*x) == s] 
    return res 

Sortie:

In [37]: equipart({1,2,3,4,5,6}, 3) 
Out[37]: 
[({3, 4, 6}, {1, 2, 5}), 
({2, 3, 5}, {1, 4, 6}), 
({1, 2, 6}, {3, 4, 5}), 
({2, 3, 4}, {1, 5, 6}), 
({4, 5, 6}, {1, 2, 3}), 
({2, 3, 6}, {1, 4, 5}), 
({1, 3, 6}, {2, 4, 5}), 
({2, 4, 6}, {1, 3, 5}), 
({2, 5, 6}, {1, 3, 4}), 
({3, 5, 6}, {1, 2, 4})] 

In [38]: equipart({1,2,3,4,5,6}, 2) 
Out[38]: 
[({1, 2}, {5, 6}, {3, 4}), 
({1, 2}, {4, 6}, {3, 5}), 
({1, 2}, {4, 5}, {3, 6}), 
({5, 6}, {1, 3}, {2, 4}), 
({5, 6}, {1, 4}, {2, 3}), 
({1, 3}, {4, 6}, {2, 5}), 
({1, 3}, {4, 5}, {2, 6}), 
({4, 6}, {1, 5}, {2, 3}), 
({4, 5}, {1, 6}, {2, 3}), 
({1, 4}, {2, 6}, {3, 5}), 
({1, 4}, {3, 6}, {2, 5}), 
({1, 5}, {2, 6}, {3, 4}), 
({1, 5}, {3, 6}, {2, 4}), 
({1, 6}, {2, 5}, {3, 4}), 
({1, 6}, {2, 4}, {3, 5})]