如何创建惰性组合

Question

我的问题很简单，如何让这段代码变懒：

/*
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=] })
}))

还不确定如何解决这个问题。

Answer 1

我找到了一种可能的解决方案，但我暂时不接受这个答案，看看是否有人知道更好的解决方案。

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.

Answer 2

这是我想出的：

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.

如何创建惰性组合

How to create lazy combinations

swift

functional-programming

lazy-sequences