Swift:将一组值 A 映射到 B，将 B 映射到 A

Question

任务:

考虑一组值，例如0, 1, 2, 现在想象其中的两个集合以及它们之间的双射关系。

如何在 Swift 中将其封装在数据结构中？

说明和示例:

示例映射可能如下所示:

0 <-> 1
1 <-> 2
2 <-> 0

经典的双向 hashmap 不太适合这个用例，因为两边的值都不唯一。

数据结构应该允许从两边查询:

let ds = DS(...)
let ds.right(from: 1) // 2
let ds.left(from: 0) // 2

实现这种数据结构的最简单方法是什么？我的实现可以基于哪些现有数据类型？

更新:

“两边的值都不唯一”是什么意思 “左侧”的值在该侧是唯一的，“右侧”的值也是如此。但是，如果值存在于一侧，它将始终存在于另一侧。因此，这些值不是唯一的。

能否举个非唯一值的例子，以及非唯一情况下right(from:)和left(from:)的预期结果？

澄清一下，左侧的所有值都是0,1,2。右侧还有 0,1,2。

查询示例:

ds.rightFrom(left: 2) -> 0
ds.rightFrom(left: 0) -> 1


ds.leftFrom(right: 0) -> 2
ds.leftFrom(right: 1) -> 0

Answer 1

从集合到自身的双射函数是 permutation .如果集合由从零开始的连续整数组成，则排列可以表示为数组。

在您的例子中，从 [0, 1, 2] 到自身定义的映射

0 -> 1, 1 -> 2, 2 -> 0

将表示为数组[1, 2, 0]。 “从左到右”的映射然后变成下标操作:

let perm = [1, 2, 0]

print(perm[1]) // 2

“从右到左”映射是逆排列，也可以表示为数组:

func inversePermution(of perm: [Int]) -> [Int]? {
    var inverse: [Int] = Array(repeating: -1, count: perm.count)
    for (idx, elem) in perm.enumerated() {
        // Check for valid entries:
        guard elem >= 0 && elem < perm.count else { return nil }
        // Check for duplicate entries:
        guard inverse[elem] == -1 else { return nil }
        // Set inverse mapping:
        inverse[elem] = idx
    }
    return inverse
}

(这只是为了演示一般的想法。当然你可以把它做成一个Array扩展方法，或者用这个和更多的方法定义一个Permutation类型。)

在你的例子中:

if let invPerm = inversePermution(of: perm) {
    print(invPerm) // [2, 0, 1]

    print(invPerm[2]) // 1
}