Алгоритм сортировки элементов с использованием относительных предикатов - PullRequest
Новая
       35

Алгоритм сортировки элементов с использованием относительных предикатов

0 голосов
/ 02 апреля 2020

У меня есть набор элементов, каждый из которых имеет относительные предикаты, которые я хочу использовать для правильной сортировки группы. Каков наилучший алгоритм / подход для правильной сортировки следующей группы по

[a, c, b, e, f, d] или [c, a, b, e, f, d]? 

[
  a,
  b, // >a and <e
  c, // =a
  d, // >f
  e, // <f
  f, // >a
]

Я настроил свои предикаты в Swift, выполнив следующее : 

import Foundation

class Item {

  let id: String
  let relations: [String: ComparisonResult]

  var description: String {
    return id
  }

  init(id: String, relations: [String: ComparisonResult] = [:]) {
     self.id = id
     self.relations = relations
  }

}

let items = [
  Item(id: "a"),
  Item(id: "b", relations: ["a": .orderedDescending, "e": .orderedAscending]),
  Item(id: "c", relations: ["a": .orderedSame]),
  Item(id: "d", relations: ["f": .orderedDescending]),
  Item(id: "e", relations: ["f": .orderedAscending]),
  Item(id: "f", relations: ["a": .orderedDescending]),
]

print(items) // [a, b, c, d, e, f, g]
print(items.sorted) // [a, c, b, e, f, d]

1 Ответ

0 голосов
/ 03 апреля 2020

Используя Александр Восстановите предложение Моники в комментариях. Я создал решение теории графов, которое работает так, как нужно ниже! 

import Foundation

extension ComparisonResult {

    var inverse: ComparisonResult {
        switch self {
        case .orderedAscending: return .orderedDescending
        case .orderedDescending: return .orderedAscending
        default: return .orderedSame
        }
    }

}

extension ComparisonResult: CustomStringConvertible {

    public var description: String {
        switch self {
        case .orderedAscending: return "<"
        case .orderedDescending: return ">"
        default: return "="
        }
    }

}

class Graph {

    var nodes = [String]()
    var arcs = [String: [String: ComparisonResult]]()

    init(nodes: [String] = []) {
        self.nodes = nodes
    }

    func connect(_ a: String, _ b: String, _ relation: ComparisonResult) {
        var arcs = self.arcs[a] ?? [:]
        arcs[b] = relation
        self.arcs[a] = arcs
        arcs = self.arcs[b] ?? [:]
        arcs[a] = relation.inverse
        self.arcs[b] = arcs
    }

    func connect(_ a: String, _ b: String, _ relation: String) {
        switch relation {
        case "<": connect(a, b, .orderedAscending)
        case ">": connect(a, b, .orderedDescending)
        default: connect(a, b, .orderedSame)
        }
    }

    func compare(_ a: String, _ b: String, _ excluding: [String] = []) -> ComparisonResult {
        if let arcs = self.arcs[a] {
            if let value = arcs[b] { return value }
            for (id, relation) in arcs {
                guard !excluding.contains(id), relation != .orderedDescending else { continue }
                return compare(id, b, excluding + [a, b, id])
            }
        }
        return .orderedSame
    }

    func sorted(reversed: Bool = false) -> [String] {
        return nodes.sorted {
            if reversed { return self.compare($0, $1) != .orderedAscending }
            return self.compare($0, $1) == .orderedAscending
        }
    }

}

extension Graph: CustomStringConvertible {

    var description: String {
        var strings = [String]()
        for (id, map) in arcs {
            strings.append("\(id) -> \(map)")
        }
        return strings.joined(separator: "\n")
    }

}

let graph = Graph(nodes: ["a","b","c","d","e","f"])
graph.connect("b", "a", ">")
graph.connect("b", "e", "<")
graph.connect("c", "a", "=")
graph.connect("e", "f", "<")
graph.connect("f", "a", ">")
graph.connect("d", "f", ">")

print(graph)
print(graph.nodes) // [a, b, c, d, e, f]
print(graph.sorted()) // [a, c, b, e, f, d]
print(graph.sorted(reversed: true)) // [d, f, e, b, c, a]
...