如何做组合学飞 [英] How to do Combinatorics on the Fly

问题描述

我有一个很奇怪的问题，这有一定的约束，使得它难以解决。我有一个列表的列表，我想要做的这些列表中的所有项目的组合。每个项目都有一个名字和一个值。下面是一个例子：

I have a very weird problem which has some constrains that make it difficult to solve. I have a list of lists and I want to do the combinations of all items in those lists. Each item has a name and a value. Here is an example:

主目录：

• 列表01：
  • 项目01：名称：name01，值：value01
  • 项目02：名称：name02，值：value02
  • List 01:
    • Item 01: name:name01, value:value01
    • Item 02: name:name02, value:value02
    • 项目01：名称：name03，值：value03
    • 项目01：名称：name04，值：value04
    • 项目02：名称：name05，值：value05

    最终的结果应该是这样的：

    The end result should look like this:

    部分列表：

    • 项目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

    新的列表pretty的多少包含了像哈希表项。

    The new list pretty much contains items that act like hash map.

    的约束如下：

    1. 在我不能收集到新的列表，然后将它们，因为这些名单可能很快变得非常大。
    2. 在我使用的某种观测样的API，所以我需要让关于结果的观察，尽快使我没有使用多少内存。

    在换句话说这个组合生成器可以feeded与列出的每一个，其中可能包含N多的项目，我必须生成它们的组合，而无需使用太多内存的X个。

    In other words this combinations generator may be feeded with X number of lists each one of which could contain N number of items and I must generate the combinations of them without using too much memory.

    我不希望在同一时间与更多然后5名单的工作，但我想提出的算法抵御code的改变成为可能。

    I don't expect to work with more then 5 list at a time but I would like to make the algorithm as resilient to code changes as possible.

    我解决在Java的问题，但该算法应在其他语言工作得同样也因为它很可能要翻译

    I am solving the problem in java but the algorithm should work equally in other languages too because it is likely to be translated.

    你有什么意见，建议？

    在此先感谢。

    P.S。我不认为一个递归将工作做好。我玩弄使用whil​​e循环和一些嵌套循环的想法，但它是变得非常很难想象这应该是如何工作的。

    P.S. I don't think that a recursion will work well. I am toying with the idea of using a while loop and some nested loops but it is getting really difficult to envision how this should work.

    推荐答案

    所以这是笛卡尔积，你后？

    So this is the cartesian product, you're after?

    假设3列出，2，1和3元。 （：A * B * ...... *我的抽象）

    Assume 3 lists, with 2, 1 and 3 Elements. You would end in 2*1*3 combinations = 6. (abstract: a * b * ... * i)

    现在你从0 6个号码为5。

    Now you take 6 numbers from 0 to 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
    

    这篇关于如何做组合学飞的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！