Отсортированные кортежи из декартова произведения списков

Question

У меня есть словарь списков, например, так:

D = {'x': [15, 20], 
    'y': [11, 12, 14, 16, 19], 
    'z': [7, 9, 17, 18]} 

Я хочу, чтобы взять ключи 3, в то время (я буду использовать itertools.permutations), а затем подсчитать все пути что я могу взять один элемент из каждого списка и отсортировать результат.

Для трех клавиш, показанных выше, я хотел бы получить 2:

(15, 16, 17) 
(15, 16, 18) 

Очевидно, что я могу сделать декартово произведение словарных значений, а затем рассчитывать те, отсортированные:

answer = 0 
for v_x, v_y, v_z in product(D['x'], D['y'], D['z']): 
    if v_x < v_y < v_z: 
     answer += 1 

Могу ли я сделать лучше? Это решение не масштабируется для количества ключей и длины списков, которые являются значениями. Я пробовал несколько бесплодных поисковых запросов, но я подозреваю, что мне, возможно, придется воспользоваться тем, как ключи сопоставляются со значениями списка. Тем не менее, я подумал, что было бы полезно посмотреть, есть ли решение, которое я могу использовать, без повторного выполнения остальной части программы.

ETA: Вот более большой пример.

D = {'a': [15, 20], 
    'b': [8], 
    'c': [11, 12, 14, 16, 19], 
    'd': [7, 9, 17, 18], 
    'e': [3, 4, 5, 6, 10, 13], 
    'f': [2], 
    'g': [1]} 

Есть 14 действительных ответов:

(8, 9, 10) (8, 9, 13) (8, 11, 13) (8, 12, 13) (8, 11, 17) (8, 11, 18) (8, 12, 17) (8, 12, 18) (8, 14, 17) (8, 14, 18) (8, 16, 17) (8, 16, 18) (15, 16, 17) (15, 16, 18) 

Answer 1

Вы можете сделать это в умный способ - для каждого существующего списка, отображать каждый номер в ней графу в следующем списке чисел больше, чем Это. После того, как у вас есть эти подсчеты, разумное суммирование продуктов должно дать вам счет, который вам нужен.

Вот пример того, как можно получить отсчеты:

D = {'x': [15, 20], 
    'y': [11, 12, 14, 16, 19], 
    'z': [7, 9, 17, 18]} 

order = ['x', 'y', 'z'] 
pairs = zip(order[:-1], order[1:]) 

counts = dict() 
for pair in pairs: 
    counts[pair[0]] = dict() 
    for num in D[pair[0]]: 
     counts[pair[0]][num] = len([el for el in D[pair[1]] if el >= num]) 

EDIT следующих редактированиями OP к вопросу для более четкой задачи:

Вам нужно будет построить динамичное программирование решения для эта проблема (я предполагаю, что у вас есть фон с DP algorithms, а если нет, посмотрите на несколько). Предположим, что у вашего оригинального словаря есть n ключей. Затем вам нужно три словаря длиной n, скажем M1, M2 и M3. Для каждого ключа и номера M3[key][number] будет хранить количество способов, которыми number может быть третьим элементом кортежа (это будет тождественно 1). M2[key][number] будет число способов, которыми number может быть вторым элементом кортежа (это должно быть динамически построено назад от M3), а M1[key][number] будет числом способов number может быть первым элементом кортежа. M1 необходимо будет построить от M2. Вашим окончательным решением будет сумма элементов в M1. Я оставлю правила обновления и инициализации M1, M2 и M3.

Например, для заполнения записи в M1[key][number] предположим, что downkeys - это набор ключей, которые прилагаются после key. Для каждого downkey вы можете посмотреть записи M2[downkey] и подытожить значения M2[downkey][num2], где num2 больше, чем number.Добавление всех таких чисел для всех downkey s даст вам запись для M1[key][number]. Таким образом, это дает вам подсказку относительно порядка, в котором вам необходимо обновить строки M1 и M2.

Если вы думаете, что это большая работа - ну, это так, но это все еще многочлен, а не экспоненциальный, как декартово произведение. Даже декартовский способ - вам нужно сначала найти все возможные комбинации из 3 из n списков, затем взять продукт, а затем отфильтровать их. Это чрезвычайно дорогой. Решение динамического программирования повторно использует информацию с каждого шага, а не переучитывает ее каждый раз.

