logo标签列表

来自列表笛卡尔积的排序元组

pythoncombinatoricsdynamic-programming
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

但我能做得更好吗？这个解决方案在键的数量和值为列表的长度方面并不具有可扩展性。我尝试了一些无果的探究，但我怀疑我可能需要利用键映射到列表值的方式。然而，我认为看看是否有一个解决方案可以在不重新设计程序的情况下使用是值得的。

预计完成时间：这里有一个更大的示例。

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)
如果你只是想计算数量，就不需要生成所有排列。 - Joel Cornett
Joel，感谢您的撰写。您所说的是密钥的排列组合吗？如果是这样，我不太理解您的意思。也就是说，我有大约360个键，每个键都有它们自己的列表（恰好在一个键的列表中出现的元素不会出现在任何其他键的列表中）。我如何避免生成排列组合呢？ - bbayles
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])

根据问题提出者对问题的编辑，以下是更清晰的问题：
你需要构建一个动态规划的解决方案来解决这个问题（我假设你有一些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]的值，其中num2大于number。将所有这些数字添加到所有downkey的条目中，将为您提供M1[key][number]的条目。因此，这为您提供了更新M1和M2行的顺序的提示。
如果您认为这是很多工作 - 那么它确实是，但它仍然是多项式的，而不是像笛卡尔积一样指数级的。即使是笛卡尔积方法 - 您仍然需要先找到n个列表中3个可能组合的所有可能组合，然后取乘积，然后过滤它们。那是非常昂贵的。动态编程解决方案重用每个步骤的信息，而不是每次重新计算它。
你的第一个问题说你想从每个列表中取一个元素，但在你的第二个例子中，你只从原来的7个列表中取了3个。我为你想要从每个列表中取一个元素的情况编写了代码，我认为它可以工作，但这不是你想要做的。那么你的问题就有点困难了，但仍然可以高效地解决。我现在不能为你编写代码，但我会编辑我的答案给你提供一个路线图。 - Ansari
我应该提到，当我一次取3个键时，我也只按排序顺序取它们。因此，在我的第二个例子中，第一个有效答案具有来自'b'、'd'和'e'列表的元素。我永远不会以不同的顺序查看它们。因此，我的问题是“在选择与排序后的3个键相关联的每个列表中的1个项目时，有多少种方法可以使这些项目排序？”这是一个冗长的问题。 - bbayles
这很有道理。我经常在没有递归和记忆化的情况下遇到动态规划问题，所以这很有帮助。你的方法对我的测试值得出了正确的答案；我现在正在运行它来处理大数据集，看看它是否足够扩展！我很快就会将你的答案标记为解决问题。 - bbayles
这个大数据集已经用完了内存（看看我的例子是如何使用数字1-20一次的？而这个大数据集使用了1-60M）。但是，这显然是解决这个问题的好方法，非常感谢你的帮助！ - bbayles
这些是我正在尝试的技巧，但目前还没有完全成功的。幸运的是，Python使这变得容易... M_1，M_2 = defaultdict(Counter)，defaultdict(Counter)。 - bbayles
显示剩余5条评论
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
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)])
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接