在 ArrayList 中进行元素组合 [Kotlin]

Question

我有一个元素的ArrayList，需要获取成对组合的元素。

例如：[A, B, C] 将被转换为 [[A, B], [A, C], [B, C]]

我目前使用传统的方式来实现此目的。

for(i in 0 until arr.size-1)
    for(j in i+1 until arr.size)
        //do stuff with arr[i], arr[j]

如果需要组合超过两个元素，我可能会编写递归函数来完成相同的操作。我的担忧是这种方法还是有点老派，可能不太像Kotlin函数式编程风格。

是否有更好的方式来实现这一点，同时还可以使组合数更多而不用进入递归？

- Deepan

---

为什么你害怕递归？Kotlin编译器能够使用关键字 tailrec 优化递归函数，而不会出现堆栈溢出的风险。详情请参见 https://kotlinlang.org/docs/reference/functions.html - Nikolai Shevchenko

谢谢，我并不害怕。我目前正在学习Kotlin，并且想知道是否有语言特性或者集合中的预定义函数，以便更好地理解Kotlin及其库。 - Deepan

Answer 1

为了增强其功能，您可以将产生和消费成对的过程解耦。

可以使用函数sequence编写成对生成器：

fun <T> elementPairs(arr: List<T>): Sequence<Pair<T, T>> = sequence {
    for(i in 0 until arr.size-1)
        for(j in i+1 until arr.size)
            yield(arr[i] to arr[j])
}

然后您可以使用该序列并以不同的方式处理成对的内容，例如。

fun main() {
    elementPairs(listOf('A', 'B', 'C', 'D')).forEach {
        println(it)
    }

    elementPairs(listOf("apple", "desk", "arc", "density", "array"))
        .filter { (a, b) -> a.first() == b.first() }
        .forEach { println("Starting with the same letter: $it") }
}

你可以在这里尝试：https://pl.kotl.in/dJ9mAiATc。

- Ilya

---

太棒了！解耦逻辑确实让它更加优雅。也许我可以编写一个扩展，使其适用于任何Iterable类。 - Deepan

Answer 2

val arr = arrayListOf("A", "B", "C", "D")
val list= mutableListOf<Pair<String, String>>()

arr.indices.forEach() { 
    i -> arr.indices.minus(0..i).forEach() { 
    j -> list.add(arr[i] to arr[j]) }
}
println(list)

输出

[(A, B), (A, C), (A, D), (B, C), (B, D), (C, D)]

- Kaloyan Karaivanov

Answer 3

对于 Kotlin 标准而言，上面的答案过于冗长。我认为可以使用 flatmap 来解决这个问题，更加简洁明了：

fun main() {
    val letters = "ABC".toList();
    val pairs = letters
        .flatMap {first -> letters
        .filter{second -> !first.equals(second)} // if you want to exclude "identity" pairs
        .map{second->first to second }};
    println(pairs)
}

- Ben

---

这会重复所有的组合。例如，它会返回"A,C"和"C,A" - 但是OP只想要其中一个。 - matt freake

Answer 4

所以被接受的答案创建了一对一对的组合。我创建了一个对象，可以处理任何长度的组合，最多可以到items.size-1。

class CombinationGenerator<T>(private val items: List<T>, choose: Int = 1) : Iterator<List<T>>, Iterable<List<T>> {
    private val indices = Array(choose) { it }
    private var first = true

    init {
        if (items.isEmpty() || choose > items.size || choose < 1)
            error("list must have more than 'choose' items and 'choose' min is 1")
    }

    override fun hasNext(): Boolean = indices.filterIndexed { index, it ->
        when (index) {
            indices.lastIndex -> items.lastIndex > it
            else -> indices[index + 1] - 1 > it
        }
    }.any()

    override fun next(): List<T> {
        if (!hasNext()) error("AINT NO MORE WHA HAPPEN")
        if (!first) {
            incrementAndCarry()
        } else
            first = false
        return List(indices.size) { items[indices[it]] }
    }

    private fun incrementAndCarry() {
        var carry = false
        var place = indices.lastIndex
        do {
            carry = if ((place == indices.lastIndex && indices[place] < items.lastIndex)
                    || (place != indices.lastIndex && indices[place] < indices[place + 1] - 1)) {
                indices[place]++
                (place + 1..indices.lastIndex).forEachIndexed { index, i ->
                    indices[i] = indices[place] + index + 1
                }
                false
            } else
                true
            place--
        } while (carry && place > -1)
    }

    override fun iterator(): Iterator<List<T>> = this
}

fun main() {
    val combGen = CombinationGenerator(listOf(1, 2, 3, 4), 3)
    combGen.map { println(it.joinToString()) }

}

- mavriksc

Answer 5

val arr = intArrayOf(1, 2, 3, 4) //test array

arr.indices.forEach() {
    i -> arr.indices.minus(0..i).forEach() {
    j -> println("${arr[i]} ${arr[j]}") } }

输出

1 3
1 4
2 3
2 4
3 4

- Kaloyan Karaivanov