java - 从多个列表中获取值的所有组合

Question

我正在尝试根据给定字符串解析所有元素组合。

字符串是这样的:

String result="1,2,3,###4,5,###6,###7,8,";

###之间的元素个数(以,分隔)未确定，“list”的个数(以###分隔的部分) ) 也未确定。

注意:我在这个例子中使用了数字，但它也可以是 String。

在这种情况下预期的结果是一个字符串包含:

String result = "1467, 1468, 1567, 1568, 2467, 2468, 2567, 2568, 3467, 3468, 3567, 3568"

因此，正如您所看到的，结果中的元素必须以第一个列表的元素开头，然后第二个元素必须是第二个列表的元素，依此类推...

从现在开始，我制作了这个算法，但它很慢:

    String [] parts = result.split("###");
    if(parts.length>1){
        result="";
        String stack="";
        int i;
        String [] elmts2=null;

        String [] elmts = parts[0].split(",");
        for(String elmt : elmts){               //Browse root elements
            if(elmt.trim().isEmpty())continue;

            /**
             * This array is used to store the next index to use for each row.
             */
            int [] elmtIdxInPart= new int[parts.length];

            //Loop until the root element index change.
            while(elmtIdxInPart[0]==0){

                stack=elmt;

                //Add to the stack an element of each row, chosen by index (elmtIdxInPart)
                for(i=1 ; i<parts.length;i++){
                    if(parts[i].trim().isEmpty() || parts[i].trim().equals(","))continue;
                    String part = parts[i];
                    elmts2 = part.split(",");
                    stack+=elmts2[elmtIdxInPart[i]];
                }
                //rollback i to previous used index
                i--;

                if(elmts2 == null){
                    elmtIdxInPart[0]=elmtIdxInPart[0]+1;
                }
                //Check if all elements in the row have been used.
                else if(elmtIdxInPart[i]+1 >=elmts2.length || elmts2[elmtIdxInPart[i]+1].isEmpty()){

                    //Make evolve previous row that still have unused index
                    int j=1;
                    while(elmtIdxInPart[i-j]+1 >=parts[i-j].split(",").length || 
                            parts[i-j].split(",")[elmtIdxInPart[i-j]+1].isEmpty()){
                        if(j+1>i)break;
                        j++;
                    }
                    int next = elmtIdxInPart[i-j]+1;
                    //Init the next row to 0.
                    for(int k = (i-j)+1 ; k <elmtIdxInPart.length ; k++){
                        elmtIdxInPart[k]=0;
                    }
                    elmtIdxInPart[i-j]=next;
                }
                else{
                    //Make evolve index in current row, init the next row to 0.
                    int next = elmtIdxInPart[i]+1;
                    for(int k = (i+1) ; k <elmtIdxInPart.length ; k++){
                        elmtIdxInPart[k]=0;
                    }
                    elmtIdxInPart[i]=next;
                }
                //Store full stack
                result+=stack+",";
            }
        }
    }
    else{
        result=parts[0];
    }

如果可能的话，我正在寻找性能更高的算法。我是从头开始做的，没有考虑任何数学算法。所以我认为我做了一个棘手/缓慢的算法，它可以改进。

感谢您的建议，也感谢您试图理解我所做的事情:)

编辑

使用 Svinja 命题将执行时间除以 2:

        StringBuilder res = new StringBuilder();
        String input = "1,2,3,###4,5,###6,###7,8,";
        String[] lists = input.split("###");
        int N = lists.length;
        int[] length = new int[N];
        int[] indices = new int[N];
        String[][] element = new String[N][];
        for (int i = 0; i < N; i++){
            element[i] = lists[i].split(",");
            length[i] = element[i].length;
        }

        // solve
        while (true)
        {
            // output current element
            for (int i = 0; i < N; i++){
                res.append(element[i][indices[i]]);
            }
            res.append(",");

            // calculate next element
            int ind = N - 1;
            for (; ind >= 0; ind--)
                if (indices[ind] < length[ind] - 1) break;
            if (ind == -1) break;

            indices[ind]++;
            for (ind++; ind < N; ind++) indices[ind] = 0;
        }
        System.out.println(res);

Answer 1

这是我的解决方案。它在 C# 中，但您应该能够理解它(重要的部分是“计算下一个元素”部分):

    static void Main(string[] args)
    {
        // parse the input, this can probably be done more efficiently
        string input = "1,2,3,###4,5,###6,###7,8,";
        string[] lists = input.Replace("###", "#").Split('#');
        int N = lists.Length;
        int[] length = new int[N];
        int[] indices = new int[N];
        for (int i = 0; i < N; i++)
            length[i] = lists[i].Split(',').Length - 1;

        string[][] element = new string[N][];
        for (int i = 0; i < N; i++)
        {
            string[] list = lists[i].Split(',');
            element[i] = new string[length[i]];
            for (int j = 0; j < length[i]; j++)
                element[i][j] = list[j];
        }

        // solve
        while (true)
        {
            // output current element
            for (int i = 0; i < N; i++) Console.Write(element[i][indices[i]]);
            Console.WriteLine(" ");

            // calculate next element
            int ind = N - 1;
            for (; ind >= 0; ind--)
                if (indices[ind] < length[ind] - 1) break;
            if (ind == -1) break;

            indices[ind]++;
            for (ind++; ind < N; ind++) indices[ind] = 0;
        }
    }

似乎与您的解决方案有点相似。这真的有不好的表现吗？在我看来，这显然是最优的，因为复杂度与输出大小成线性关系，这始终是最优的。

编辑:我所说的“相似”是指您似乎也在用索引进行计数。你的代码太复杂了，我下类后无法阅读。 :D

我的索引调整工作很简单:从右边开始，找到第一个我们可以增加而不会溢出的索引，将其增加一个，并将其右边的所有索引(如果有的话)设置为0。它基本上是在计数每个数字都在不同基数中的数字系统。一旦我们甚至无法再增加第一个索引(这意味着我们无法增加任何索引，因为我们从右侧开始检查)，我们就完成了。