3
\$\begingroup\$

Given is a list with (possibly) non-unique elements.

My goal is to split this list into multiple lists, in sum containing the same elements, but separated in a way that no sublist contains each element value more than once.

A few examples to show the supposed result:

[1, 2, 2] -> [[1, 2], [2]]

[1, 2, 2, 3, 3, 4, 4, 4] -> [[1, 2, 3, 4], [2, 3, 4], [4]]

[4, 4, 1, 1, 4, 1, 3, 2, 1, 2, 5, 1, 2, 4, 4, 2, 5] ->
[[4, 1, 3, 2, 5], [4, 1, 2, 5], [4, 1, 2], [4, 1, 2], [4, 1]]

The order of the elements is not important. The fact that is it preserved is just a side-effect of my current implementation, but not needed. So the following would also be valid:

[1, 2, 2] -> [[2, 1], [2]]

My current implementation looks as follows:

fun <T> ungroupDuplicateValues(values: List<T>): List<List<T>> {
    val result: MutableList<List<T>> = mutableListOf()
    var counts = values.groupingBy { it }.eachCount().toMutableMap()
    while (counts.isNotEmpty()) {
        val newCounts: MutableMap<T, Int> = mutableMapOf()
        val subResult: MutableList<T> = mutableListOf()
        for ((value, count) in counts) {
            subResult.add(value)
            if (count > 1) {
                newCounts[value] = counts.getValue(value) - 1
            }
        }
        result.add(subResult)
        counts = newCounts
    }
    return result
}

It works, but feels kind of clumsy. Is there a more elegant/idiomatic (maybe functional) solution?

\$\endgroup\$
3
\$\begingroup\$

Played a bit with it... how do you like the following?

fun <T> ungroupDuplicateValues(values: List<T>): List<List<T>> {
  val countPerValue = values.groupingBy { it }.eachCount()
  val maxCount = countPerValue.map { it.value }.max() ?: 0
  return (1..maxCount).map { index ->
    countPerValue.filterValues { it >= index }
        .map { it.key }
  }
}

Complexity (in regards to O-notation) should be similar to yours...

Or the following variant using tailrec:

fun <T> ungroupDuplicateValues(values: List<T>) = ungroupDuplicateValues(values.toMutableList())

private tailrec fun <T> ungroupDuplicateValues(remainingValues : MutableList<T>, newValues : MutableList<List<T>> = mutableListOf()) : List<List<T>> {
  val values = remainingValues.distinct()
  newValues.add(values)
  values.forEach { remainingValues.remove(it) }
  return if (remainingValues.isEmpty()) newValues
         else ungroupDuplicateValues(remainingValues, newValues)
}

But don't ask me about the O-notation here. tailrec should be optimized, but as I still use a forEach { remove } it will probably still be O(n²).

If you rather prefer a direct assigned function (of the first shown solution), maybe the following is also ok for you:

fun <T> ungroupDuplicateValues(values: List<T>) =
  values.groupingBy { it }.eachCount().let { countPerValue ->
    (countPerValue.map { it.value }.max() ?: 0).let { maxCount ->
      (1..maxCount).map { index ->
        countPerValue.filterValues { it >= index }
            .map { it.key }
      }
    }
  }
\$\endgroup\$
  • \$\begingroup\$ Nice, a lot more terse. But do I understand correctly, that it raises the time complexity to O(n²)? \$\endgroup\$ – Tobias Hermann Sep 20 '18 at 9:36
  • \$\begingroup\$ It is probably as complex as yours... I think yours was already O(n²)... your while is hit m times (m < n) which will translate to O(m*n) which is basically O(n²)... \$\endgroup\$ – Roland Sep 20 '18 at 10:06
  • \$\begingroup\$ adapted it slightly... still didn't do anything to improve the complexity itself ;-) \$\endgroup\$ – Roland Sep 20 '18 at 10:25
  • \$\begingroup\$ added variant with tailrec ;-) \$\endgroup\$ – Roland Sep 20 '18 at 11:10
  • \$\begingroup\$ Thanks a lot. I like your first solution the most. And disregarding the toMutableMap call, which might be O(n*log(n)) in case of a map based on trees instead of hashing), the complexity of my solution should be O(n). Example 1: The list [1, 1, 1, 1, 1] will cause 5 iterations in the outer loop, with 1 in the inner loop each. Example 2: The list [1, 2, 3, 4, 5] will cause 1 outer iteration with 5 inner iterations. And I think your solution does the same. So my initial O(n²) statement was wrong. :) \$\endgroup\$ – Tobias Hermann Sep 20 '18 at 14:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.