我如何使用现代 kotlin 函数技术来解决这个递归循环问题？

Question

我有一个 kotlin 问题，你能想出一个优雅的解决方法吗？

如此有效，我有一个对象列表，我想根据是否存在链来按顺序排列这些对象。这是模型对象

data class Sequence(
    val id: String,
    val previousSequence: List<String>
  )

所以 previousSequence 告诉你它是否在链中并且包含另一个序列的 id（或者它可以为空）。 previousSequence 是一个字符串列表，但您可以假设该列表只包含一个条目。（别问我是继承了别人的烂设计）

如此有效下面的测试数据

  Sequence("2b", listOf("1a")),
  Sequence("1a", emptyList()),
  Sequence("3c", listOf("2b")),
  Sequence("91z", emptyList()),
  Sequence("92z", listOf("91z")),
  Sequence("NO_CHAIN", emptyList())

结果列表列表如下：

[
  [
   Sequence(id=1a, previousSequence=[]), 
   Sequence(id=2b, previousSequence=[1a]), 
   Sequence(id=3c, previousSequence=[2b])
  ], 
  
  [
   Sequence(id=91z, previousSequence=[]), 
   Sequence(id=92z, previousSequence=[91z])
  ]
]

下面的代码有效..使用递归。但希望有一个更优雅的解决方案。你能想出一个吗？

data class Sequence(
    val id: String,
    val previousSequence: List<String>
  )

  @Test
  fun `Test chaining of sequence`() {
    val sequences = listOf(
      Sequence("2b", listOf("1a")),
      Sequence("1a", emptyList()),
      Sequence("3c", listOf("2b")),
      Sequence("91z", emptyList()),
      Sequence("92z", listOf("91z")),
      Sequence("NO_CHAIN", emptyList())
    )

    val sequenceChains = sequences.filter { it.previousSequence.isNotEmpty() }
    val baseOfChainList = sequences.filter { base ->
      base.previousSequence.isEmpty() && sequenceChains.any { it.previousSequence.contains(base.id) }
    }

    val listOfChains: MutableList<MutableList<Sequence>> = mutableListOf()

    baseOfChainList.forEach {
      val individualList: MutableList<Sequence> = mutableListOf()
      individualList.add(it)
      individualList.addAll(recursiveAddSequence(it.id, sequenceChains))
      listOfChains.add(individualList)
    }

    println(listOfChains)
  }


  fun recursiveAddSequence(id: String, sequenceChains: List<Sequence>): List<Sequence> {
    val individualChain: MutableList<Sequence> = mutableListOf()
    sequenceChains.forEach {
      if (it.previousSequence.contains(id)) {
        individualChain.add(it)
        individualChain.addAll(recursiveAddSequence(it.id, sequenceChains))
      }
    }
    return individualChain
  }

Answer 1

我们可以用下面的代码解决这个问题：

val (heads, notHeads) = sequences.partition { it.previousSequence.isEmpty() }
val sequencesByPrevious = notHeads.associateBy { it.previousSequence.first() }
val result = heads.map { head ->
    generateSequence(head) { sequencesByPrevious[it.id] }.toList()
}

首先，我们根据上一个项目准备一个项目地图。然后对于作为头部的每个项目（没有前一个项目），我们一次迭代下一个元素。

generateSequence() 是一个棘手的部分。此函数创建一个惰性且未绑定的项目序列（请注意，它与您的示例中的“序列”不同）。它通过将提供的 lambda 应用于前一个项目来获取后续项目，并一遍又一遍地执行此操作，直到它变为 null。这一行相当于这个循环：

val list = mutableListOf<Sequence>()
var curr: Sequence? = head
while (curr != null) {
    list += curr
    curr = sequencesByPrevious[curr.id]
}

如果我们对不属于任何链的元素不感兴趣（它们不引用也不被任何其他项目引用），那么我们可以简单地过滤掉它们（感谢@Joffrey）：

result.filter { it.size > 1 }

作为奖励：如果我是正确的，您的解决方案至少具有二次时间复杂度。以上解是线性的。

我如何使用现代 kotlin 函数技术来解决这个递归循环问题？

How can I use modern kotlin functional techniques to solve this recursive loop problem?

recursion

functional-programming

kotlin