naive, recursive and dynamic methods + bonus

import Foundation


//:Наивный метод, метод подстановки
func combinationsNaive(n: Int, k: Int) -> Int {
    var numerator = 1
    var denominator = 1

    for i in 0..<k {
        numerator *= n - i
        denominator *= i + 1
    }

    return numerator / denominator
}


//:Рекурсиыный метод
func combinationsRecursive(n: Int, k: Int) -> Int {
    if k == 0 || k == n {
        return 1
    } else {
        return combinationsRecursive(n: n-1, k: k-1) + combinationsRecursive(n: n-1, k: k)
    }
}

//:Динамическое программирование
func combinationsDynamic(n: Int, k: Int) -> Int {
    var cache = [[Int]](repeating: [Int](repeating: 0, count: k+1), count: n+1)

    for i in 0...n {
        for j in 0...min(i, k) {
            if j == 0 || j == i {
                cache[i][j] = 1
            } else {
                cache[i][j] = cache[i-1][j-1] + cache[i-1][j]
            }
        }
    }

    return cache[n][k]
}





//:Расчёт
func testCombinations() {
    let testCases = [(n: 5, k: 2), (n: 10, k: 3), (n: 15, k: 7), (n: 20, k: 10)]

    for (n, k) in testCases {
        print("n = \(n), k = \(k)")

        // Наивный алгоритм
        let startTime1 = DispatchTime.now()
        let result1 = combinationsNaive(n: n, k: k)
        let endTime1 = DispatchTime.now()
        let time1 = Double(endTime1.uptimeNanoseconds - startTime1.uptimeNanoseconds) / 1_000_000_000
        let iterations1 = k

        print("Наивный:        \(result1), время = \(time1), число итераций = \(iterations1)")

        // Рекурсивный метод
        let startTime2 = DispatchTime.now()
        let result2 = combinationsRecursive(n: n, k: k)
        let endTime2 = DispatchTime.now()
        let time2 = Double(endTime2.uptimeNanoseconds - startTime2.uptimeNanoseconds) / 1_000_000_000
        let iterations2 = pow(2, Double(k))

        print("Рекурсивный:    \(result2), время = \(time2), число итераций = \(iterations2)")

        // Динамическое программирование
        let startTime3 = DispatchTime.now()
        let result3 = combinationsDynamic(n: n, k: k)
        let endTime3 = DispatchTime.now()
        let time3 = Double(endTime3.uptimeNanoseconds - startTime3.uptimeNanoseconds) / 1_000_000_000
        let iterations3 = k * (k+1) / 2

        print("Динамический:      \(result3), время = \(time3), число итераций = \(iterations3)")
        print()
    }
}


testCombinations()


// Как можно видеть, наивный алгоритм работает быстро для маленьких значений `n` и `k`, но становится очень медленным при увеличении этих значений.
// Рекурсивный алгоритм работает лучше на больших значениях `n` и `k`, но его количество итераций растет экспоненциально.
// Динамическое программирование работает быстро для всех значений `n` и `k`, и его количество итераций растет линейно.









//:
//: МОЙ АЛГОРИТМ + БОНУС
//:


func combinations(_ n: Int, _ k: Int) -> (result: Int, iterations: Int) {
    var combinations: Double = 1
    var iterations = 0

    for i in (n - k + 1)...n {
        combinations *= Double(i)
        iterations += 1
    }

    for i in 2...k {
        combinations /= Double(i)
        iterations += 1
    }

    return (result: Int(combinations.rounded()), iterations: iterations)
}

//: Моя проверка
func testCombinationsMine() {
    let testCases = [
        (n: 5, k: 2),
        (n: 10, k: 3),
        (n: 15, k: 7),
        (n: 20, k: 10),
        (n: 30, k: 15)
    ]

    for (n, k) in testCases {
        print("n = \(n), k = \(k)")

        // Naive algorithm
        let startTime = DispatchTime.now()
        let (result, iterations) = combinations(n, k)
        let endTime = DispatchTime.now()
        let time = Double(endTime.uptimeNanoseconds - startTime.uptimeNanoseconds) / 1_000_000_000

        print("Result: \(result)")
        print("Iterations: \(iterations)")
        print("Time: \(time) seconds\n")
    }
}

testCombinationsMine()


//: Формула Стирлинга (бонус)


func combinationsStirling(n: Int, k: Int) -> Double {
    let logSqrt2π = 0.5 * log(2 * Double.pi)
    let logNFact = log(Double(n)) + logSqrt2π + Double(n) * log(Double(n))
    let logKFact = log(Double(k)) + logSqrt2π + Double(k) * log(Double(k))
    let logNKDiffFact = log(Double(n - k)) + logSqrt2π + Double(n - k) * log(Double(n - k))

    let logResult = logNFact - (logKFact + logNKDiffFact)

    return exp(logResult)
}

func testCombinationsStirling() {
    let testCases = [
        (n: 5, k: 2),
        (n: 10, k: 3),
        (n: 15, k: 7),
        (n: 20, k: 10),
        (n: 30, k: 15)
    ]

    for (n, k) in testCases {
        print("n = \(n), k = \(k)")

        // Stirling's approximation algorithm
        let startTime = DispatchTime.now()
        let result = combinationsStirling(n: n, k: k)
        let endTime = DispatchTime.now()
        let time = Double(endTime.uptimeNanoseconds - startTime.uptimeNanoseconds) / 1_000_000_000
        let iterations = 1

        print("Stirling's:   \(result), time = \(time), iterations = \(iterations)")
        print()
    }
}

testCombinationsStirling()