如何创建惰性组合
How to create lazy combinations
我的问题很简单,如何让这段代码变懒:
/*
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({ [[=10=]] })
}
if options.count == 1 {
return head.map({ [[=10=]] })
}
let tailCombinations = combinations(options: Array(options.dropFirst()))
return head.flatMap({ option in
return tailCombinations.map({ combination -> [T] in
return [option] + combination
})
})
}
上面的代码用于计算组合,但这样做是在内存中创建整个数组。
我需要的是 return 类似 LazySequence<Array<T>>
的东西,除了 Swift 类型系统不允许我做那些通用的事情。
有什么想法可以实现这一点并保持功能风格吗?
Ps.: 我确实想到了另一种方法来用生成器解决这个问题并跟踪索引,但我不想跟踪任何状态,我想要一个纯函数(如FP) 解决方案。
Haskell 默认情况下会这样做,顺便说一句,我正在寻找同样的东西。
编辑: 我已经设法解决了部分问题,即类型系统,AnyCollection
func combinations<T>(options: [[T]]) -> LazyCollection<AnyCollection<[T]>> {
guard let head = options.first else {
return AnyCollection([].lazy.map({ [[=11=]] })).lazy
}
if options.count == 1 {
return AnyCollection(head.lazy.map({ [[=11=]] })).lazy
}
let tailCombinations = combinations(options: Array(options.dropFirst()))
return AnyCollection(head.lazy.flatMap({ option in
return tailCombinations.lazy.map({ [option] + [=11=] })
})).lazy
}
但是当我使用该函数时,它会将整个集合加载到内存中,即不懒惰。
编辑 2: 进行更多调查后发现问题出在 AnyCollection
// stays lazy
let x1 = head.lazy.flatMap({ option in
return tailCombinations.lazy.map({ [option] + [=12=] })
})
// forces to load in memory
let x2 = AnyCollection(head.lazy.flatMap({ option in
return tailCombinations.lazy.map({ [option] + [=12=] })
}))
还不确定如何解决这个问题。
我找到了一种可能的解决方案,但我暂时不接受这个答案,看看是否有人知道更好的解决方案。
func combinations<T>(options: [[T]]) -> LazySequence<AnySequence<[T]>> {
guard let head = options.first else {
return AnySequence([].lazy.map({ [[=10=]] })).lazy
}
if options.count == 1 {
return AnySequence(head.lazy.map({ [[=10=]] })).lazy
}
let tailCombinations = combinations(options: Array(options.dropFirst()))
return AnySequence(head.lazy.flatMap({ option in
return tailCombinations.lazy.map({ [option] + [=10=] })
})).lazy
}
解决方案是使用 AnySequence
而不是 AnyCollection
。
我不确定为什么,我仍然想要 AnyCollection
接口而不是 AnySequence
,因为它为我提供了更多方法,例如 count
.
这是我想出的:
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 + [[=10=]] }
})
}
与的主要区别在于递归
调用创建一个序列
首先 N-1
选项,然后组合每个元素
该序列与最后一个选项的每个元素。这是更多
高效,因为序列 returned 来自递归调用
只枚举一次,而不是对它所代表的每个元素枚举一次
结合.
其他区别是:
- 如果
AnySequence
上没有必要调用 .lazy
序列已经是惰性的。 return 类型因此是 "simplified"
至 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) { [=11=] * .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.
我的问题很简单,如何让这段代码变懒:
/*
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({ [[=10=]] })
}
if options.count == 1 {
return head.map({ [[=10=]] })
}
let tailCombinations = combinations(options: Array(options.dropFirst()))
return head.flatMap({ option in
return tailCombinations.map({ combination -> [T] in
return [option] + combination
})
})
}
上面的代码用于计算组合,但这样做是在内存中创建整个数组。
我需要的是 return 类似 LazySequence<Array<T>>
的东西,除了 Swift 类型系统不允许我做那些通用的事情。
有什么想法可以实现这一点并保持功能风格吗?
Ps.: 我确实想到了另一种方法来用生成器解决这个问题并跟踪索引,但我不想跟踪任何状态,我想要一个纯函数(如FP) 解决方案。 Haskell 默认情况下会这样做,顺便说一句,我正在寻找同样的东西。
编辑: 我已经设法解决了部分问题,即类型系统,AnyCollection
func combinations<T>(options: [[T]]) -> LazyCollection<AnyCollection<[T]>> {
guard let head = options.first else {
return AnyCollection([].lazy.map({ [[=11=]] })).lazy
}
if options.count == 1 {
return AnyCollection(head.lazy.map({ [[=11=]] })).lazy
}
let tailCombinations = combinations(options: Array(options.dropFirst()))
return AnyCollection(head.lazy.flatMap({ option in
return tailCombinations.lazy.map({ [option] + [=11=] })
})).lazy
}
但是当我使用该函数时,它会将整个集合加载到内存中,即不懒惰。
编辑 2: 进行更多调查后发现问题出在 AnyCollection
// stays lazy
let x1 = head.lazy.flatMap({ option in
return tailCombinations.lazy.map({ [option] + [=12=] })
})
// forces to load in memory
let x2 = AnyCollection(head.lazy.flatMap({ option in
return tailCombinations.lazy.map({ [option] + [=12=] })
}))
还不确定如何解决这个问题。
我找到了一种可能的解决方案,但我暂时不接受这个答案,看看是否有人知道更好的解决方案。
func combinations<T>(options: [[T]]) -> LazySequence<AnySequence<[T]>> {
guard let head = options.first else {
return AnySequence([].lazy.map({ [[=10=]] })).lazy
}
if options.count == 1 {
return AnySequence(head.lazy.map({ [[=10=]] })).lazy
}
let tailCombinations = combinations(options: Array(options.dropFirst()))
return AnySequence(head.lazy.flatMap({ option in
return tailCombinations.lazy.map({ [option] + [=10=] })
})).lazy
}
解决方案是使用 AnySequence
而不是 AnyCollection
。
我不确定为什么,我仍然想要 AnyCollection
接口而不是 AnySequence
,因为它为我提供了更多方法,例如 count
.
这是我想出的:
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 + [[=10=]] }
})
}
与N-1
选项,然后组合每个元素
该序列与最后一个选项的每个元素。这是更多
高效,因为序列 returned 来自递归调用
只枚举一次,而不是对它所代表的每个元素枚举一次
结合.
其他区别是:
- 如果
AnySequence
上没有必要调用.lazy
序列已经是惰性的。 return 类型因此是 "simplified" 至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) { [=11=] * .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.