Создание метода, который генерирует все перестановки строки в kotlin с использованием рекурсии - PullRequest
Новая
       13

Создание метода, который генерирует все перестановки строки в kotlin с использованием рекурсии

1 голос
/ 23 марта 2020

пытается написать некоторый код, который генерирует все перестановки входной строки как рекурсивное упражнение, но не может понять, почему я получаю ошибку переполнения стека. 

fun main() {
    println(subSet(listOf("abcd")))
}

fun subSet(s: List<String>): List<String>{
    return listOf<String>() + createSubSets(s)
}

fun createSubSets(s: List<String>): List<String>{
    if(s.isEmpty()){
        return listOf()
    }
    return s.mapIndexed{i, elem ->
        elem + createSubSets(s.drop(i))
    }
}

Ответы [ 2 ]

0 голосов
/ 23 марта 2020

Ваша рекурсивная функция небезопасна. Он повторяется вечно, продолжает добавлять в стек, и поэтому вы получаете переполнение стека.

Помимо исправления вашего алгоритма, вы можете сделать две вещи, чтобы улучшить ситуацию:

  1. Добавьте условие выхода, чтобы в конце концов завершить работу функции. 
fun main() {
    println(subSet(listOf("a", "b", "c", "d")))
}

fun subSet(s: List<String>): List<String>{
    return createSubSets(s, 0)
}

fun createSubSets(s: List<String>, index: Int): List<String> {
    if (index > s.lastIndex) {
        return emptyList()
    }
    val otherElements = s.subList(0, index) + s.subList(index + 1, s.size)
    val element = s[index]
    return otherElements.map { element + it } + createSubSets(s, index + 1)
}

// [ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc]
Сделайте функцию хвостовой рекурсивной , чтобы даже при длинных строках она не переполнялась стеком. 
fun main() {
    println(subSet(listOf("a", "b", "c", "d")))
}

fun subSet(s: List<String>): List<String>{
    return createSubSets(s, 0, emptyList())
}

tailrec fun createSubSets(s: List<String>, index: Int, carryOn: List<String>): List<String> {
    if (index > s.lastIndex) {
        return carryOn
    }
    val otherElements = s.subList(0, index) + s.subList(index + 1, s.size)
    val element = s[index]
    return createSubSets(s, index + 1, carryOn + otherElements.map { element + it })
}

// [ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc]

Обратите внимание, что хвостовая рекурсивная версия всегда вызывает себя как последнее. В частности, он не выполняет никаких операций над результатом самого вызова. Вот почему он должен переносить результат на следующий вызов, но именно поэтому он безопасен для стека.

Наконец, обратите внимание, что вам вообще не нужна рекурсия для решения этой проблемы: 

fun main() {
    println(subSet(listOf("a", "b", "c", "d")))
}

fun subSet(s: List<String>): List<String>{
    return createSubSets(s)
}

fun createSubSets(s: List<String>): List<String> {
    return s.mapIndexed { i, element ->
        val otherElements = s.subList(0, i) + s.subList(i + 1, s.size)

        otherElements.map { element + it }
    }.flatten()
}

// [ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc]
0 голосов
/ 23 марта 2020

Это утверждение приводит к бесконечной рекурсии: 

return s.mapIndexed { i, elem ->
    elem + createSubSets(s.drop(i))
}

В ней первая итерация имеет значение i 0 (при этом elem является символом в индексе 0) и рекурсивный вызов createSubSets(s.drop(i)) эквивалентен createSubSets(s), поскольку удаление нулевых символов из строки возвращает исходную строку.

...