swift - 如何在 Swift 中从 n 元素数组生成所有可能的 k 元素数组

Question

我想从n-element 数组创建所有 可能的k-element 数组。 k 可能大于或小于 n。输出数组中的元素不必是唯一的。

例如:

给定这个数组

let a = [1,2]

给定所需大小 3 的函数应返回:

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

示例 2

给定这个数组

let b = [[0,1], [2,3]]

给定所需大小 3 的函数应返回:

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

如何在 Swift 中做到这一点？

Answer 1

因此，您希望所有 k 元组都包含给定集合中的元素。这可以递归地完成通过将集合中的所有元素作为第一个元组元素并将其组合所有 (k-1) 个元组:

func allTupelsFrom<T>(elements: [T], withLength k : UInt,
    combinedWith prefix : [T] = []) -> [[T]] {

        if k == 0 {
            return [prefix]
        }

        var result : [[T]] = []
        for e in elements {
            result += allTupelsFrom(elements, withLength: k-1, combinedWith: prefix + [e])
        }
        return result
}

例子:

let result1 = allTupelsFrom([1, 2], withLength: 3)
println(result1)
// [[1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 2, 2], [2, 1, 1], [2, 1, 2], [2, 2, 1], [2, 2, 2]]

let result2 = allTupelsFrom(["a", "b", "c", "d"], withLength: 4)
println(result2)
// [[a, a, a, a], [a, a, a, b],  ... , [d, d, d, c], [d, d, d, d]]