Reverse Cartesian Product

Question

Given the data set below:

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

Perform a reverse Cartesian product to get:

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

I am currently working with scala, and my input/output data type is currently:

ListBuffer[Array[Array[Int]]]

I have come up with a solution (seen below), but feel it could be optimized. I am open to optimizations of my approach, and completely new approaches. Solutions in scala and c# are preferred.

I am also curious if this could be done in MS SQL.

My current solution:

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
  }

The way this works is:

1. Loop over columns, from right to left (the groupingIndex specifies which column to run on. This column is the only one which does not have to have values equal to each other in order to merge the rows.)
2. Recursively group the data on all other columns (not groupingIndex).
3. After grouping all columns, it is assumed that the data in each group have equivalent values in every column except for the grouping column.
4. Merge the rows with the matching columns. Take the distinct values for each column and sort each one.

I apologize if some of this does not make sense, my brain is not functioning today.

Answer 1

Here is my take on this. Code is in Java but could easily be converted into Scala or C#.

I run groupingBy on all combinations of n-1 and go with the one that has the lowest count, meaning largest merge depth, so this is kind of a greedy approach. However it is not guaranteed that you will find the optimal solution, meaning minimize the number k which is np-hard to do, see link here for an explanation, but you will find a solution that is valid and do it rather fast.

Full example 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());
        }
    }

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

or rewritten for readability:

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

If you were to do all this in sql (mysql) you could possibly use group_concat(), I think MS SQL has something similar here: simulating-group-concat or STRING_AGG if SQL Server 2017, but I think you would have to work with text columns which is a bit nasty in this case:

e.g.

    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;

Would give the result below, so you would have to parse and sort and update the comma separated result for any next merge iteration (group by) to be correct.

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