# Ungrouping of values into multiple lists

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) {
if (count > 1) {
newCounts[value] = counts.getValue(value) - 1
}
}
counts = newCounts
}
return result
}


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

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()
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 }
}
}
}

• Nice, a lot more terse. But do I understand correctly, that it raises the time complexity to O(n²)? – Tobias Hermann Sep 20 '18 at 9:36
• 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²)... – Roland Sep 20 '18 at 10:06
• adapted it slightly... still didn't do anything to improve the complexity itself ;-) – Roland Sep 20 '18 at 10:25
• added variant with tailrec ;-) – Roland Sep 20 '18 at 11:10
• 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. :) – Tobias Hermann Sep 20 '18 at 14:02