如何即时进行组合数学

Question

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

主列表：

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

最终结果应如下所示：

Some List:

• Item 01: name01:value01, name03:value03, name04:value04
• Item 02：名称02：值02，名称03：
• 值03，名称04：值04 项目03：名称03：值03，名称03：值03，名称04：值04
• 项目04：名称01：值01，名称03：值03，名称04：值05
• 项目05：名称02：值02，名称03： value03, name04:value05
• Item 06: name03:value03, name03:value03, name04:value05

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

限制如下：

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

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

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

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

您有什么想法、建议吗？

提前致谢。

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

Answer 1

这就是您想要的笛卡尔积吗？

假设有 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

Answer 2

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

Answer 3

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

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

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

Answer 4

你为什么不真正制作一个哈希图？

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;
}