1

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

字符串是这样的:

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

###(用 分隔)之间的元素数量,未确定,“列表”(用 分隔的部分###)的数量也未确定。

注意:我在这个例子中使用了数字,但也可以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);
4

2 回答 2

1

这是一种稍微不同的方法:

    static void Main(string[] args)
    {
        string input = "1,2,3,###4,5,###6,###7,8,";

        string[] lists = input.Replace("###", "#").Split('#');
        int N = lists.Length;
        int[] length = new int[N];
        string[][] element = new string[N][];
        int outCount = 1;

        // get each string for each position
        for (int i = 0; i < N; i++)
        {
            string list = lists[i];
            // fix the extra comma at the end
            if (list.Substring(list.Length - 1, 1) == ",")
                list = list.Substring(0, list.Length - 1);

            string[] strings = list.Split(',');
            element[i] = strings;
            length[i] = strings.Length;
            outCount *= length[i];
        }
        // prepare the output array
        string[] outstr = new string[outCount];

        // produce all of the individual output strings
        string[] position = new string[N];
        for (int j = 0; j < outCount; j++)
        {
            // working value of j:
            int k = j;

            for (int i = 0; i < N; i++)
            {
                int c = length[i];
                int q = k / c;
                int r = k - (q * c);
                k = q;
                position[i] = element[i][r];
            }
            // combine the chars
            outstr[j] = string.Join("", position);                
        }
        // join all of the strings together
        //(note: joining them all at once is much faster than doing it
        //incrementally, if a mass concatenate facility is available
        string result = string.Join(", ", outstr);            
        Console.Write(result);
    }

我也不是 Java 程序员,所以我将 Svinja 的 c# 答案改编为我的算法,假设您也可以将其转换为 Java。(感谢 Svinja..)

于 2012-04-11T20:42:59.593 回答
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。它基本上是在一个数字系统中计数,其中每个数字都有不同的基数。一旦我们甚至不能再增加第一个索引(这意味着我们不能增加任何索引,因为我们从右边开始检查),我们就完成了。

于 2012-04-11T14:13:10.270 回答