如何在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]]