CODEWITHSUNDEEP
kotlinfunctional-programmingcombinatorics
Emil Jansson
Emil Jansson

Reputation: 159

How can one generate non-exhaustive permutations of a certain length in a functional style

I am trying to create a function that generates all possible permutations of length n, where the objects being listed are taken non-exhaustively from a set S. I am trying to accomplish this with Kotlin in a functional style.

This is the same question as was asked for Python here: Generating permutations of a given length - Python The answer provided is Python specific and therefore does not help me.

I also found this: https://discuss.kotlinlang.org/t/cartesian-products/343 But have a hard time understanding if this is the same thing I'm trying to do.

I have written a function that comes close to accomplishing the task, but it returns all non-exhaustive permutations of length <= n which is not what I'm after. Here is the code:

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>>{

    return if (components.isEmpty() || length <= 0 ){
        listOf(listOf())
    }else{
        components.map { x ->  nonexhaustivePermutations(length-1, components)
            .map { y -> listOf(x) + y } }
            .fold(listOf(listOf()), { x, y -> x + y} )
    }
}

I would be thankful if someone points out my mistakes or suggests an entirely new approach to the problem.

Upvotes: 2

Views: 378

Answers (2)

IlyaMuravjov
IlyaMuravjov

Reputation: 2492

You can do it this way:

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>> =
    if (components.isEmpty() || length <= 0) listOf(emptyList())
    else nonexhaustivePermutations(length - 1, components)
        .flatMap { sub -> components.map { sub + it } }

Now I'll explain how you can fix your solution. First of all, I'll reformat it:

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>> =
    if (components.isEmpty() || length <= 0) listOf(listOf())
    else components.map { elm ->
        nonexhaustivePermutations(length - 1, components).map { sub -> listOf(elm) + sub }
    }.fold(listOf(listOf())) { result, elm -> result + elm }

The first problem is elm -> nonexhaustivePermutations(length - 1, components). Here you call nonexhaustivePermutations with the same arguments for each elm on each recursion step. So I suggest swapping components.map with nonexhaustivePermutations(length - 1, components).map:

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>> =
    if (components.isEmpty() || length <= 0) listOf(listOf())
    else nonexhaustivePermutations(length - 1, components).map { sub ->
        components.map { elm -> listOf(elm) + sub }
    }.fold(listOf(listOf())) { result, elm -> result + elm }

But in addition to significantly improving performance, this swapping also reorders the returned elements. It can partly be fixed by replacing listOf(elm) + sub with sub + elm:

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>> =
    if (components.isEmpty() || length <= 0) listOf(listOf())
    else nonexhaustivePermutations(length - 1, components).map { sub ->
        components.map { elm -> sub + elm }
    }.fold(listOf(listOf())) { result, elm -> result + elm }

If you run this method, you will see that it returns permutations in order of length increasing. So short permutations are added first. To be more precise, they are added at the time the list is created. So to get rid of them, fold(listOf(listOf())) must be replaced with fold(emptyList()):

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>> =
    if (components.isEmpty() || length <= 0) listOf(listOf())
    else nonexhaustivePermutations(length - 1, components).map { sub ->
        components.map { elm -> sub + elm }
    }.fold(emptyList()) { result, elm -> result + elm }

This version works properly. But the only thing the last line does is list flatting. And flatting can be combined with mapping by replacing map with flatMap:

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>> =
    if (components.isEmpty() || length <= 0) listOf(listOf())
    else nonexhaustivePermutations(length - 1, components).flatMap { sub ->
        components.map { elm -> sub + elm } 
    }

Upvotes: 2

Nathan Schwermann
Nathan Schwermann

Reputation: 31503

You did the hard part, now just tak on a filter in the end :-)

fun <T> nonexhaustivePermutations(length: Int, components: List<T>): List<List<T>>{

    return if (components.isEmpty() || length <= 0 ){
        listOf(listOf())
    }else{
        components.map { x ->
                nonexhaustivePermutations(length-1, components).map { y -> listOf(x) + y }
        }.fold(listOf(listOf<T>())) { x, y -> x + y}
    }.filter {
        it.size == length
    }
}

Upvotes: 0

Related Questions