查找所有“和”组合多个集合

比方说我有x集合对象，并且每个集合都有一定数量的对象。我想创建一个数组，它将存储所有这些对象的唯一“和”组合。例如，如果我在集合A中有5个对象，集合B中有10个对象，集合C中有8个对象，那么我知道有5 * 10 * 8 = 400个独特的方式从每个对象中选择一个对象组。但我想实际上将这些组合存储在一个数组中。查找所有“和”组合多个集合

所以数组是多维的，是这样的：

{ 
    { a, a, a } 
    { a, a, b } 
    { a, a, c } 
    ... 
    { a, b, a } 
    { a, b, b } 
    and so on... 
}

我需要的解决方案，以尽可能高效，因为我处理的地方有潜在的数以千万计的组合情况。我不确定如何开始解决这个问题。

对不起，如果它不清楚，但我真的不知道该怎么称呼我想达到的目标，所以我只是尽我所能地描述它。感谢您提供任何帮助。

编辑：这是有关该问题的一些详细信息：

这个问题的目的是，我要计算每个结果数组“得分”值。然后，我想找到排名前n分数并将它们返回给用户。所以实际上，我相信我不需要在内存中拥有整个数组。我可以遍历数组，计算得分，并将其添加到返回的数组，如果它的分数足够高。这样，我只需要不断在内存中的顶层n对象。

我希望这使事情更清楚。

来源

2015-11-06 Charles

一些评论：notationally，我不认为'set'可以有多个相同的元素。或者，至少要知道，某些语言（例如Python）会在您使用'set（）'时重复数据删除。其次 - 拥有数以百万计的连击数，你是否需要立即整个阵列？或者你可以迭代每一个。否则，你可能会遇到内存大小问题，不是吗？ – dwanderson

嘿，对不起，如果不明确。每个集合A，B，C中的对象都是唯一的。如果你指的是符号'{a，a，a}'，我想说的是'{从一个对象a，从一个对象a到另一个对象a，从集合c对象a'等等...... – Charles

啊，陷入困境，然后忽略第一点。第二个仍然站立。 – dwanderson

快速蟒蛇，恐怕无法得到更有效的，因为你需要在某个时候进行迭代...

getItems(A, B, C): 
    for a in A: 
     for b in B: 
      for c in C: 
       items = (a, b, c) ## or [a, b, c], as desired 
       yield items

或者，如果你熟悉发电机表达式：

gen = ((a, b, c) for a in A for b in B for c in C)

然后使用：

for combo in getItems(A, B, C): ## or for combo in gen: 
    ## do stuff here

编辑：

def getItems(*allSets): 
    if len(allSets) == 0: 
     yield [] 
     return 
    thisSet, theRest = allSets[0], allSets[1:] 
    for value in thisSet: 
     for values in getItems(*theRest): 
      yield [value] + values

来源

2015-11-06 17:44:39 dwanderson

嘿，谢谢你的回复！我对此很熟悉。但是，有没有办法递归地做到这一点？我不一定知道有多少套。 – Charles

最后一点还不够用;不能连接列表'[value]'和生成器'getItems（theRest）'，但我正在处理它 – dwanderson

现在应该工作。 – dwanderson

你知道设计时的组数吗？如果是这样，我会做嵌套for循环。如果你不知道集的数量，那么你可能会做某种形式的递归来处理循环。

这样说，我认为你所做的是，根据定义，是不高效的。是否有理由需要将所有可能的组合存储在内存中，而不是根据需要随时生成它们？

来源

2015-11-06 17:48:21 WingedPanther73

对于递归，你需要一组设置对象（在java中数组的数组，等等）。你的递归将循环遍历该主数组，传递要循环的集合的索引，以及当前选中的元素。 – WingedPanther73

请参阅编辑，我希望它使问题更清楚。 – Charles

@Charles稍微澄清一点。在你的情况下，我绝对不会将所有内容都存储在RAM中。只有最高的n个分数以及他们的分数，所以你可以取代更好的分数。我可能会使用一个链表或平衡树，所以你可以保持秩序的分数，并降低最低分，一旦你找到n个物品。 – WingedPanther73

查找所有“和”组合多个集合

回答

相关问题