Comment créer une liste de tous les tuples possibles à partir de cette table?

Question

Supposons que j'ai un ensemble de définitions de colonne:

Col1: value11 value12 value13 
Col2: value21 value22 
Col3: value31 value32 value33 
... 

Étant donné un sous-ensemble de colonnes - 2 ou plus - je veux trouver toutes les valeurs possibles pour ces colonnes. Supposons que je choisis les colonnes 1 et 2 ci-dessus:

(value11 value21) 
(value11 value22) 
(value12 value21) 
(value12 value22) 
(value13 value21) 
(value13 value22) 

Si je l'avais choisi 2: 3:

(value21 value31) 
(value21 value32) 
(value21 value33) 
(value22 value31) 
(value22 value32) 
(value22 value33) 

Si je l'avais choisi trois:

(value11 value21 value31) 
(value11 value21 value32) 
... 

Je m implémentant ceci en python, et je voudrais un rapide algorithme pour ce faire. Mon entrée est une liste de tuples: (columnName, columnValueList)

Des suggestions?

Answer 1

La meilleure façon d'obtenir ceci va utiliser itertools.product(). Par exemple:

import itertools 

group1 = ['a', 'b'] 
group2 = ['c', 'd'] 

print list(itertools.product(group1, group2)) 

#==> [('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd')] 

Cette fonction accepte plusieurs arguments (c'est-à-dire plusieurs colonnes).

Pour plus d'aide sur iterools.product(), voir this.

Answer 2

On dirait que itertools.combination pourrait vous aider.

>>> from itertools import combinations 
>>> list(combinations(xrange(5), 2)) 
[(0, 1), (0, 2), (0, 3), (0, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] 
>>> list(combinations(xrange(5), 3)) 
[(0, 1, 2), (0, 1, 3), (0, 1, 4), (0, 2, 3), (0, 2, 4), (0, 3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)] 

Answer 3

En plus d'utiliser itertools.product() comme jeremy suggère, vous voudrez peut-être envisager de convertir votre liste de tuples à un dict faire pour columnName rapide lookups:

dict(tupleList)

Answer 4

solutions plus générales Jeremy serait:

import itertools 
full = [[value11, value12, value13], 
     [value21, value22], 
     [value31, value32, value33]] 
ids = 0, 2 

ou si elle est un dict (comme il devrait être):

full = {'col1': [value11, value12, value13], 
     'col2': [value21, value22], 
     'col3': [value31, value32, value33]} 
ids = 'col1', 'col3' 
selected = (full[i] for i in ids) 
list(itertools.product(*selected)) 

Answer 5

Je parie que les solutions basées sur itertools vont être plus rapides, mais si elles doivent être évitées (par ex. coincé sur Python 2.5 sans itertools.product, etc), il peut bien sûr être entièrement codé en "base Python" quand il le faut.

Essayer de « tirer tous les arrêts » pour la vitesse, peut-être quelque chose comme: (! A besoin de profilage complet des échantillons de données réalistes)

def odo(*names_and_valuelists): 
    aux = [[vl, 0] for n, vl in names_and_valuelists] 
    if any(len(vl)==0 for vl, _ in aux): 
     return 
    while True: 
     yield tuple(vl[i] for vl, i in aux) 
     for vlandi in reversed(aux): 
      if vlandi[1] == len(vlandi[0])-1: 
      vlandi[1] = 0 
      else: 
      vlandi[1] += 1 
      break 
     else: 
      return 

si quelques réglages mineurs pourraient accélérer encore.

Voici votre exemple d'utilisation:

def main(): 
    data = [ 
     ('Col1', 'value11 value12 value13'.split()), 
     ('Col2', 'value21 value22'.split()), 
     ('Col3', 'value31 value32 value33'.split()), 
    ] 
    for tup in odo(data[0], data[1]): print tup 
    print 
    for tup in odo(data[1], data[2]): print tup 
    print 
    for i, tup in enumerate(odo(*data)): 
     print tup 
     if i>5: break 

if __name__ == '__main__': 
    main() 

qui émet les résultats:

('value11', 'value21') 
('value11', 'value22') 
('value12', 'value21') 
('value12', 'value22') 
('value13', 'value21') 
('value13', 'value22') 

('value21', 'value31') 
('value21', 'value32') 
('value21', 'value33') 
('value22', 'value31') 
('value22', 'value32') 
('value22', 'value33') 

('value11', 'value21', 'value31') 
('value11', 'value21', 'value32') 
('value11', 'value21', 'value33') 
('value11', 'value22', 'value31') 
('value11', 'value22', 'value32') 
('value11', 'value22', 'value33') 
('value12', 'value21', 'value31')