java - 如何即时进行组合学

Question

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

主要列表:

• list 01:
  • 项目 01:名称:name01，值:value01
  • 项目 02:名称:name02，值:value02
• list 02:
  • 项目 01:名称:name03，值:value03
• list 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

新列表几乎包含类似于 HashMap 的项目。

约束如下:

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

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

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

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

您有什么想法、建议吗？

提前致谢。

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

Answer 1

这就是笛卡尔积，你要找的是什么？

假设有 3 个列表，其中包含 2、1 和 3 个元素。您将以 2*1*3 组合 = 6 结束。(摘要:a * b * ... * i)

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

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