Answer 2

В примерах вы учитывая все ваши словарные списки предварительно отсортированы, так что вы можете сделать некоторые сортировки себя перед вызовом itertools.product, чтобы уменьшить количество перечислений:

def count_sorted(x,y,z): 
    from itertools import ifilter, product, imap 

    _x = ifilter(lambda k: k<z[-1],x) 
    _y = ifilter(lambda k: x[0]<k<z[-1],y) 
    _z = ifilter(lambda k: k > x[0],z) 

    return sum(imap(lambda t: t[0]<t[1]<t[2], product(_x,_y,_z))) 


D = {'a': [15, 20], 
    'b': [8], 
    'c': [11, 12, 14, 16, 19], 
    'd': [7, 9, 17, 18], 
    'e': [3, 4, 5, 6, 10, 13], 
    'f': [2], 
    'g': [1]} 

for key1,key2,key3 in itertools.permutations(D.keys(),3): 
    print '[%s, %s, %s] has %i sorted combinations'%(key1,key2,key3,count_sorted(D[key1],D[key2],D[key3])) 

Результаты:

[a, c, b] has 0 sorted combinations 
[a, c, e] has 0 sorted combinations 
[a, c, d] has 2 sorted combinations 
[a, c, g] has 0 sorted combinations 
[a, c, f] has 0 sorted combinations 
[a, b, c] has 0 sorted combinations 
[a, b, e] has 0 sorted combinations 
[a, b, d] has 0 sorted combinations 
[a, b, g] has 0 sorted combinations 
[a, b, f] has 0 sorted combinations 
[a, e, c] has 0 sorted combinations 
[a, e, b] has 0 sorted combinations 
[a, e, d] has 0 sorted combinations 
[a, e, g] has 0 sorted combinations 
[a, e, f] has 0 sorted combinations 
[a, d, c] has 2 sorted combinations 
[a, d, b] has 0 sorted combinations 
[a, d, e] has 0 sorted combinations 
[a, d, g] has 0 sorted combinations 
[a, d, f] has 0 sorted combinations 
[a, g, c] has 0 sorted combinations 
[a, g, b] has 0 sorted combinations 
[a, g, e] has 0 sorted combinations 
[a, g, d] has 0 sorted combinations 
[a, g, f] has 0 sorted combinations 
[a, f, c] has 0 sorted combinations 
[a, f, b] has 0 sorted combinations 
[a, f, e] has 0 sorted combinations 
[a, f, d] has 0 sorted combinations 
[a, f, g] has 0 sorted combinations 
[c, a, b] has 0 sorted combinations 
[c, a, e] has 0 sorted combinations 
[c, a, d] has 6 sorted combinations 
[c, a, g] has 0 sorted combinations 
[c, a, f] has 0 sorted combinations 
[c, b, a] has 0 sorted combinations 
[c, b, e] has 0 sorted combinations 
[c, b, d] has 0 sorted combinations 
[c, b, g] has 0 sorted combinations 
[c, b, f] has 0 sorted combinations 
[c, e, a] has 4 sorted combinations 
[c, e, b] has 0 sorted combinations 
[c, e, d] has 4 sorted combinations 
[c, e, g] has 0 sorted combinations 
[c, e, f] has 0 sorted combinations 
[c, d, a] has 8 sorted combinations 
[c, d, b] has 0 sorted combinations 
[c, d, e] has 0 sorted combinations 
[c, d, g] has 0 sorted combinations 
[c, d, f] has 0 sorted combinations 
[c, g, a] has 0 sorted combinations 
[c, g, b] has 0 sorted combinations 
[c, g, e] has 0 sorted combinations 
[c, g, d] has 0 sorted combinations 
[c, g, f] has 0 sorted combinations 
[c, f, a] has 0 sorted combinations 
[c, f, b] has 0 sorted combinations 
[c, f, e] has 0 sorted combinations 
[c, f, d] has 0 sorted combinations 
[c, f, g] has 0 sorted combinations 
[b, a, c] has 2 sorted combinations 
[b, a, e] has 0 sorted combinations 
[b, a, d] has 2 sorted combinations 
[b, a, g] has 0 sorted combinations 
[b, a, f] has 0 sorted combinations 
[b, c, a] has 8 sorted combinations 
[b, c, e] has 2 sorted combinations 
[b, c, d] has 8 sorted combinations 
[b, c, g] has 0 sorted combinations 
[b, c, f] has 0 sorted combinations 
[b, e, a] has 4 sorted combinations 
[b, e, c] has 8 sorted combinations 
[b, e, d] has 4 sorted combinations 
[b, e, g] has 0 sorted combinations 
[b, e, f] has 0 sorted combinations 
[b, d, a] has 4 sorted combinations 
[b, d, c] has 7 sorted combinations 
[b, d, e] has 2 sorted combinations 
[b, d, g] has 0 sorted combinations 
[b, d, f] has 0 sorted combinations 
[b, g, a] has 0 sorted combinations 
[b, g, c] has 0 sorted combinations 
[b, g, e] has 0 sorted combinations 
[b, g, d] has 0 sorted combinations 
[b, g, f] has 0 sorted combinations 
[b, f, a] has 0 sorted combinations 
[b, f, c] has 0 sorted combinations 
[b, f, e] has 0 sorted combinations 
[b, f, d] has 0 sorted combinations 
[b, f, g] has 0 sorted combinations 
[e, a, c] has 12 sorted combinations 
[e, a, b] has 0 sorted combinations 
[e, a, d] has 12 sorted combinations 
[e, a, g] has 0 sorted combinations 
[e, a, f] has 0 sorted combinations 
[e, c, a] has 44 sorted combinations 
[e, c, b] has 0 sorted combinations 
[e, c, d] has 44 sorted combinations 
[e, c, g] has 0 sorted combinations 
[e, c, f] has 0 sorted combinations 
[e, b, a] has 8 sorted combinations 
[e, b, c] has 20 sorted combinations 
[e, b, d] has 12 sorted combinations 
[e, b, g] has 0 sorted combinations 
[e, b, f] has 0 sorted combinations 
[e, d, a] has 28 sorted combinations 
[e, d, c] has 52 sorted combinations 
[e, d, b] has 4 sorted combinations 
[e, d, g] has 0 sorted combinations 
[e, d, f] has 0 sorted combinations 
[e, g, a] has 0 sorted combinations 
[e, g, c] has 0 sorted combinations 
[e, g, b] has 0 sorted combinations 
[e, g, d] has 0 sorted combinations 
[e, g, f] has 0 sorted combinations 
[e, f, a] has 0 sorted combinations 
[e, f, c] has 0 sorted combinations 
[e, f, b] has 0 sorted combinations 
[e, f, d] has 0 sorted combinations 
[e, f, g] has 0 sorted combinations 
[d, a, c] has 4 sorted combinations 
[d, a, b] has 0 sorted combinations 
[d, a, e] has 0 sorted combinations 
[d, a, g] has 0 sorted combinations 
[d, a, f] has 0 sorted combinations 
[d, c, a] has 18 sorted combinations 
[d, c, b] has 0 sorted combinations 
[d, c, e] has 4 sorted combinations 
[d, c, g] has 0 sorted combinations 
[d, c, f] has 0 sorted combinations 
[d, b, a] has 2 sorted combinations 
[d, b, c] has 5 sorted combinations 
[d, b, e] has 2 sorted combinations 
[d, b, g] has 0 sorted combinations 
[d, b, f] has 0 sorted combinations 
[d, e, a] has 8 sorted combinations 
[d, e, c] has 16 sorted combinations 
[d, e, b] has 0 sorted combinations 
[d, e, g] has 0 sorted combinations 
[d, e, f] has 0 sorted combinations 
[d, g, a] has 0 sorted combinations 
[d, g, c] has 0 sorted combinations 
[d, g, b] has 0 sorted combinations 
[d, g, e] has 0 sorted combinations 
[d, g, f] has 0 sorted combinations 
[d, f, a] has 0 sorted combinations 
[d, f, c] has 0 sorted combinations 
[d, f, b] has 0 sorted combinations 
[d, f, e] has 0 sorted combinations 
[d, f, g] has 0 sorted combinations 
[g, a, c] has 2 sorted combinations 
[g, a, b] has 0 sorted combinations 
[g, a, e] has 0 sorted combinations 
[g, a, d] has 2 sorted combinations 
[g, a, f] has 0 sorted combinations 
[g, c, a] has 8 sorted combinations 
[g, c, b] has 0 sorted combinations 
[g, c, e] has 2 sorted combinations 
[g, c, d] has 8 sorted combinations 
[g, c, f] has 0 sorted combinations 
[g, b, a] has 2 sorted combinations 
[g, b, c] has 5 sorted combinations 
[g, b, e] has 2 sorted combinations 
[g, b, d] has 3 sorted combinations 
[g, b, f] has 0 sorted combinations 
[g, e, a] has 12 sorted combinations 
[g, e, c] has 28 sorted combinations 
[g, e, b] has 4 sorted combinations 
[g, e, d] has 20 sorted combinations 
[g, e, f] has 0 sorted combinations 
[g, d, a] has 6 sorted combinations 
[g, d, c] has 12 sorted combinations 
[g, d, b] has 1 sorted combinations 
[g, d, e] has 4 sorted combinations 
[g, d, f] has 0 sorted combinations 
[g, f, a] has 2 sorted combinations 
[g, f, c] has 5 sorted combinations 
[g, f, b] has 1 sorted combinations 
[g, f, e] has 6 sorted combinations 
[g, f, d] has 4 sorted combinations 
[f, a, c] has 2 sorted combinations 
[f, a, b] has 0 sorted combinations 
[f, a, e] has 0 sorted combinations 
[f, a, d] has 2 sorted combinations 
[f, a, g] has 0 sorted combinations 
[f, c, a] has 8 sorted combinations 
[f, c, b] has 0 sorted combinations 
[f, c, e] has 2 sorted combinations 
[f, c, d] has 8 sorted combinations 
[f, c, g] has 0 sorted combinations 
[f, b, a] has 2 sorted combinations 
[f, b, c] has 5 sorted combinations 
[f, b, e] has 2 sorted combinations 
[f, b, d] has 3 sorted combinations 
[f, b, g] has 0 sorted combinations 
[f, e, a] has 12 sorted combinations 
[f, e, c] has 28 sorted combinations 
[f, e, b] has 4 sorted combinations 
[f, e, d] has 20 sorted combinations 
[f, e, g] has 0 sorted combinations 
[f, d, a] has 6 sorted combinations 
[f, d, c] has 12 sorted combinations 
[f, d, b] has 1 sorted combinations 
[f, d, e] has 4 sorted combinations 
[f, d, g] has 0 sorted combinations 
[f, g, a] has 0 sorted combinations 
[f, g, c] has 0 sorted combinations 
[f, g, b] has 0 sorted combinations 
[f, g, e] has 0 sorted combinations 
[f, g, d] has 0 sorted combinations 

