反向笛卡爾乘積

Question

下面給出的設置數據：

a | b | c | d 
1 | 3 | 7 | 11 
1 | 5 | 7 | 11 
1 | 3 | 8 | 11 
1 | 5 | 8 | 11 
1 | 6 | 8 | 11 

執行反向笛卡爾乘積得到：

a | b | c | d 
1 | 3,5 | 7,8 | 11 
1 | 6 | 8 | 11 

我目前使用Scala的工作，和我的輸入/輸出數據類型是目前：

ListBuffer[Array[Array[Int]]] 

我想出了一個解決方案（見下文），但覺得它可以優化。我願意優化我的方法和全新的方法。在scala和c＃中的解決方案是首選。

我也很好奇，如果這可以在MS SQL中完成。

我目前的解決方案：

def main(args: Array[String]): Unit = { 

    // Input 
    val data = ListBuffer(Array(Array(1), Array(3), Array(7), Array(11)), 
          Array(Array(1), Array(5), Array(7), Array(11)), 
          Array(Array(1), Array(3), Array(8), Array(11)), 
          Array(Array(1), Array(5), Array(8), Array(11)), 
          Array(Array(1), Array(6), Array(8), Array(11))) 

    reverseCartesianProduct(data) 
} 

def reverseCartesianProduct(input: ListBuffer[Array[Array[Int]]]): ListBuffer[Array[Array[Int]]] = { 
    val startIndex = input(0).size - 1 

    var results:ListBuffer[Array[Array[Int]]] = input 

    for (i <- startIndex to 0 by -1) { 
     results = groupForward(results, i, startIndex) 
    } 

    results 
} 

def groupForward(input: ListBuffer[Array[Array[Int]]], groupingIndex: Int, startIndex: Int): ListBuffer[Array[Array[Int]]] = { 

    if (startIndex < 0) { 
     val reduced = input.reduce((a, b) => { 
     mergeRows(a, b) 
     }) 

     return ListBuffer(reduced) 
    } 

    val grouped = if (startIndex == groupingIndex) { 
     Map(0 -> input) 
    } 
    else { 
     groupOnIndex(input, startIndex) 
    } 

    val results = grouped.flatMap{ 
     case (index, values: ListBuffer[Array[Array[Int]]]) => 
     groupForward(values, groupingIndex, startIndex - 1) 
    } 

    results.to[ListBuffer] 
    } 

    def groupOnIndex(list: ListBuffer[Array[Array[Int]]], index: Int): Map[Int, ListBuffer[Array[Array[Int]]]] = { 

    var results = Map[Int, ListBuffer[Array[Array[Int]]]]() 

    list.foreach(a => { 
     val key = a(index).toList.hashCode() 

     if (!results.contains(key)) { 
     results += (key -> ListBuffer[Array[Array[Int]]]()) 
     } 

     results(key) += a 
    }) 

    results 
    } 

    def mergeRows(a: Array[Array[Int]], b: Array[Array[Int]]): Array[Array[Int]] = { 

    val zipped = a.zip(b) 

    val merged = zipped.map{ case (array1: Array[Int], array2: Array[Int]) => 
     val m = array1 ++ array2 

     quickSort(m) 

     m.distinct 
     .array 
    } 

    merged 
    } 

其工作原理是：

1. 遍歷列，從右到左（該groupingIndex指定上運行其列此列是唯一一個爲了合併行而不必具有彼此相等的值）。
2. 對所有其他列（不是groupingIndex）上的數據進行遞歸分組。
3. 將所有列分組後，假定每個組中的數據在除分組列以外的每列中都有相同的值。
4. 合併具有匹配列的行。爲每一列取不同的值並對每一列進行排序。

我很抱歉，如果這些沒有意義，我的大腦今天就不能運作。

Answer 1

這是我對此的看法。代碼使用Java，但可以輕鬆轉換爲Scala或C＃。

我在n-1的所有組合上運行groupingBy，並且選擇計數最低的那一個，這意味着最大的合併深度，所以這是一種貪婪的方法。但不能保證你會找到最佳的解決方案，這意味着儘量減少k這是np-hard要做的，請參閱鏈接here的解釋，但你會找到一個有效的解決方案，並做得相當快。

