Swift 中的组合数学
import Combinatorics
for chars in Permutation(of:"swift") {
print(String(chars))
}
以下是随机访问迭代器，每个元素通过 [_:Int] 获得。会检查边界，如果超出范围，则会 fatalError()。
let p = Permutation(0, 1, 2, 3)
p.count // 24
p[0] // [0, 1, 2, 3]
p[p.count - 1] // [3, 2, 1, 0]
它们都支持以下形式的初始化器。
Permutation(seed:[Element], size:Int=default)
Permutation(of:Sequence, size:Int=default)
Permutation(_ source:Element…)
第一个是规范初始化器。size 指定迭代器返回的数组的大小，默认为 seed.count。第二个形式是为了方便，在这种情况下，任何 Sequence 都会被转换为 [Element]。
返回一个迭代器，该迭代器返回排列后的数组。
var p = Permutation(of:"abcd")
p.count // 24
p[p.count-1] // ["d","c","b","a"]
p.map { $0 } // [["a","b","c","d"]...["d","c","b","a"]]
p = Permutation(of:"abcd", size:2)
p.count // 12
p[p.count-1] // ["d", "c"]
p.map { $0 } // [["a","b"] ... ["d","c"]]
返回一个迭代器，该迭代器返回排列后的数组，但具有相同元素的数组被视为相同，而不管顺序如何。因此，您不应省略 size，否则您只会得到一个结果。
var c = Combination(of:"abcd")
c.count // 1
c[c.count-1] // ["a","b","c","d"]
c.map { $0 } // [["a","b","c","d"]]
c = Combination(of:"abcd", size:2)
c.count // 6
c[c.count-1] // ["c","d"]
c.map { $0 } // [["a","b"],["a","c"],["a","d"],["b","c"], ["b","d"], ["c","d"]]
返回一个迭代器，该迭代器返回相应的“数字”。
var d = BaseN(of:0...3)
d.count // 4 ** 4 == 256
d[d.count-1] // [3,3,3,3]
d.map { $0 } // [[0,0,0,0]...[3,3,3,3]]
d = BaseN(of:0...3, size:2)
d.count // 16
d[d.count-1] // [3,3]
d.map { $0 } // [[0,0]...[3,3]]
返回一个迭代器，该迭代器返回每次迭代的幂集的元素。 size 固定为 seed.count，其中 seed 是源序列。
let s = PowerSet(of:0...3)
s.count // 2 ** 4 == 16
s.map { $0 } // [[],[0],[1],[0,1]...[0,1,2,3]]
返回一个迭代器，该迭代器返回每次迭代的笛卡尔积的元素。
let suits = "♠️♦️❤️♣️"
let ranks = 1..13
let cp = CartesianProduct(suits, ranks)
cp.count // 52
cp.map { $0 } //[("♠️",1)...("♣️",13)]
与其他迭代器不同，CartesianProduct 接受两个 Collection，并以元组形式返回它们的笛卡尔积。它们的 .Element 的类型不必匹配。
迭代器本身也是一个集合，因此您可以通过连续应用乘数来构建多维笛卡尔积。
let cp = CartesianProduct("01", "abc")
let cpcp = CartesianProduct(cp, "ATCG")
cp.count // 24
cpcp.map{ $0 } // [(("0","a"),"A")...(("1","c"),"G")]
如您所见，CartesianProduct 返回一个元组。这在数学上是正确的，但更难使用。但是在 Swift 中，(T,T) 与 (T,T,T) 是不同的类型，因此您无法编写一个返回不同长度的元组的函数。
为了缓解这种情况，Combinatorics 提供了 ProductSet。所有元素的类型必须相同，但您会得到一个数组而不是元组。
let ps = ProductSet([0,1],[2,4,6],[3,6,9,12],[4,8,12,16,20])
ps.count // 2 * 3 * 4 * 5 == 120
ps.map{ $0 } // [[0, 2, 3, 4] ... [1, 6, 12, 20]]
此模块还附带以下算术函数，这些函数作为静态函数捆绑在 Combinatorics 中。
// T:SignedInteger
Combinatorics.factorial<T>(_ n:T)->T
Combinatorics.permutation<T>(_ n:T, _ k:T)->T
Combinatorics.combination<T>(_ n:T, _ k:T)->T
如您所见，它们被通用地定义，因此您不仅可以使用 Int，还可以使用 BigInt（如果可用）。
在底层，上面的迭代器定义如下
public typealias Permutation = CombinatoricsIndex<Int>.Permutation
public typealias Combination = CombinatoricsIndex<Int>.Combination
// …
public typealias ProductSet = CombinatoricsIndex<Int>.ProductSet
为什么？因为 Int 通常对于组合数学来说足够大。幸运的是，Swift 允许您通用地定义 subscript，其索引不必是 Int。 请参阅 BigCombinatorics 以了解如何使用 BigInt 索引。
$ git clone https://github.com/dankogai/swift-combinatorics.git
$ cd swift-combinatorics # the following assumes your $PWD is here
$ swift build
简单地
$ scripts/run-repl.sh
或者
$ swift build && swift -I.build/debug -L.build/debug -lCombinatorics
在您的 repl 中，
1> import Combinatorics
2> Permutation(of:"swift").map{ String($0) }
$R0: [String] = 120 values {
[0] = "swift"
[1] = "switf"
[2] = "swfit"
// ...
[119] = "tfiws"
}
Xcode 项目被故意排除在存储库之外，因为它应该通过 swift package generate-xcodeproj 生成。 为方便起见，您可以
$ scripts/prep-xcode
然后 Workspace 会打开， Playground 在顶部。 该 Playground 是作为手册编写的。
不幸的是，Swift Package Manager 不支持 iOS。 更糟糕的是，Swift Playgrounds 不支持模块。 但是不用担心。 此模块非常紧凑，您只需要复制 Combinatorics.swift。
如果是 Swift Playgrounds，只需将其复制到 Sources 文件夹下即可。 如果您太懒，只需运行
$ scripts/ios-prep.sh
并且 iOS/Combinatorics.playground 就设置好了。 您不必在其中 import Combinatorics。
将以下内容添加到 dependencies 部分
.package(
url: "https://github.com/dankogai/swift-combinatorics.git", from: "0.0.1"
)
并将以下内容添加到 .target 参数
.target(
name: "YourSwiftyPackage",
dependencies: ["Combinatorics"])
现在您所要做的就是
import Combinatorics
在您的代码中。 尽情享受吧！
Swift 4.1 或更高版本，OS X 或 Linux 用于构建。