我的问题很简单,如何使这段代码变得懒惰:
/* input: [ [1, 2], [3, 4], [5, 6] ] output: [ [1, 3, 5], [1, 3, 6], [1, 4, 5], [1, 4, 6], [2, 3, 5], [2, 3, 6], [2, 4, 5], [2, 4, 6], ] */ func combinations<T>(options: [[T]]) -> [[T]] { guard let head = options.first else { return [].map({ [$0] }) } if options.count == 1 { return head.map({ [$0] }) } let tailCombinations = combinations(options: Array(options.dropFirst())) return head.flatMap({ option in return tailCombinations.map({ combination -> [T] in return [option] + combination }) }) }
上面的代码可以计算组合,但是可以在内存中创建整个数组数组。我需要让它返回类似的东西LazySequence<Array<T>>,除了Swift类型系统不允许我做一些通用的事情。
LazySequence<Array<T>>
有什么想法如何实现这一目标并保持功能风格吗?
附注:我确实想过用生成器解决这个问题并跟踪索引的另一种方法,但是我不想跟踪任何状态,我想要一个纯函数式(如FP中)的解决方案。Haskell默认情况下会这样做,顺便说一句,我正在寻找相同的东西。
编辑: 我已经设法解决了部分问题,类型系统,AnyCollection
AnyCollection
func combinations<T>(options: [[T]]) -> LazyCollection<AnyCollection<[T]>> { guard let head = options.first else { return AnyCollection([].lazy.map({ [$0] })).lazy } if options.count == 1 { return AnyCollection(head.lazy.map({ [$0] })).lazy } let tailCombinations = combinations(options: Array(options.dropFirst())) return AnyCollection(head.lazy.flatMap({ option in return tailCombinations.lazy.map({ [option] + $0 }) })).lazy }
但是,当我使用该函数时,它将整个集合加载到内存中,即不是惰性的。
编辑2: 做更多的调查,结果问题出在AnyCollection
// stays lazy let x1 = head.lazy.flatMap({ option in return tailCombinations.lazy.map({ [option] + $0 }) }) // forces to load in memory let x2 = AnyCollection(head.lazy.flatMap({ option in return tailCombinations.lazy.map({ [option] + $0 }) }))
尚不确定如何解决此问题。
这是我想出的:
func combinations<T>(options: [[T]]) -> AnySequence<[T]> { guard let lastOption = options.last else { return AnySequence(CollectionOfOne([])) } let headCombinations = combinations(options: Array(options.dropLast())) return AnySequence(headCombinations.lazy.flatMap { head in lastOption.lazy.map { head + [$0] } }) }
此解决方案的主要区别在于,递归调用创建了 第一个 N-1选项的序列,然后将该序列的每个元素与最后一个选项的每个元素组合在一起。这是更有效的,因为从递归调用返回的序列仅被枚举一次,而不是与其组合的每个元素一次。
N-1
其他区别是:
.lazy
AnySequence
AnySequence<[T]>
CollectionOfOne
options.count == 1
完全不同的方法是定义一个自定义 集合类型 ,该 类型 使用简单的模运算来计算每个组合作为索引的函数:
struct Combinations<T> : RandomAccessCollection { let options: [[T]] let startIndex = 0 let endIndex: Int init(options: [[T]]) { self.options = options.reversed() self.endIndex = options.reduce(1) { $0 * $1.count } } subscript(index: Int) -> [T] { var i = index var combination: [T] = [] combination.reserveCapacity(options.count) options.forEach { option in combination.append(option[i % option.count]) i /= option.count } return combination.reversed() } }
无需额外的存储,也无需递归。用法示例:
let all = Combinations(options: [[1, 2], [3, 4], [5, 6]]) print(all.count) for c in all { print(c) }
输出:
8 [1、3、5] [1、3、6] [1,4,5] [1,4,6] [2,3,5] [2、3、6] [2,4,5] [2,4,6]
用测试
let options = Array(repeating: [1, 2, 3, 4, 5], count: 5)
这种基于集合的方法比上面基于序列的方法要快2倍。