Как можно генерировать неисчерпывающие перестановки определенной длины в функциональном стиле

Question

Я пытаюсь создать функцию, которая генерирует все возможные перестановки длины n, где перечисленные объекты взяты не исчерпывающе из набора S. Я пытаюсь сделать это с помощью Kotlin в функциональном стиле.

Это тот же вопрос, который был задан для Python: Генерация перестановок заданной длины - Python Предоставленный ответ является специфическим для Python и поэтому не помогает мне.

Я такженашел это: https://discuss.kotlinlang.org/t/cartesian-products/343 Но мне трудно понять, если это то же самое, что я пытаюсь сделать.

Я написал функцию, которая близка к выполнению задачи, но она возвращаетвсе неисчерпывающие перестановки длины <= n, что не то, что я ищу. Вот код: </p>

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

Я был бы благодарен, если бы кто-то указал на мои ошибки или предложил совершенно новый подход к проблеме.

Answer 1

Вы можете сделать это следующим образом:

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

---

Теперь я объясню, как вы можете исправить свое решение. Прежде всего, я переформатирую это:

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 }

Первая проблема - elm -> nonexhaustivePermutations(length - 1, components). Здесь вы вызываете nonexhaustivePermutations с одинаковыми аргументами для каждого elm на каждом шаге рекурсии. Поэтому я предлагаю заменить components.map на 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 }

Но в дополнение к значительному улучшению производительности этот обмен также изменяет порядок возвращаемых элементов. Это можно частично исправить, заменив listOf(elm) + sub на 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 }

Если вы запустите этот метод, вы увидите, что он возвращает перестановки в порядке увеличения длины. Поэтому короткие перестановки добавляются в первую очередь. Чтобы быть более точным, они добавляются во время создания списка. Таким образом, чтобы избавиться от них, fold(listOf(listOf())) необходимо заменить на 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 }

Эта версия работает правильно. Но единственное, что делает последняя строка - это выравнивание списка. И выравнивание можно объединить с отображением, заменив map на 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 } 
    }

Answer 2

Вы выполнили сложную часть, а теперь просто добавьте фильтр в конце: -)

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