Swift: сопоставить набор значений от A до B и от B до A - PullRequest
Новая
       72

Swift: сопоставить набор значений от A до B и от B до A

0 голосов
/ 24 июня 2019

Задача:

Рассмотрим набор значений, например, 0, 1, 2, теперь представьте два из этих наборов и биективную связь между ними.

Как я могу реализовать это в Swift, инкапсулированном в структуру данных?

Разъяснение и примеры:

Пример отображения может выглядеть так: 

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

Классическая двунаправленная хэш-карта не подходит для этого варианта использования, так как значения с обеих сторон не уникальны.

Структура данных должна позволять запрашивать с обеих сторон: 

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

Какой самый простой способ реализации такой структуры данных?На каких существующих типах данных я могу основывать свою реализацию?

ОБНОВЛЕНИЕ:

Что означает «значения с обеих сторон не являются уникальными» Значения на левой стороне уникальны для этой стороны, а также значения на правой стороне, однако, если значение присутствует на одной стороне, оно всегда будет присутствовать на другой.значения не являются уникальными.

Можете ли вы привести пример с неуникальными значениями и ожидаемыми результатами справа (от :) и слева (от :) в случае неединственности?

Для пояснения, все значения, которые имеет левая сторона, равны 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

Ответы [ 3 ]

1 голос
/ 25 июня 2019

Биективная функция от набора к себе - это перестановка . Если набор состоит из последовательных целых чисел, начинающихся с нуля, то перестановка может быть представлена ​​в виде массива.

В вашем случае отображение из [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
}
0 голосов
/ 24 июня 2019

Код, с которым я закончил: 

import Foundation

public struct BidirectionalMapNonUnique<Left, Right> where Left: Hashable, Right: Hashable {
    private let ltr: [Left: Right]
    public let rtl: [Right: Left]

    public init(_ ltrMapping: [Left: Right]) {
        var rtlPending = [Right: Left]()
        for (key, value) in ltrMapping {
            rtlPending[value] = key
        }
        self.ltr = ltrMapping
        self.rtl = rtlPending
    }

    public func leftFrom(right: Right) -> Left {
        return rtl[right]!
    }

    public func rightFrom(left: Left) -> Right {
        return ltr[left]!
    }
}


let example = BidirectionalMapNonUnique<Int, Int>([0:10, 1:11, 2:12])

print(example.leftFrom(right: 11)) // Prints 1
print(example.rightFrom(left: 0)) // Prints 10
0 голосов
/ 24 июня 2019

Вы можете использовать zip(_:_:) на array, т.е. 

let arr1 = [0,1,2]
let arr2 = [01,2,0]

let result = Array(zip(arr1,arr2))

print(result) //Output: [(0, 1), (1, 2), (2, 0)]
...