拓冰网站定制 ：两集合笛卡尔积的惰性遍历指南)
开发工具【免费下载链接】swift-algorithmsCommonly used sequence and collection algorithms for Swift项目地址https://gitcode.com/gh_mirrors/swi/swift-algorithms点击查看免费下载product(_:_:)是 Swift Algorithms 开源包提供的高阶组合算法它把两个集合的所有元素两两配对成二元组并惰性产出等价于两个嵌套的for循环。本文围绕 Guides/Product.md 的设计文档结合 Product.swift 的完整实现与 ProductTests.swift 的测试用例讲解它的使用方式、类型约束、复杂度、命名权衡与多语言对比读完即可在项目里正确、高效地使用并理解这个 API。product 的功能与基本用法product的核心语义是迭代两个不同集合中每一对元素的组合返回一个产生二元组tuple的序列。设计文档给出了最直观的示例——把年份范围与季节列表做配对let seasons [winter, spring, summer, fall] for (year, season) in product(1900...2020, seasons) { // ... }这等价于手写两个嵌套循环for years in 1900...2020 { for season in seasons { // ... } }也就是说product不是并发压缩那是Zip2Sequence的职责而是笛卡尔积式的全组合遍历。源码 Product.swift 中的文档注释给出了更具体的输出顺序先拿第一个集合的首个元素依次与第二个集合的每个元素配对再拿第一个集合的第二个元素重复此过程依此类推顺序是确定且一致的let numbers 1...3 let colors [cerise, puce, heliotrope] for (number, color) in product(numbers, colors) { print(\(number): \(color)) } // 1: cerise // 1: puce // 1: heliotrope // 2: cerise // 2: puce // 2: heliotrope // 3: cerise // 3: puce // 3: heliotrope空集合的边界行为当两个输入中任意一个为空时结果序列也是空的。这一点在设计文档中被明确说明并同时被测试覆盖——ProductTests.swift 中验证了product(1...10, )与product(, 1...10)都产生空结果expectEqualSequences(product(1...10, ), [], by: ) expectEqualSequences(product(, 1...10), [], by: )即使其中一个集合有 10 个元素只要另一侧为空count依然为 0。这一点也体现在startIndex的实现上当base2为空时起点直接指向base1.endIndex见 Product.swift。详细设计为什么需要序列 集合的组合product的公开签名Product.swift如下public func productBase1: Sequence, Base2: Collection( _ s1: Base1, _ s2: Base2 ) - Product2SequenceBase1, Base2不对称的约束Base1 是 SequenceBase2 是 Collection两个参数的类型约束并不对称这是刻意的设计Base2必须满足Collection因为内层集合需要对每一个外层元素被完整重新遍历一次。以product(1...3, colors)为例colors会被从头到尾扫 3 遍这就要求它具备可重复遍历的能力而Sequence并不保证这一点比如一次性流式序列就无法回放。Base1只需满足Sequence外层序列在整个过程中只被完整遍历一次因此不需要Collection约束这放宽了可用输入的范围。Product2Sequence一个按能力逐级升级的包装类型Product2Sequence结构体Product.swift内部持有两个基础类型外层base1与内层base2本身只做包装构造开销极小public struct Product2SequenceBase1: Sequence, Base2: Collection { internal let base1: Base1 internal let base2: Base2 }它的协议能力是逐级条件升级的完全取决于两个基础类型的既有能力两个基础类型的约束Product2Sequence获得的能力任意SequenceCollectionSequence基础形态可for遍历两个都是CollectionCollection支持下标与索引两个都是BidirectionalCollectionBidirectionalCollection支持反向遍历两个都是RandomAccessCollectionRandomAccessCollection支持 O(1) 索引偏移这三层扩展分别对应源码中的三处声明extension Product2Sequence: Collection where Base1: CollectionProduct.swift、extension Product2Sequence: BidirectionalCollection where Base1: BidirectionalCollection, Base2: BidirectionalCollectionProduct.swift以及extension Product2Sequence: RandomAccessCollection where Base1: RandomAccessCollection, Base2: RandomAccessCollectionProduct.swift。正因如此当两个输入都是RandomAccessCollection时product的结果也支持reversed()、distance(from:to:)、index(_:offsetBy:)等随机访问操作——ProductTests.swift 中的testProductReversed就验证了product(1...2, AB).reversed()的输出为(2, B), (2, A), (1, B), (1, A)。为什么不提供高元数版本Product3、Product4……设计文档明确说明当前不提供Product3Sequence、Product4Sequence等更高元数的类型目的是与 Swift 标准库的Zip2Sequence保持一致的设计口径。如果确实需要三元组乃至更高维度的组合通过多次嵌套调用product即可自行组合例如product(product(a, b), c)外层调用产生((a, b), c)再手动扁平化。这种组合而非特设的做法保持了 API 面最小化。索引类型与下标当升级为Collection时Product2Sequence定义了自己的IndexProduct.swift它由两个基础索引i1、i2构成比较顺序遵循字典序先比较i1再比较i2并实现了Comparable。核心的下标操作是public subscript(position: Index) - (Base1.Element, Base2.Element) { (base1[position.i1], base2[position.i2]) }count的实现直截了当base1.count * base2.countProduct.swift。注意startIndex的特殊处理——当base2为空时起点被设为base1.endIndex这正是空集合情形下序列表现为空的关键所在。迭代器的实现原理Product2Sequence.IteratorProduct.swift内部维护三个状态外层迭代器i1、内层迭代器i2、以及当前缓存的element1。其next()的核心逻辑是首次调用或上一轮已耗尽时先取外层下一个元素element1 i1.next()若外层已空则永久返回nil从内层i2.next()取一个元素与element1组成二元组返回内层耗尽后取外层的下一个元素并用base2.makeIterator()重新创建内层迭代器再取内层首元素返回。这套状态机正是外层只遍历一次、内层遍历base1.count次这一复杂度特征的直接体现。由于它只保存当前元素和迭代器引用而不预先物化全部配对product是惰性的——即使输入集合很大也可以边产出边消费。复杂度分析设计文档给出的复杂度结论分两个层面构造product的调用本身是 O(1)它只是把两个基础类型包进Product2Sequence不拷贝元素、不预先计算全部配对。源码中product函数体只有一行Product2Sequence(s1, s2)Product.swift可作印证对结果进行集合操作的复杂度是 O(m × n)其中m base1.count、n base2.count完整遍历一遍结果自然需要访问全部m × n个二元组。同理count属性虽然通过乘法 O(1) 得出但真正遍历所有元素的开销始终是m × n量级。测试 ProductTests.swift 验证了索引距离计算product([1, 2], abc)的distance(from: startIndex, to: endIndex)等于 6即2 × 3。testProductIndexTraversalsProductTests.swift则用IndexValidator系统性验证了四种组合非空×非空、非空×空、空×非空、空×空下索引遍历的合法性与expectedCount4*3、4*0、0*3、0*0覆盖了所有空与非空的边界。值得注意的是distance(from:to:)与index(_:offsetBy:)的实现Product.swift做了精细的数学处理通过完整穿越内层集合的轮数full cycles把二维索引距离拆解为段与轮的组合计算避免逐元素推进。源码注释中用l、c、r示意区段直观地说明了在两层索引之间换算距离的推导过程。命名与乘法的语义冲突product一词源于数学中的笛卡尔积cartesian product这也是该函数在多种语言中的先例命名。但设计文档坦承存在一个不幸的重叠product同时也是乘法运算的结果product of numbers。因此看到product(numbers1, numbers2)时读者有可能误以为这是两个数组的逐元素相乘element-wise product而非全组合配对。这是 API 命名上的已知取舍使用时需要在文档注释与上下文里加以区分。与其他语言的对比设计文档用两个代表性语言做了横向对比帮助理解本实现的定位RubyArray#product方法可以传入一个或多个数组返回 n 元组的数组。传入单个数组时语义与本函数完全一致两个集合的笛卡尔积。Pythonitertools.product传入两个及以上集合时返回这些集合的笛卡尔积如果只传一个集合并配合repeatn参数则等价于把该集合重复n次参与组合。文档给出的例子product(ABC, repeat2)产出AA, AB, AC, BA, BB, BC, CA, CB, CC—— 这实际上等价于 Swift 中的product(ABC, ABC)外层内层配对只是语法层面 Python 用repeat参数省去了显式传同一个集合两次。可以看到本库的product(_:_:)定位更聚焦固定为二元组合通过重复传入同一集合或嵌套调用来覆盖 Pythonrepeat与 Ruby n 元组的场景与标准库Zip2Sequence的二元结构保持一致。在项目中安装与使用product(_:_:)随Algorithms库一起发布。参照 README.md 的说明在 SwiftPM 项目中把它加入依赖// Package.swift 的 dependencies 中 .package(url: https://github.com/apple/swift-algorithms, from: 1.2.0),再为目标声明依赖.target(name: target, dependencies: [ .product(name: Algorithms, package: swift-algorithms), ]),最后在源码中import Algorithms即可使用product(_:_:)以及库中其他算法。本仓库的 Package.swift 定义了名为Algorithms的库目标与SwiftAlgorithmsTests测试目标product的实现位于Algorithms目标内随库一并编译分发。典型应用场景小结组合遍历两个维度如年份 × 季节、用户 × 权限、坐标 × 颜色的全配对枚举替代手写嵌套循环代码更声明式惰性消费输入为大集合时product不预先物化全部配对适合与lazy链式操作或提前break的遍历配合避免一次性分配m × n个元组可随机访问的组合当两个输入都是RandomAccessCollection时结果支持按索引直接定位到某个特定配对如取第k个组合配合distance/offsetBy可实现组合空间的随机采样式访问。一句话总结product(_:_:)用 O(1) 的包装成本把一个两两配对的全组合问题封装成符合 Swift 集合协议体系的惰性序列能力随输入自动升级是嵌套循环在表达力与性能之间的一个优雅中间点。赞分享开发工具【免费下载链接】swift-algorithmsCommonly used sequence and collection algorithms for Swift项目地址https://gitcode.com/gh_mirrors/swi/swift-algorithms点击查看免费下载相关推荐Swift Algorithms笛卡尔积10个product方法在组合问题中的终极应用指南Swift Algorithms笛卡尔积10个product方法在组合问题中的终极应用指南 Swift Algorithms是一个为Swift开发者提供常用序开发工具30 seconds of code用 JavaScript 实现两个数组的笛卡尔积Cartesian Product30 seconds of code用 JavaScript 实现两个数组的笛卡尔积Cartesian Product 笛卡尔积Cartesian pr教程文档es-toolkit 迭代器 cartesianProduct 全解析惰性笛卡尔积、无限序列与 pipe 组合实战es toolkit 迭代器 cartesianProduct 全解析惰性笛卡尔积、无限序列与 pipe 组合实战 导读 cartesianProduct 前端后端上一篇React Container Query 项目教程下一篇终极指南掌握path-to-regexp参数匹配轻松应对复杂路由模式创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Swift Algorithms 之 product(_:_:)：两集合笛卡尔积的惰性遍历指南
开发工具【免费下载链接】swift-algorithmsCommonly used sequence and collection algorithms for Swift项目地址https://gitcode.com/gh_mirrors/swi/swift-algorithms点击查看免费下载product(_:_:)是 Swift Algorithms 开源包提供的高阶组合算法它把两个集合的所有元素两两配对成二元组并惰性产出等价于两个嵌套的for循环。本文围绕 Guides/Product.md 的设计文档结合 Product.swift 的完整实现与 ProductTests.swift 的测试用例讲解它的使用方式、类型约束、复杂度、命名权衡与多语言对比读完即可在项目里正确、高效地使用并理解这个 API。product 的功能与基本用法product的核心语义是迭代两个不同集合中每一对元素的组合返回一个产生二元组tuple的序列。设计文档给出了最直观的示例——把年份范围与季节列表做配对let seasons [winter, spring, summer, fall] for (year, season) in product(1900...2020, seasons) { // ... }这等价于手写两个嵌套循环for years in 1900...2020 { for season in seasons { // ... } }也就是说product不是并发压缩那是Zip2Sequence的职责而是笛卡尔积式的全组合遍历。源码 Product.swift 中的文档注释给出了更具体的输出顺序先拿第一个集合的首个元素依次与第二个集合的每个元素配对再拿第一个集合的第二个元素重复此过程依此类推顺序是确定且一致的let numbers 1...3 let colors [cerise, puce, heliotrope] for (number, color) in product(numbers, colors) { print(\(number): \(color)) } // 1: cerise // 1: puce // 1: heliotrope // 2: cerise // 2: puce // 2: heliotrope // 3: cerise // 3: puce // 3: heliotrope空集合的边界行为当两个输入中任意一个为空时结果序列也是空的。这一点在设计文档中被明确说明并同时被测试覆盖——ProductTests.swift 中验证了product(1...10, )与product(, 1...10)都产生空结果expectEqualSequences(product(1...10, ), [], by: ) expectEqualSequences(product(, 1...10), [], by: )即使其中一个集合有 10 个元素只要另一侧为空count依然为 0。这一点也体现在startIndex的实现上当base2为空时起点直接指向base1.endIndex见 Product.swift。详细设计为什么需要序列 集合的组合product的公开签名Product.swift如下public func productBase1: Sequence, Base2: Collection( _ s1: Base1, _ s2: Base2 ) - Product2SequenceBase1, Base2不对称的约束Base1 是 SequenceBase2 是 Collection两个参数的类型约束并不对称这是刻意的设计Base2必须满足Collection因为内层集合需要对每一个外层元素被完整重新遍历一次。以product(1...3, colors)为例colors会被从头到尾扫 3 遍这就要求它具备可重复遍历的能力而Sequence并不保证这一点比如一次性流式序列就无法回放。Base1只需满足Sequence外层序列在整个过程中只被完整遍历一次因此不需要Collection约束这放宽了可用输入的范围。Product2Sequence一个按能力逐级升级的包装类型Product2Sequence结构体Product.swift内部持有两个基础类型外层base1与内层base2本身只做包装构造开销极小public struct Product2SequenceBase1: Sequence, Base2: Collection { internal let base1: Base1 internal let base2: Base2 }它的协议能力是逐级条件升级的完全取决于两个基础类型的既有能力两个基础类型的约束Product2Sequence获得的能力任意SequenceCollectionSequence基础形态可for遍历两个都是CollectionCollection支持下标与索引两个都是BidirectionalCollectionBidirectionalCollection支持反向遍历两个都是RandomAccessCollectionRandomAccessCollection支持 O(1) 索引偏移这三层扩展分别对应源码中的三处声明extension Product2Sequence: Collection where Base1: CollectionProduct.swift、extension Product2Sequence: BidirectionalCollection where Base1: BidirectionalCollection, Base2: BidirectionalCollectionProduct.swift以及extension Product2Sequence: RandomAccessCollection where Base1: RandomAccessCollection, Base2: RandomAccessCollectionProduct.swift。正因如此当两个输入都是RandomAccessCollection时product的结果也支持reversed()、distance(from:to:)、index(_:offsetBy:)等随机访问操作——ProductTests.swift 中的testProductReversed就验证了product(1...2, AB).reversed()的输出为(2, B), (2, A), (1, B), (1, A)。为什么不提供高元数版本Product3、Product4……设计文档明确说明当前不提供Product3Sequence、Product4Sequence等更高元数的类型目的是与 Swift 标准库的Zip2Sequence保持一致的设计口径。如果确实需要三元组乃至更高维度的组合通过多次嵌套调用product即可自行组合例如product(product(a, b), c)外层调用产生((a, b), c)再手动扁平化。这种组合而非特设的做法保持了 API 面最小化。索引类型与下标当升级为Collection时Product2Sequence定义了自己的IndexProduct.swift它由两个基础索引i1、i2构成比较顺序遵循字典序先比较i1再比较i2并实现了Comparable。核心的下标操作是public subscript(position: Index) - (Base1.Element, Base2.Element) { (base1[position.i1], base2[position.i2]) }count的实现直截了当base1.count * base2.countProduct.swift。注意startIndex的特殊处理——当base2为空时起点被设为base1.endIndex这正是空集合情形下序列表现为空的关键所在。迭代器的实现原理Product2Sequence.IteratorProduct.swift内部维护三个状态外层迭代器i1、内层迭代器i2、以及当前缓存的element1。其next()的核心逻辑是首次调用或上一轮已耗尽时先取外层下一个元素element1 i1.next()若外层已空则永久返回nil从内层i2.next()取一个元素与element1组成二元组返回内层耗尽后取外层的下一个元素并用base2.makeIterator()重新创建内层迭代器再取内层首元素返回。这套状态机正是外层只遍历一次、内层遍历base1.count次这一复杂度特征的直接体现。由于它只保存当前元素和迭代器引用而不预先物化全部配对product是惰性的——即使输入集合很大也可以边产出边消费。复杂度分析设计文档给出的复杂度结论分两个层面构造product的调用本身是 O(1)它只是把两个基础类型包进Product2Sequence不拷贝元素、不预先计算全部配对。源码中product函数体只有一行Product2Sequence(s1, s2)Product.swift可作印证对结果进行集合操作的复杂度是 O(m × n)其中m base1.count、n base2.count完整遍历一遍结果自然需要访问全部m × n个二元组。同理count属性虽然通过乘法 O(1) 得出但真正遍历所有元素的开销始终是m × n量级。测试 ProductTests.swift 验证了索引距离计算product([1, 2], abc)的distance(from: startIndex, to: endIndex)等于 6即2 × 3。testProductIndexTraversalsProductTests.swift则用IndexValidator系统性验证了四种组合非空×非空、非空×空、空×非空、空×空下索引遍历的合法性与expectedCount4*3、4*0、0*3、0*0覆盖了所有空与非空的边界。值得注意的是distance(from:to:)与index(_:offsetBy:)的实现Product.swift做了精细的数学处理通过完整穿越内层集合的轮数full cycles把二维索引距离拆解为段与轮的组合计算避免逐元素推进。源码注释中用l、c、r示意区段直观地说明了在两层索引之间换算距离的推导过程。命名与乘法的语义冲突product一词源于数学中的笛卡尔积cartesian product这也是该函数在多种语言中的先例命名。但设计文档坦承存在一个不幸的重叠product同时也是乘法运算的结果product of numbers。因此看到product(numbers1, numbers2)时读者有可能误以为这是两个数组的逐元素相乘element-wise product而非全组合配对。这是 API 命名上的已知取舍使用时需要在文档注释与上下文里加以区分。与其他语言的对比设计文档用两个代表性语言做了横向对比帮助理解本实现的定位RubyArray#product方法可以传入一个或多个数组返回 n 元组的数组。传入单个数组时语义与本函数完全一致两个集合的笛卡尔积。Pythonitertools.product传入两个及以上集合时返回这些集合的笛卡尔积如果只传一个集合并配合repeatn参数则等价于把该集合重复n次参与组合。文档给出的例子product(ABC, repeat2)产出AA, AB, AC, BA, BB, BC, CA, CB, CC—— 这实际上等价于 Swift 中的product(ABC, ABC)外层内层配对只是语法层面 Python 用repeat参数省去了显式传同一个集合两次。可以看到本库的product(_:_:)定位更聚焦固定为二元组合通过重复传入同一集合或嵌套调用来覆盖 Pythonrepeat与 Ruby n 元组的场景与标准库Zip2Sequence的二元结构保持一致。在项目中安装与使用product(_:_:)随Algorithms库一起发布。参照 README.md 的说明在 SwiftPM 项目中把它加入依赖// Package.swift 的 dependencies 中 .package(url: https://github.com/apple/swift-algorithms, from: 1.2.0),再为目标声明依赖.target(name: target, dependencies: [ .product(name: Algorithms, package: swift-algorithms), ]),最后在源码中import Algorithms即可使用product(_:_:)以及库中其他算法。本仓库的 Package.swift 定义了名为Algorithms的库目标与SwiftAlgorithmsTests测试目标product的实现位于Algorithms目标内随库一并编译分发。典型应用场景小结组合遍历两个维度如年份 × 季节、用户 × 权限、坐标 × 颜色的全配对枚举替代手写嵌套循环代码更声明式惰性消费输入为大集合时product不预先物化全部配对适合与lazy链式操作或提前break的遍历配合避免一次性分配m × n个元组可随机访问的组合当两个输入都是RandomAccessCollection时结果支持按索引直接定位到某个特定配对如取第k个组合配合distance/offsetBy可实现组合空间的随机采样式访问。一句话总结product(_:_:)用 O(1) 的包装成本把一个两两配对的全组合问题封装成符合 Swift 集合协议体系的惰性序列能力随输入自动升级是嵌套循环在表达力与性能之间的一个优雅中间点。赞分享开发工具【免费下载链接】swift-algorithmsCommonly used sequence and collection algorithms for Swift项目地址https://gitcode.com/gh_mirrors/swi/swift-algorithms点击查看免费下载相关推荐Swift Algorithms笛卡尔积10个product方法在组合问题中的终极应用指南Swift Algorithms笛卡尔积10个product方法在组合问题中的终极应用指南 Swift Algorithms是一个为Swift开发者提供常用序开发工具30 seconds of code用 JavaScript 实现两个数组的笛卡尔积Cartesian Product30 seconds of code用 JavaScript 实现两个数组的笛卡尔积Cartesian Product 笛卡尔积Cartesian pr教程文档es-toolkit 迭代器 cartesianProduct 全解析惰性笛卡尔积、无限序列与 pipe 组合实战es toolkit 迭代器 cartesianProduct 全解析惰性笛卡尔积、无限序列与 pipe 组合实战 导读 cartesianProduct 前端后端上一篇React Container Query 项目教程下一篇终极指南掌握path-to-regexp参数匹配轻松应对复杂路由模式创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考