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

Question

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.

IlyaMuravjov · Accepted Answer · 2019-10-19T13:08:29.040

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 } 
    }

Thank you, this does exactly what I wanted! Do you have any insight to share as to what was going wrong in my initial attempt? — Emil Jansson, Oct 19 '19 at 11:36
@EmilJansson Give me some time, and I will add an explanation of your mistakes to my answer. — IlyaMuravjov, Oct 19 '19 at 12:15

score 0 · Answer 2 · answered Oct 19 '19 at 01:19

0

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
    }
}

answered Oct 19 '19 at 01:19

Nathan Schwermann

31,285
16
80
91

Thanks! I'm still wondering if this is an efficient way of doing it though. Seems to me that I would be doing unnecessary work generating extra lists only to filter them later. – Emil Jansson Oct 19 '19 at 07:33

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

2 Answers2