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\$

1 Answer 1

Reset to default
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\$
6
  • \$\begingroup\$ Nice, a lot more terse. But do I understand correctly, that it raises the time complexity to O(n²)? \$\endgroup\$ Commented Sep 20, 2018 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\$ Commented Sep 20, 2018 at 10:06
  • \$\begingroup\$ adapted it slightly... still didn't do anything to improve the complexity itself ;-) \$\endgroup\$ Commented Sep 20, 2018 at 10:25
  • \$\begingroup\$ added variant with tailrec ;-) \$\endgroup\$ Commented Sep 20, 2018 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\$ Commented Sep 20, 2018 at 14:02

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.