5

Is there a short/idiomatic way to iterate through every pair of elements in a collection?

Even better would be a method that iterates through all fixed-cardinality subsets of a collection.

The classic and ugly approach would be:

val s = setOf(1, 2, 3, 4)

for (i in s) {
    for (j in s) {
        if (i != j) {
            println("$i $j")
        }
    }
}

For having bigger subsets, more loops are necessary, so this isn't scalable.

Moritz Groß
  • 1,352
  • 12
  • 30
  • Not sure you can do much better than that. Keep in mind that the `if` condition `i != j` might work for sets but it will produce possibly odd results for lists. If you have `listOf(1,1,1,1,1)` that loop won't do anything. It might be what you want, but I don't know. – al3c Jun 26 '20 at 11:10
  • Do you mean something like [this](https://stackoverflow.com/questions/53749357/idiomatic-way-to-create-n-ary-cartesian-product-combinations-of-several-sets-of)? – Lino Jun 26 '20 at 11:48
  • Cartesian products and subsets are similar, but different. So I guess sadly not @Lino – Moritz Groß Jun 26 '20 at 11:52
  • I think the technical term here is [2-permutations](https://en.wikipedia.org/wiki/Permutation#k-permutations_of_n). – gidds Jun 26 '20 at 13:11
  • Check out this https://www.baeldung.com/kotlin/split-list-into-parts – Ravi Mar 26 '21 at 11:27

3 Answers3

3

I think you got already the most idiomatic way to solve it. If you want to do it more functional, this is what you can convert it to:

s.map { i -> s.map { i to it } }
    .flatten()
    .filter { (left, right) -> left != right }
    .onEach { (i, j) -> println("$i $j") }
Neo
  • 1,869
  • 1
  • 7
  • 20
3

This is technically also O(n^2) but will have a little less than half as many iterations: (n^2 - n) / 2

val l = s.toList()
for (i in s.indices) {
    for (j in i + 1 until s.size) {
        println("${l[i]}, ${l[j]}")
        println("${l[j]}, ${l[i]}")
    }
}
Tenfour04
  • 83,111
  • 11
  • 94
  • 154
1

If you find an implementation of the power set operation, you can take all elements of the power set with length = 2.

aax
  • 394
  • 5
  • 10
  • Yes, thats true. But for a set of size n the powerset has size 2^n. This runtime is horrible. The number of pairs for example is only n^2 asymptotically. – Moritz Groß Jun 26 '20 at 12:36