完整的示例在這裏：https://github.com/jbilander/ReverseCartesianProduct/tree/master/src

Main.java

import java.util.*; 
    import java.util.stream.Collectors; 

    public class Main { 

     public static void main(String[] args) { 

      List<List<Integer>> data = List.of(List.of(1, 3, 7, 11), List.of(1, 5, 7, 11), List.of(1, 3, 8, 11), List.of(1, 5, 8, 11), List.of(1, 6, 8, 11)); 
      boolean done = false; 
      int rowLength = data.get(0).size(); //4 
      List<Table> tables = new ArrayList<>(); 

      // load data into table 
      for (List<Integer> integerList : data) { 

       Table table = new Table(rowLength); 
       tables.add(table); 

       for (int i = 0; i < integerList.size(); i++) { 
        table.getMap().get(i + 1).add(integerList.get(i)); 
       } 
      } 

      // keep track of count, needed so we know when to stop iterating 
      int numberOfRecords = tables.size(); 

      // start algorithm 
      while (!done) { 

       Collection<List<Table>> result = getMinimumGroupByResult(tables, rowLength); 

       if (result.size() < numberOfRecords) { 

        tables.clear(); 

        for (List<Table> tableList : result) { 

         Table t = new Table(rowLength); 
         tables.add(t); 

         for (Table table : tableList) { 
          for (int i = 1; i <= rowLength; i++) { 
           t.getMap().get(i).addAll(table.getMap().get(i)); 
          } 
         } 
        } 
        numberOfRecords = tables.size(); 
       } else { 
        done = true; 
       } 
      } 

      tables.forEach(System.out::println); 
     } 

     private static Collection<List<Table>> getMinimumGroupByResult(List<Table> tables, int rowLength) { 

      Collection<List<Table>> result = null; 
      int min = Integer.MAX_VALUE; 

      for (List<Integer> keyCombination : getKeyCombinations(rowLength)) { 

       switch (rowLength) { 

        case 4: { 
         Map<Tuple3<TreeSet<Integer>, TreeSet<Integer>, TreeSet<Integer>>, List<Table>> map = 
           tables.stream().collect(Collectors.groupingBy(t -> new Tuple3<>(
             t.getMap().get(keyCombination.get(0)), 
             t.getMap().get(keyCombination.get(1)), 
             t.getMap().get(keyCombination.get(2)) 
           ))); 
         if (map.size() < min) { 
          min = map.size(); 
          result = map.values(); 
         } 
        } 
        break; 
        case 5: { 
         //TODO: Handle n = 5 
        } 
        break; 
        case 6: { 
         //TODO: Handle n = 6 
        } 
        break; 
       } 
      } 

      return result; 
     } 

     private static List<List<Integer>> getKeyCombinations(int rowLength) { 

      switch (rowLength) { 
       case 4: 
        return List.of(List.of(1, 2, 3), List.of(1, 2, 4), List.of(2, 3, 4), List.of(1, 3, 4)); 

       //TODO: handle n = 5, n = 6, etc... 
      } 

      return List.of(List.of()); 
     } 
    } 

輸出的tables.forEach(System.out::println)

Table{1=[1], 2=[3, 5, 6], 3=[8], 4=[11]} 
    Table{1=[1], 2=[3, 5], 3=[7], 4=[11]} 

或改寫可讀性：

 a | b | c | d 
    --|-------|---|--- 
    1 | 3,5,6 | 8 | 11 
    1 | 3,5 | 7 | 11 

如果你要在sql（mysql）中完成所有這些，你可以使用group_concat()，我認爲MS SQL在這裏有類似的內容：simulating-group-concat或STRING_AGG如果SQL Server 2017，但我認爲你將不得不使用文本列在這種情況下有點討厭：

eg

create table my_table (A varchar(50) not null, B varchar(50) not null, 
          C varchar(50) not null, D varchar(50) not null); 

    insert into my_table values ('1','3,5','4,15','11'), ('1','3,5','3,10','11'); 

    select A, B, group_concat(C order by C) as C, D from my_table group by A, B, D; 

會給結果的下方，所以你必須分析和排序，並更新逗號分隔的結果對任何未來合併迭代（按組）是正確的。

['1', '3,5', '3,10,4,15', '11']