4

我有一个非常奇怪的问题，它有一些难以解决的限制。我有一个列表列表，我想对这些列表中的所有项目进行组合。每个项目都有一个名称和一个值。这是一个例子：

主要清单：

  • 清单 01：
    • 项目 01：名称：name01，值：value01
    • 项目 02：名称：name02，值：value02
  • 清单 02：
    • 项目 01：名称：name03，值：value03
  • 清单 03：
    • 项目 01：名称：name04，值：value04
    • 项目 02：名称：name05，值：value05

最终结果应如下所示：

一些清单：

  • 项目 01：name01:value01、name03:value03、name04:value04
  • 项目 02：name02:value02、name03:value03、name04:value04
  • 项目 03：name03:value03、name03:value03、name04:value04
  • 项目 04：name01:value01、name03:value03、name04:value05
  • 项目 05：name02:value02、name03:value03、name04:value05
  • 项目 06：name03:value03、name03:value03、name04:value05

新列表几乎包含类似于哈希映射的项目。

约束如下：

  1. 我无法收集到新列表并将它们混合，因为这些列表可能会很快变得很大。
  2. 我正在使用某种类似观察者的 api，所以我需要尽快让观察者了解结果，这样我就不会使用太多内存。

换句话说，这个组合生成器可能会收到 X 个列表，每个列表可以包含 N 个项目，我必须在不使用太多内存的情况下生成它们的组合。

我不希望一次处理超过 5 个列表，但我想让算法尽可能地适应代码更改。

我正在用 java 解决这个问题，但该算法在其他语言中也应该同样有效，因为它可能会被翻译。

你有什么想法、建议吗？

提前致谢。

PS我不认为递归会很好用。我正在玩弄使用while循环和一些嵌套循环的想法，但是很难想象它应该如何工作。

4

4 回答 4

2

所以这是笛卡尔积，你在追求吗？

假设 3 个列表，包含 2、1 和 3 个元素。您将以 2*1*3 组合 = 6 结尾。（摘要：a * b * ... * i）

现在你从 0 到 5 取 6 个数字。

void getCombiFor (int i, List <List <Integer>> li) 
{
     if (li.length > 0) 
     { 
        int idx = i % li.get (0).size ();        
        System.out.print (li.get (0).get(idx));                 
        getCombiFor (i - idx, li.remove (0));
     } 
     System.out.println ();
}   
// pseudocodeline:
List li = List (List ('a', 'b'), List ('c'), List ('d', 'e', 'f'))
for (int i = 0; i < 6; ++i) 
{
     getCombiFor (i, li);
}

例子：

Lists = ((a,b), (c), (d,e,f))
acd
bcd
acf
bcf
ace
bce
于 2011-02-17T01:52:49.803 回答
1

你不需要使用任何内存来解决这个问题。可以在数学上获得列表的第 N 个元素，而无需创建整个组合。这里解释

于 2011-02-17T01:09:56.770 回答
0

如何创建一个索引数组，每个给定列表一个？可以通过依次对每个列表执行 get() 来读取当前组合。每个索引都为零 - 然后前进到您实际执行的下一个组合

index[0]++;
if (index[0] >= list[0].size()) {
    index[0] = 0;
    index[1]++;
    if (index[1] >= list[1].size()) {
        ...
    }
}

（将嵌套的 if 转换为迭代，留给读者练习。）

于 2011-02-17T00:52:17.657 回答
0

你为什么不实际制作一个哈希图？

Map<String,Map<String,String>> mainMap = new HashMap<String,Map<String,String>>();

for(List l : lists) {
    for(Data d : l) {
        String item = d.item;
        String name = d.name;
        String value = d.value;

        Map<String,String> itemMap = mainMap.get(item);
        if(item == null) {
            itemMap = new HashMap<String,String>(); 
            mainMap.put(item,itemMap);
        }
        itemMap.put(name,value);
    }
}

稍后，您想获取给定名称的所有值，无论是什么项目？

List<String> getValuesForName(String name) {
    List<String> list = new LinkedList<String>();
    for(Map<String,String map : mainMap) {
        String value = map.get(name);
        if(value != null) list.add(value);
    }
    return list;
}
于 2011-02-17T00:57:33.160 回答