generics - Swift 泛型函数(n 选 k)

Question

我正在尝试用 Swift 编写这段 JavaScript 代码:k_combinations

到目前为止，我在 Swift 中有这个:

import Foundation
import Cocoa

extension Array {
func slice(args: Int...) -> Array {
    var s = args[0]
    var e = self.count - 1
    if args.count > 1 { e = args[1] }

    if e < 0 {
        e += self.count
    }

    if s < 0 {
        s += self.count
    }

    let count = (s < e ? e-s : s-e)+1
    let inc = s < e ? 1 : -1
    var ret = Array()

    var idx = s
    for var i=0;i<count;i++  {
        ret.append(self[idx])
        idx += inc
    }
    return ret
  }
}

func kombinaatiot<T>(setti: Array<T>, k: Int) -> Array<Array<T>> {

var i: Int, j: Int

if (k > setti.count || k <= 0) {
    return []
}

if (k == setti.count) {
    return [setti]
}

if (k == 1) {
    var combs: Array<T> = []

    for var i = 0; i < setti.count; i++ {
        combs += [setti[i]]
    }
    return [combs]
}

var combs: Array<Array<T>> = [[]]

for var i = 0; i < setti.count - k + 1; i++ {
    var head = setti.slice(i,i + 1)
var tailcombs = kombinaatiot(setti.slice(i + 1), k - 1)
    for var j = 0; j < tailcombs.count; j++ {
combs += ([head + tailcombs[j]])

    }
}
    println(combs)
   return combs
}

但问题是我的函数打印

[[], [1, 2, 2, 3, 4], [2, 3, 3, 4], [3, 4, 4]]

什么时候打印

[[1,2], [1,3], [2, 3]

我在这里做错了什么？我是编码新手，我的 javascript 技能不是很好，但是那个 javascript 对我有用，但很快我就做不到了。

Answer 1

您的 Swift 翻译中的主要错误是对 JavaScript 的误解 slice(start, end)方法:该方法返回具有从给定起始索引到但不包括给定结束索引的索引的元素。您的 Swift 方法包括结束索引，这是错误的。

但是 Swift 已经内置了带有下标和范围语法的切片。示例:

let a = [0, 1, 2, 3]
let b = Array(a[1 ..< 3]) // from index 1 up to (but not including) 3
println(b) // [1, 2]

另一个错误是(并且可能已经存在于 JavaScript 代码中)，即对于 k == 0你必须返回[[]] ，即包含空选择的数组，而不是 [] .而这实际上是唯一需要特殊处理的情况。递归会自动正确处理所有其他情况。

最后，在一般情况下，您必须从一个空数组开始:

var combs: Array<Array<T>> = [] // not [[]]

这给出了以下方法:

func kombinaatiot<T>(setti: [T], k: UInt) -> [[T]] {

    if k == 0 {
        return [[]]
    }

    var combs: [[T]] = []
    for (i, head) in enumerate(setti) {
        let tailcombs = kombinaatiot(Array(setti[i+1 ..< setti.count]), k - 1)
        for tc in tailcombs {
            combs += [[head] + tc]
        }
    }
    return combs
}

一些说明:

• [T]是 Array<T> 的简写符号.
• 我已经用 for .. in 替换了“C 风格”循环更“swift ”的循环。
• k参数声明为无符号整数。