1

Assume I have a list of list such this one: [["1","2","4"], ["5","6"], ["7"]]

I would like to write a function that returns all the possible sequences of numbers by taking only one number from each sublist.

An example of the output: [["1","5","7"], ["2","5","7"],["2","5",7"] continue...]

I thought about using multiple nested loops but the end result is not going to be "nice to look at".

So I was wondering if there is a cleaner way to deal with this using Kotlin collection APIs

This was the solution I came up with:

fun test():List<List<String>> {
        val test = mutableListOf(listOf("1","2","3"), listOf("5"), listOf("6"))
        val result:MutableMap<Int,MutableList<List<String>>> = mutableMapOf()
        for(i in test.indices) {
            if (!result.containsKey(i)) result[i] = mutableListOf()
            if (i == 0) test[i].forEach { result[i]!!.add(listOf(it)) }
            else {
                if (i-2 >= 0) result.remove(i-2)
                result[i-1]!!.forEach {prev ->
                    test[i].forEach {
                        result[i]!!.add(prev + listOf(it))
                    }
                }
            }
        }
        return result[test.size-1]
    }

This is how I modified the solution based on comments input, maybe it could come in handy for someone in the future.

fun test():List<List<String>> {
        return result[test.size-1]
    }

fun cartesianProduct(input: List<List<*>>): List<List<*>> {
        if (input.isEmpty()) return listOf()
        return if (input.size == 1) input[0].map { listOf(it) }
        else {
            val a = input[0]
            val b = input[1]
            val rest = input.filterIndexed{index, set -> index>1 }.toSet()
            (setOf(a, b).plus(rest))
                    .fold(listOf(listOf<Any?>())) { acc, set ->
                        acc.flatMap { list -> set.map { element -> list + element } }
                    }
        }
    }
Mattew Pina
  • 13
  • 3
  • 3
    Have you tried writing it? – Laksitha Ranasingha Jun 14 '20 at 20:54
  • you're correct that using nested loops is going to be a little ugly, though it could work. It would also wouldn't let you generalize to a list with anything other than 3 sub-lists. Maybe think about recursion where successive recursive function call works on the next sub-list. If recursion is new to you, maybe instead have an array of the current index into each of the sub-lists and have just 1 loop - on each iteration you change at least 1 sub-lists's index, though at times you'll also have to change which sub-list is current and reset some indexes as you move back "up" the lists. – Oliver Dain Jun 14 '20 at 21:19
  • This seems to basically be a cartesian product. See https://stackoverflow.com/questions/53749357/idiomatic-way-to-create-n-ary-cartesian-product-combinations-of-several-sets-of – user Jun 14 '20 at 21:25
  • Thank you guys for the input. I added my starting solution and the one I ended up after receiving the advice to use cartesian product. – Mattew Pina Jun 14 '20 at 21:51
  • Your solution is wrong for the case with one input. It is simply returning the input. – Tenfour04 Jun 14 '20 at 21:58
  • 1
    Fixed, thank you for pointing it out – Mattew Pina Jun 14 '20 at 22:06

1 Answers1

2

Here's a version of the answer here that's adapted to be more versatile:

fun <T> Collection<Iterable<T>>.getCartesianProduct(): List<List<T>> = 
        if (isEmpty()) emptyList()
        else drop(1).fold(first().map(::listOf)) { acc, iterable ->
            acc.flatMap { list ->
                iterable.map(list::plus)
            }
        }

fun main() {
    val input = listOf("124", "56", "7")
    val product = input.map(CharSequence::asIterable).getCartesianProduct()
    println(product)
}

outputs

[[1, 5, 7], [1, 6, 7], [2, 5, 7], [2, 6, 7], [4, 5, 7], [4, 6, 7]]
Tenfour04
  • 83,111
  • 11
  • 94
  • 154