如何创建懒惰组合 [英] How to create lazy combinations
问题描述
我的问题很简单，我该如何让这段代码很懒：
/ *
input：[
[1,2]，
[3,4]，
[5,6]
]
输出：[
[ 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组合< T>（选项：[[T]]） - > [[T]] {
guard let head = options.first else {
return [] .map（{[$ 0]}）
}
如果选项.count == 1 {
return head.map（{[$ 0]}）
}
let tailCombinations = combinations（options：Array（options.dropFirst（）））
返回head.flatMap（{在
中的选项）return tailCombinations.map（{bb
返回[选项] +组合
}中的{组合 - > [T]）
}）
}
上面的代码用于计算组合，但它在内存中创建了整个数组数组。
我需要的是让它返回类似于 LazySequence< Array< T>> 的东西，除了Swift类型的系统不允许我执行通用。
任何想法如何实现这一点并保持功能风格？
另一种解决这个问题的方法是使用生成器并记录索引，但我不想追踪任何状态，我想要一个纯功能（如FP）解决方案。
Haskell在默认情况下执行它，顺便说一句，我正在寻找同样的东西。
编辑：使用 AnyCollection
来解决部分问题， func组合< T>（选项：[[T]]） - > LazyCollection< AnyCollection< [T]>> {
guard let head = options.first else {
return AnyCollection（[]。lazy.map（{[$ 0]}））。lazy
}
如果options.count == 1 {
return AnyCollection（head.lazy.map（{[$ 0]}））。lazy
}
let tailCombinations = combinations（options： Array（options.dropFirst（）））
返回AnyCollection（head.lazy.flatMap（{
中的选项）return tailCombinations.lazy.map（{[option] + $ 0}）
$）}）。lazy
}
但是当我使用函数时，在记忆中的整个集合，即不懒。
编辑2：做一些更多的调查，事实证明问题是与 AnyCollection
//保持懒惰
让x1 = head.lazy。 flatMap（{
中的选项return tailCombinations.lazy.map（{[option] + $ 0}）
}）
//强制加载内存
let x2 = AnyCollection（head.lazy.flatMap（{
中的选项return t ailCombinations.lazy.map（{[option] + $ 0}）
）））
不知道如何解决这个问题。
这是我想出来的：
pre $
func组合< 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 选项的序列
，然后结合
的每个元素都与最后一个选项的每个元素排列在一起。由于从递归调用
返回的序列仅枚举一次，而不是每个与
组合的元素一次，所以这是
的高效。
其他区别是：
- 不需要调用
.lazy AnySequence
，如果
序列已经是懒惰的。返回类型因此是简化的
到 AnySequence< [T]> 。
c $ c> CollectionOfOne 为空数组创建单元素序列。
选项。 count == 1 单独不是必需的用于算法的工作（但可能是一个可能的性能
改进）。
一种完全不同的方法是定义一个自定义的集合类型
，它将每个组合计算为使用
简单模算术：
struct组合< 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}
}
下标（索引：Int） - > [T] {
var i = index
var combination：[T] = []
combination.reserveCapacity（options.count）
options.forEach {
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 {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（重复：[1，2，3，4，5]，count：5）
这个基于集合的方法竟然比我上面基于序列的方法的
快了2倍。 p>
My question is very simple, how do I make this code lazy:
/*
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
})
})
}
The code above works to calculate the combinations, but it does so creating the entire array of arrays in memory.
What I need is to have it return something like LazySequence<Array<T>>, except the Swift type system doesn't let me do something that generic.
Any ideas how to achieve this and keep the functional style?
Ps.: I did think of another way to solve this problem with generators and keeping track of indexes, but I don't wanna keep track of any state, I want a pure functional (as in FP) solution. Haskell does it by default, btw, and I'm looking for the same thing.
EDIT: I've managed to solve part of the problem, the type system, with 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
}
But when I use the function, it loads the entire collection in memory, i.e., not lazy.
EDIT 2: Doing some more investigation, turns out the problem is with 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 })
}))
Not sure how to solve this yet.
Here is what I came up with:
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] }
})
}
The main difference to this solution is that the recursive
call creates a sequence
of the first N-1 options, and then combines each element of
that sequence with each element of the last option. This is more
efficient because the sequence returned from the recursive call
is enumerated only once, and not once for each element that it is
combined with.
Other differences are:
- There is no need to call
.lazyon theAnySequenceif that sequence is already lazy. The return type is therefore "simplified" toAnySequence<[T]>. - I have used
CollectionOfOneto create a single-element sequence for the empty array. - Treating the case
options.count == 1separately is not necessary for the algorithm to work (but might be a possible performance improvement).
A completely different approach is to define a custom collection type which computes each combination as a function of the index, using simple modulo arithmetic:
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()
}
}
No extra storage is needed and no recursion. Example usage:
let all = Combinations(options: [[1, 2], [3, 4], [5, 6]])
print(all.count)
for c in all { print(c) }
Output:
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]
Testing with
let options = Array(repeating: [1, 2, 3, 4, 5], count: 5)
this collection-based method turned out to be faster then the my above sequence-based method by a factor of 2.
这篇关于如何创建懒惰组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
