多くのリストから値のすべての組み合わせを取得する

Question

指定された文字列に基づいてすべての要素の組み合わせを解決しようとしています。

文字列は次のようである：

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

（,で分離）###間の素子の数が決定されず、「リスト」の数は、（一部は###で分離された）のいずれかで決定されません。

注意：この例ではnumberを使用していますが、Stringでも構いません。ですから、結果の要素は、その後、2番目の要素は要素でなければならない最初のリストの要素で開始する必要があります見ることができるように

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

私が探しています可能であれば、より性能の高いアルゴリズム。私は何か数学的なアルゴリズムを考えずにゼロから作りました。だから私はトリッキーな/遅いアルゴを作ったと思うし、それは改善することができます。

ご提案のおかげで、私は

EDIT

は、それが2で実行時間を分割Svinja命題を使用して:)何をやったか理解しようとしてくれてありがとう：

 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

私のインデックス調整は非常に簡単です：右から始めて、オーバーフローせずに増やすことができる最初のインデックスを見つけ、それを1つ増やし、すべてのインデックスを右に（もしあれば）0に設定します。各桁が異なるベースにあるナンバーシステムでカウントします。いったん最初のインデックスをさらに増やせなくなったら（つまり、右からチェックを始めたときには増やすことはできません）、完了です。

Answer 2

はここで多少異なるアプローチである：

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のおかげで..）