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] -&gt; [[1, 2], [2]]

[1, 2, 2, 3, 3, 4, 4, 4] -&gt; [[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] -&gt;
[[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] -&gt; [[2, 1], [2]]


My current implementation looks as follows:

fun &lt;T&gt; ungroupDuplicateValues(values: List&lt;T&gt;): List&lt;List&lt;T&gt;&gt; {
    val result: MutableList&lt;List&lt;T&gt;&gt; = mutableListOf()
    var counts = values.groupingBy { it }.eachCount().toMutableMap()
    while (counts.isNotEmpty()) {
        val newCounts: MutableMap&lt;T, Int&gt; = mutableMapOf()
        val subResult: MutableList&lt;T&gt; = mutableListOf()
        for ((value, count) in counts) {
            subResult.add(value)
            if (count &gt; 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?
Played a bit with it... how do you like the following?

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


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

Or the following variant using tailrec:

fun &lt;T&gt; ungroupDuplicateValues(values: List&lt;T&gt;) = ungroupDuplicateValues(values.toMutableList())

private tailrec fun &lt;T&gt; ungroupDuplicateValues(remainingValues : MutableList&lt;T&gt;, newValues : MutableList&lt;List&lt;T&gt;&gt; = mutableListOf()) : List&lt;List&lt;T&gt;&gt; {
  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 &lt;T&gt; ungroupDuplicateValues(values: List&lt;T&gt;) =
  values.groupingBy { it }.eachCount().let { countPerValue -&gt;
    (countPerValue.map { it.value }.max() ?: 0).let { maxCount -&gt;
      (1..maxCount).map { index -&gt;
        countPerValue.filterValues { it &gt;= index }
            .map { it.key }
      }
    }
  }