小编典典

如何创建懒惰组合

swift

我的问题很简单,如何使这段代码变得懒惰:

/*
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类型系统不允许我做一些通用的事情。

有什么想法如何实现这一目标并保持功能风格吗?

附注:我确实想过用生成器解决这个问题并跟踪索引的另一种方法,但是我不想跟踪任何状态,我想要一个纯函数式(如FP中)的解决方案。Haskell默认情况下会这样做,顺便说一句,我正在寻找相同的东西。

编辑: 我已经设法解决了部分问题,类型系统,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 })
}))

尚不确定如何解决此问题。


阅读 269

收藏
2020-07-07

共1个答案

小编典典

这是我想出的:

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选项的序列,然后将该序列的每个元素与最后一个选项的每个元素组合在一起。这是更有效的,因为从递归调用返回的序列仅被枚举一次,而不是与其组合的每个元素一次。

其他区别是:

  • 如果该序列已经是惰性的.lazyAnySequence则无需调用。因此,返回类型“简化为” 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倍。

2020-07-07