Question: Reverse Cartesian Product

Question

Reverse Cartesian Product

Answers 0
Added at 2017-09-06 23:09
Tags
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.

Answers to

Reverse Cartesian Product

Source Show
◀ Wstecz