4

我有列表字典，如下所示：

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

3 回答 3

2

您可以以一种聪明的方式做到这一点 - 对于每个现有列表，将其中的每个数字映射到下一个大于它的数字列表中的计数。一旦你有了这些计数，明智的产品总和应该会让你得到你需要的计数。

这是一个如何获得计数的示例：

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

在OP对问题的编辑之后进行编辑以获得更清晰的问题：

你需要为这个问题构建一个动态编程解决方案（我假设你有一些DP 算法的背景；如果没有，请看一些）。假设您的原始字典有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]wherenum2大于的值number。为所有 s 添加所有此类数字downkey将为您提供 的条目M1[key][number]。因此，这会提示您必须更新 和 的行的M1顺序M2。

如果你认为这需要做很多工作——嗯，确实如此，但它仍然是多项式的，而不是像笛卡尔积那样的指数。即使是笛卡尔乘积方式 - 您必须首先找到 3 个n列表的所有可能组合，然后取乘积，然后过滤它们。那是极其昂贵的。动态规划解决方案重用每一步的信息，而不是每次都重新计算。

于 2012-05-25T02:38:14.783 回答
0

在示例中，您给出的所有字典列表都是预先排序的，因此您可以在调用 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
于 2012-05-25T06:04:21.407 回答
0

递归解决方案：

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)])
于 2012-05-25T06:32:30.360 回答