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"

したがって、結果の要素は最初のリストの要素で開始する必要があり、次に2番目の要素は2番目のリストの要素である必要があります。

今から私はこのアルゴリズムを機能させるようにしましたが、それは遅いです:

    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

これが私の解決策です。これは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

私のインデックス調整は非常に簡単に機能します。右から始めて、オーバーフローせずに増やすことができる最初のインデックスを見つけ、それを1つ増やし、その右側のすべてのインデックス(存在する場合)を0に設定します。各桁は異なるベースにあります。最初のインデックスをこれ以上増やすことができなくなったら(つまり、右からチェックを開始したため、増やすことはできません)、これで完了です。

于 2012-04-11T14:13:10.270 に答える
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プログラマーではないので、Javaに変換できることを前提として、Svinjaのc#の回答をアルゴリズムに適合させました。(Svinjaに感謝します。)

于 2012-04-11T20:42:59.593 に答える