Swift - Подмассивы определенной длины

Это своего рода проблема суммы подмножества.

Для положительных целых чисел это может быть решено с помощью динамического программирования со сложностью O(length * sum).

Составьте массив A длиной (sum + 1), заполненный нулями, установите A[0] = 1

Для каждого исходного значения v пройти массив A от A[sum] до A[v], проверяя, не равен ли A[i-v] нулю. Если да, пометьте ячейку A[i] с помощью A[i-v] + 1 (количество шагов (значений) для достижения этой ячейки).

Если A[sum] не равен нулю и все-таки содержит комбинацию с необходимым количеством шагов, эта сумма может быть составлена ​​из элементов массива.

Если вам нужно отслеживать также элементы, добавьте их значения в ячейки A[i], чтобы получить подмножество.

Это вариант проблема суммы подмножества или, в более общем смысле, Задача о рюкзаке. Следующее решение предполагает, что:

• Все элементы исходного массива строго положительны,
• Исходный массив может содержать повторяющиеся элементы,
• Если сумма не может быть достигнута, на выходе будет пустой массив.

Начнем с примера: создадим динамический стол, в котором мы попытаемся найти все способы получить 5, добавив элементы из [1, 2, 3, 4]:

В этой таблице строки представляют элементы массива в порядке возрастания плюс 0. Столбцы идут от 0 до суммы 5.

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

Количество растворов - это количество клеток, содержащих в себе true. В этом случае два решения:

1)

Зеленая ячейка - это true, поэтому текущая строка является последним элементом решения. В этом случае 3 - часть решения. Таким образом, проблема поиска подмассива, сумма которого равна 5, сводится к поиску подмассива, сумма которого равна 5 - 3. Это 2. Это представлено фиолетовым arrow 1: перейдите на пять столбцов влево и на 1 строку вверх.

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

С arrow 3 мы достигаем первой ячейки в первом столбце, соответствующей 5 - 3 - 2, то есть 0.

2)

Другой путь, который мы могли бы выбрать, начинается с красной клетки:

Как видите, проблема создания 5 из [1, 2, 3, 4] становится новой меньшей проблемой создания 1 из [1, 2, 3], затем 1 из [1, 2] и, наконец, 1 из `1.

Создадим и заполним динамическую таблицу:

var dynamicTable: [[Bool]] =
    Array(repeating: Array(repeating: false, count: sum + 1),
          count: array.count + 1)

//All of the elements of the first column are true
//since we can always make a zero sum out of not elements
for i in 0...array.count {
    dynamicTable[i][0] = true
}

for row in 1...array.count {
    for column in 1...sum {
        if column < array[row - 1] {
            dynamicTable[row][column] = dynamicTable[row - 1][column]
        } else {
            if dynamicTable[row - 1][column] {
                dynamicTable[row][column] = true
            } else {
                dynamicTable[row][column] = dynamicTable[row - 1][column - array[row - 1]]
            }
        }
    }
}

Найдем все пути, ведущие к сумме:

var solutions = [[Int]]()

func getSubArraysWithTheSum(arr: [Int], row: Int, currentSum: Int, currentSolution: [Int]) {

    //The following block will be executed when
    //we reach the first cell in the first column
    if row == 0,
        currentSum == 0
    {
        solutions.append(currentSolution)
        //notice the return to exit the scope
        return
    }

    //The following block will be executed if
    //the current cell is NOT used to reach the sum
    if dynamicTable[row - 1][currentSum]
    {
        getSubArraysWithTheSum(arr: arr,
                               row: row - 1,
                               currentSum: currentSum,
                               currentSolution: currentSolution)
    }

    //The following block will be executed if
    //the current cell IS used to reach the sum
    if currentSum >= arr[row - 1],
        dynamicTable[row - 1][currentSum - arr[row - 1]]
    {
        getSubArraysWithTheSum(arr: arr,
                               row: row - 1,
                               currentSum: currentSum - arr[row - 1],
                               currentSolution: currentSolution + [arr[row - 1]])
    }
}

Вся функция выглядит так:

func getSubArrays(from array: [Int], withSum sum: Int) -> [[Int]] {

    guard array.allSatisfy({ $0 > 0 }) else {
        fatalError("All the elements of the array must be strictly positive")
    }

    guard array.count > 0, sum > 0 else {
        return []
    }

    var solutions = [[Int]]()
    var dynamicTable: [[Bool]] =
        Array(repeating: Array(repeating: false, count: sum + 1),
              count: array.count + 1)

    //All of the elements of the first column are true
    //since we can always make a zero sum out of not elements
    for i in 0...array.count {
        dynamicTable[i][0] = true
    }

    for row in 1...array.count {
        for column in 1...sum {
            if column < array[row - 1] {
                dynamicTable[row][column] = dynamicTable[row - 1][column]
            } else {
                if dynamicTable[row - 1][column] {
                    dynamicTable[row][column] = true
                } else {
                    dynamicTable[row][column] = dynamicTable[row - 1][column - array[row - 1]]
                }
            }
        }
    }

    func getSubArraysWithTheSum(arr: [Int], row: Int, currentSum: Int, currentSolution: [Int]) {

        //The following block will be executed when
        //we reach the first cell in the first column
        if row == 0,
            currentSum == 0
        {
            solutions.append(currentSolution)
            return
        }

        //The following block will be executed if
        //the current cell is NOT used to reach the sum
        if dynamicTable[row - 1][currentSum]
        {
            getSubArraysWithTheSum(arr: arr,
                                   row: row - 1,
                                   currentSum: currentSum,
                                   currentSolution: currentSolution)
        }

        //The following block will be executed if
        //the current cell IS used to reach the sum
        if currentSum >= arr[row - 1],
            dynamicTable[row - 1][currentSum - arr[row - 1]]
        {
            getSubArraysWithTheSum(arr: arr,
                                   row: row - 1,
                                   currentSum: currentSum - arr[row - 1],
                                   currentSolution: currentSolution + [arr[row - 1]])
        }
    }

    getSubArraysWithTheSum(arr: array, row: array.count , currentSum: sum, currentSolution: [])

    return solutions
}

Вот несколько тестовых примеров:

getSubArrays(from: [3, 1, 4, 2], withSum: 5)        //[[3, 2], [4, 1]]
getSubArrays(from: [1, 2, 2, 4], withSum: 3)        //[[2, 1], [2, 1]]
getSubArrays(from: [7, 3, 4, 5, 6, 1], withSum: 9)  //[[5, 3, 1], [5, 4], [6, 3]]
getSubArrays(from: [3], withSum: 3)                 //[[3]]
getSubArrays(from: [5], withSum: 10)                //[]
getSubArrays(from: [1, 2], withSum: 0)              //[]
getSubArrays(from: [], withSum: 4)                  //[]

Это решение было вдохновлено вкладом Сумит Гошздесь. Подробное объяснение того, как строится динамическая таблица, можно найти в это видео.