如何动态进行组合数学

Question

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

主列表：

- 列表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解决这个问题，但是该算法应该同样适用于其他编程语言，因为它可能会被翻译。

你有什么想法、建议吗？

提前感谢。

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

- Pass

---

你的例子不是很清晰，而且包含一个错误（我认为是这样）。我可以建议使用3个列表，分别包含2、1和3个元素((a,b)(c)(d,e,f))。这将导致6个解决方案(笛卡尔积或叉积)。如果你愿意，可以将a:=(name01, value01)读入。但是你的例子在某些列表项03中有两次n3v3 n3v3。这不是你想要的，对吧？ - user unknown

Answer 1

你想要的是笛卡尔积吗？

假设有三个列表，分别有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

- user unknown

Answer 2

你不需要使用任何内存来解决这个问题。可以通过数学方法获取列表的第N个元素，而无需创建所有组合。这里解释了这一点。

- Caner

Answer 3

如何创建一个索引数组，每个数组对应给定的列表？当前的组合可以通过依次在每个列表上执行get()来读取。每个索引都将从零开始 - 要前进到下一个组合，您实际上要做的是

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

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

- Vance Maverick

---

每个索引都会从0开始，显然。 - Vance Maverick

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

- corsiKa