Answer 3

Рекурсивный решение:

In [9]: f?? 
Definition: f(lists, triple) 
Source: 
def f(lists, triple): 
    out = set() 
    for i in range(len(lists)): 
     for x in lists[i]: 
      if len(triple) == 2 and triple[1] < x: 
       out.add(triple + (x,)) 
      elif len(triple) == 0 or triple[0] < x: 
       for j in range(i+1, len(lists)): 
        out.update(f(lists[j:], triple + (x,))) 
    return out 

Входной сигнал:

In [10]: lists 
Out[10]: 
[[15, 20], 
[8], 
[11, 12, 14, 16, 19], 
[7, 9, 17, 18], 
[3, 4, 5, 6, 10, 13], 
[2], 
[1]] 

Выход:

In [11]: out = f(lists,()) 

In [12]: len(out) 
Out[12]: 14 

In [13]: out 
Out[13]: 
set([(8, 9, 10), 
    (8, 12, 18), 
    (8, 11, 13), 
    (8, 16, 17), 
    (15, 16, 17), 
    (8, 12, 17), 
    (8, 14, 18), 
    (15, 16, 18), 
    (8, 11, 17), 
    (8, 9, 13), 
    (8, 14, 17), 
    (8, 11, 18), 
    (8, 12, 13), 
    (8, 16, 18)])