The task:
Consider a set of values, e.g. 0, 1, 2,
now imagine two of these sets and a bijective relation between them.
How can I implement this in Swift, encapsulated in a data structure?
Clarification and examples:
An example mapping could look like this:
0 <-> 1
1 <-> 2
2 <-> 0
The classic bidirectional hashmap doesn't fit to this use case well, as the values on both sides are non-unique.
The data structure should allow querying from both sides:
let ds = DS(...)
let ds.right(from: 1) // 2
let ds.left(from: 0) // 2
What is the simplest way of implementing such data structure? What existing data types I can base my implementation on?
UPDATE:
What does "the values on both sides are non-unique” The values on the "Left" side are unique within that side, as well as the values on the "Right" side. However, if the value is present in one side, it will always be present in the other. Hence, the values are not unique.
Can you give an example with non-unique values, and the expected results of right(from:) and left(from:) in the case of non-uniqueness?
To clarify, all the values the left side has are 0,1,2. The right side also has 0,1,2.
query examples:
ds.rightFrom(left: 2) -> 0
ds.rightFrom(left: 0) -> 1
ds.leftFrom(right: 0) -> 2
ds.leftFrom(right: 1) -> 0
A bijective function from a set to itself is a permutation. If the set consists of consecutive integers starting at zero then the permutation can be represented as an array.
In your case, the mapping from [0, 1, 2] to itself defined by
0 -> 1, 1 -> 2, 2 -> 0
would be represented as the array [1, 2, 0]. The “left-to-right” mapping then becomes a subscript operation:
let perm = [1, 2, 0]
print(perm[1]) // 2
The “right-to-left” mapping is the inverse permutation, and can also be represented as an array:
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
}
(This is just to demonstrate the general idea. Of course you can make this an Array extension method, or define a Permutation type with this and more methods.)
In your example:
if let invPerm = inversePermution(of: perm) {
print(invPerm) // [2, 0, 1]
print(invPerm[2]) // 1
}