Как мне составить список всех возможных кортежей из этой таблицы?

Question

Предположим, у меня есть набор определений столбцов:

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

Учитывая некоторое подмножество столбцов - 2 или более - я хочу найти все возможные значения для этих столбцов. Предположим, я выбрал столбцы 1 и 2 выше:

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

Если бы я выбрал 2: 3:

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

Если бы я выбрал все три:

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

Я реализую это в python, и мне нужен быстрый алгоритм для этого. Мой ввод представляет собой список кортежей: (columnName, columnValueList)

Есть предложения?

Answer 1

Лучший способ получить это - использовать itertools.product (). Например:

import itertools

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

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

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

Эта функция принимает несколько аргументов (то есть несколько столбцов).

Для получения дополнительной помощи по iterools.product () см. this .

Answer 2

более общих решений, чем у Джереми:

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

или, если это диктат (как и должно быть):

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 3

Бьюсь об заклад, * решения на основе itertools будут быстрее, но если их нужно избегать (например, зависание на Python 2.5 без itertools.product и т. Д.), Его, конечно, можно полностью закодировать в "base Питон ", когда нужно.

Попытка «вытащить все остановки» для скорости, может быть что-то вроде:

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

хотя незначительные изменения могут все же ускорить его (требуется тщательное профилирование с реалистичными данными выборки!).

Вот ваш пример использования:

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

который выдает результаты:

('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')

Answer 4

В дополнение к использованию itertools.product (), как предлагает Джереми, вы можете рассмотреть возможность преобразования вашего списка кортежей в dict, чтобы сделать поиск для columnName быстрым:

dict(tupleList)

Answer 5

Похоже, itertools.combination может помочь вам.

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