Split a lists into multiple sub lists with predicate - looking for a nice way to write this code

user_1940385 0
Viewed 110

Lets say I have a list of integers: [2, 4, 4, 6, 1, 8, 3, 5, 2, 2, 2], and I want to split this lists into sub lists so each sub list contain values that match the predicate, or if it doesn't then only the value that didn't match, and it should be in the order of the original list.

So for example, if the predicate is "is even" I expect to get the following result: [[2, 4, 4, 6],[1],[8],[3, 5],[2, 2, 2]]

I have a code that works, but it's pretty ugly in my opinion and I feel like there should be a much nicer way to write it:

private fun <T : Any> toSubLists(values: List<T>, predicate: (T) -> Boolean): List<List<T>> {
  val subLists = mutableListOf<List<T>>()
  var currentList = mutableListOf<T>()
  values.forEach {
    if (!predicate(it)) {
      if (currentList.isNotEmpty()) {
        subLists.add(currentList)
        currentList = mutableListOf()
      }
      subLists.add(listOf(it))
    } else {
      currentList.add(it)
    }
  }
  if (currentList.isNotEmpty()) {
    subLists.add(currentList)
  }
  return subLists
}
kotlin data-structures algorithm
5 Answers

Not sure if it's better because it might be harder to understand, but this is a way to do it

private fun <T : Any> toSubLists(values: List<T>, predicate: (T) -> Boolean): List<List<T>> = 
    values.withIndex().groupBy({
        var index = it.index
        while (index != 0 && predicate(values[index]) && predicate(values[index - 1])) index--
        index
    }){
        it.value
    }.values.toList()

see it working here

user_15148610

There is a feature request for a generic version of this that accepts other key selectors than predicates.

In the meantime, for your use case I think we can simplify a bit:

fun <T> List<T>.groupRunsBy(predicate: (T) -> Boolean): List<List<T>> {
    val result = mutableListOf<MutableList<T>>()
    var currentlyMatching: Boolean? = null
    forEach {
        val itemMatches = predicate(it)
        if (itemMatches == currentlyMatching) {
            result.last().add(it)
        } else {
            currentlyMatching = itemMatches
            result.add(mutableListOf(it))
        }
    }
    return result
}

fun main() {
    val list = listOf(2, 4, 4, 6, 1, 8, 3, 5, 2, 2, 2)
    
    println(list.groupRunsBy { it % 2 == 0 }) // [[2, 4, 4, 6], [1], [8], [3, 5], [2, 2, 2]]
}

Tested here: https://pl.kotl.in/OHVr7S6lX

This version can easily be changed to support any selector that returns non-null keys.

user_15408180 
fun <T : Any> toSubLists(values: List<T>, predicate: (T) -> Boolean): List<List<T>> {
  val items = values.map { predicate(it) to listOf(it) }.toMutableList()
  for (i in items.indices.last downTo 1) {
    if (items[i - 1].first && items[i].first) {
      items[i - 1] = items[i - 1].first to items[i - 1].second + items[i].second
      items.removeAt(i)
    }
  }
  return items.map { it.second }
}

val list1 = listOf(2, 4, 4, 6, 1, 8, 3, 5, 2, 2, 2)
val isOdd: (Int) -> Boolean = { it % 2 != 0 }
val isEven: (Int) -> Boolean = { it % 2 == 0 }

println(toSubLists(list1, isOdd))   // [[2], [4], [4], [6], [1], [8], [3, 5], [2], [2], [2]]
println(toSubLists(list1, isEven))  // [[2, 4, 4, 6], [1], [8], [3], [5], [2, 2, 2]]
user_172184290 
fun <T : Any> toSubLists(values: List<T>, predicate: (T) -> Boolean): List<List<T>> {
  return values
    .map { listOf(predicate(it) to listOf(it)) }
    .reduce { acc, item ->
      if (acc.last().first && item.first().first)
        acc.subList(0, acc.size - 1) + listOf(acc.last().first to acc.last().second + item.first().second)
      else
        acc + item
    }
    .map { it.second }
}

val list1 = listOf(2, 4, 4, 6, 1, 8, 3, 5, 2, 2, 2)
val isOdd: (Int) -> Boolean = { it % 2 != 0 }
val isEven: (Int) -> Boolean = { it % 2 == 0 }

println(toSubLists(list1, isOdd))   // [[2], [4], [4], [6], [1], [8], [3, 5], [2], [2], [2]]
println(toSubLists(list1, isEven))  // [[2, 4, 4, 6], [1], [8], [3], [5], [2, 2, 2]]
user_172184290

Here's a naive recursive solution:

fun <E> toSubListsRecursive(
  list: List<E>,
  startIndex: Int = 0,
  accMainList: MutableList<List<E>> = mutableListOf(),
  accSubList: MutableList<E> = mutableListOf(),
  newAccSubListRequired: (Boolean) -> Boolean = { true },
  predicate: (E) -> Boolean
): List<List<E>> =
  if (list.lastIndex < startIndex) {
    accMainList
  } else {
    val currElement = list[startIndex]
    val currPredicateResult = predicate(currElement)
    val currAccSubList =
      if (newAccSubListRequired(currPredicateResult)) mutableListOf(currElement).also(accMainList::add)
      else accSubList.apply { add(currElement) }
    toSubListsRecursive(list, startIndex + 1, accMainList, currAccSubList, { x -> x != currPredicateResult }, predicate)
  }

A similar solution adapted to use fold:

data class Accumulator<E>(
  var mainList: MutableList<List<E>>,
  var subList: MutableList<E>,
  var newAccSubListRequired: (Boolean) -> Boolean
)

fun <E> toSubListsWithFold(list: List<E>, predicate: (E) -> Boolean): List<List<E>> =
  list.fold<E, Accumulator<E>>(Accumulator(mutableListOf(), mutableListOf()) { true }) { acc, currElement ->
    val currPredicateResult = predicate(currElement)
    val currSubAcc =
      if (acc.newAccSubListRequired(currPredicateResult)) mutableListOf(currElement).also(acc.mainList::add)
      else acc.subList.apply { add(currElement) }
    acc.apply {
      subList = currSubAcc;
      newAccSubListRequired = { x -> x != currPredicateResult }
    }
  }.mainList

If the predicate is not expensive you can simplify (adapted from this answer):

fun <E> anotherToSubListWithFold(list: List<E>, predicate: (E) -> Boolean): List<List<E>> =
  list.fold(mutableListOf<MutableList<E>>()) { acc, curr ->
    if (acc.isEmpty() || acc.last().first().let(predicate) != curr.let(predicate)) {
      acc.apply { add(mutableListOf(curr)) }
    } else {
      acc.apply { last().add(curr) }
    }
  }
user_12052990
Related