Лучший подход к рекурсии?

Question

Я построил этот образец кода в Swift Playgrounds как доказательство концепции для части более крупного проекта, над которым я работаю. Что мне нужно сделать, это передать ряд опций (представленных optionsArray или testArray), где каждый int - количество доступных опций. Эти варианты в конечном итоге будут встроены в 300 миллионов отдельных PDF-файлов и файлов HTML. В настоящее время этот код работает, и выдает огромный список возможностей, которые я хочу.

Мой вопрос заключается в следующем: есть ли более эффективный подход к управлению подобной ситуацией? Есть ли что-то более элегантное или эффективное? Это не что-то, что будет запускаться в прямом эфире в приложении или что-то еще, оно будет запускаться из командной строки и принимать все необходимое, но если есть лучший подход к производительности или стабильности, я все уши.

Вещи, которые я уже знаю: он не может обрабатывать значение 0, выходящее из массива. Массив является константой, поэтому это не произойдет случайно. То, как код в строке будет обрабатывать вещи, 0 - это бессмысленное значение для использования. Каждый элемент представляет количество доступных опций, поэтому 2 по существу является логическим, 1 будет false. Поэтому, если мне нужны элементы-заполнители для будущего расширения, они будут иметь значение 1 и отображаться как 0 в выводе.

Кроме того, конечный продукт будет не просто штриховым текстом на консоль в качестве вывода, он напишет файл в функции permutationEnding() на основе массива currentOptions.

let optionsArray: [Int] = [7,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,2,2,2,2,2,2,2,2] 
let testArray: [Int] = [7,2,3,2] 
var currentOptions: [Int] = [] 
var outputString: String = "" 
func buildPermutations(array: Array<Int>) { 
    currentOptions.removeAll() 
    permutationRecursion(array: array, index: 0) 
} 
func permutationRecursion(array: Array<Int>, index: Int) { 
    for i in 1 ... array[index] { 
     currentOptions.append(Int(i-1)) 
     if array.count > (index + 1) { 
      permutationRecursion(array: array, index: index + 1) 
     } else { 
      permutationEnding() 
     } 
     currentOptions.removeLast() 
    } 
} 
func permutationEnding() { 
    for i in 1 ... currentOptions.count { // Output Elements 
     outputString += String(currentOptions[i-1]) 
    } 
    outputString += "\n" // Goes after output elements closing bracket. 
} 
// buildPermutations(array: optionsArray) 
buildPermutations(array: testArray) 
print(outputString) 

Мысли?

Answer 1

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

Я получил это до четырех или пяти линий.

let n = testArray.count // for readability 
let products = ([Int](1...n)).map({testArray[$0..<n].reduce(1, *)}) 

// products is the cross product of element i + 1 to element n of the array for all i in the array 

let zipped = zip(testArray, products) 

for i in 0..<testArray.reduce(1, *) { // this reduce is the cross product of the whole array 

    let treePath = zipped.map(){ String(i/$0.1 % $0.0) }.joined() 
    outputString += treePath + "\n" 
} 

Еще одно редактирование: я думаю, что это может быть быстрее с некоторыми причудливыми матричными операциями, такими как NumPy. Интересно, может ли рамка Accelerate сделать для вас какую-то магию, но я не работал с ней.

редактировать: Мне было интересно, так что я засек с этим тест-массив

let testArray: [Int] = [7,2,2,2,2,2,2,3,2] 

рекурсивная функция в этом вопросе был: 132.56 сек

почтового индекса карта здесь был: 14,44 s

И он выглядит экспоненциальным, так как я добавляю элементы в тестовый массив.