Поиск алгоритма для инвертирования (реверс? зеркало? выверните наизнанку), DAG

Попробуйте разместить на игровой площадке следующее:

let sampleResponse = """
{"gameID":13,"drawID":4178,"drawDate":"2019,04,13,20,00,00","levels":[10,0,0,0,0,0,0,9,0,0,0,0,0,8,0,0,0,0,7,0,0,0,6,0,0,0,5,0,0,4,0,0,3,0,2],"wagers":[5,10,20,30,50,100],"correct":[10,9,8,7,6,5,0,9,8,7,6,5,0,8,7,6,5,4,7,6,5,4,6,5,4,3,5,4,3,4,3,2,3,2,2],"odds":[200000,5000,200,20,4,1,1,50000,1100,50,8,2,1,10000,240,20,3,1,2400,100,10,1,420,20,3,1,200,9,1,35,2,1,18,1,7],"winners":[0,5,27,196,959,3308,1556,1,0,8,56,219,294,1,3,59,305,1043,5,10,77,386,2,58,393,1340,16,108,548,44,433,1682,126,971,259],"drawNumbers":[1,13,23,30,40,42,43,48,49,50,51,52,53,54,55,56,60,61,63,65],"unsortedDrawNumbers":[63,52,13,56,53,30,54,23,65,55,61,1,51,42,60,43,48,49,50,40],"turnover":795865}
"""

У вас странный формат даты, поэтому вам нужно придумать средство форматирования даты, чтобы справиться с этим, который я написал ниже ...

extension DateFormatter {
    static let weirdDateFormat: DateFormatter = {
        let formatter = DateFormatter()
        formatter.dateFormat = "yyyy,MM,dd,HH,mm,ss"
        formatter.calendar = Calendar(identifier: .gregorian)
        // add time zone, etc. here
        return formatter
    }()
}

Далее, мы используем Codable структуру для декодирования данных. Вот то, что я придумал, основываясь на предоставленной вами выборке.

struct ResponseObject: Codable {
    let gameID: Int
    let drawID: Int
    let drawDate: Date // Correct this to date
    let levels: [Int]
    let wagers: [Int]
    let correct: [Int]
    let odds: [Int]
    let winners: [Int]
    let drawNumbers: [Int]
    let unsortedDrawNumbers: [Int]
    let turnover: Int
}

Теперь мы декодируем JSON. Вы заметите, что я использовал расширение weirdDateFormat выше для отформатированного dateDecodingStrategy.

let jsonDecoder = JSONDecoder()
jsonDecoder.dateDecodingStrategy = .formatted(.weirdDateFormat)
if let data = sampleResponse.data(using: .utf8) {
    do {
        let response = try jsonDecoder.decode(ResponseObject.self, from: data)
        print(response)
    } catch {
        print(error)
    }
}

Вот некоторые ресурсы для использования протокола кодирования:

Форматы декодирования даты

Примеры кодирования

9
задан bendin 27 February 2009 в 14:39
поделиться

4 ответа

Пересеките создание графика ряд обратных краев и списка вершин.

Выполните топологический вид обратных краев с помощью листа (которые являются теперь корнем), узлы для запуска с.

Создайте обратный график на основе обратных краев, начинающих с конца отсортированного списка. Поскольку узлы создаются в обратном топологическом порядке, Вы, как гарантируют, создадите дочерние элементы данного узла прежде, чем создать узел, так создание неизменного представления возможно.

Это - или O (N) при использовании структур для промежуточного представления, которые отслеживают все ссылки в обоих направлениях, связанных с узлом или O (NlnN), если Вы используете сортировку для нахождения всех ссылок узла. Для маленьких графиков или языков, которые не страдают от переполнений стека, можно просто создать график лениво вместо того, чтобы явно выполнить топологический вид. Таким образом, это зависит немного, что Вы реализуете все это в том, насколько отличающийся это было бы.

A -> (B -> G, C -> (E -> F, D -> F))

original roots: [ A ]
original links: [ AB, BG, AC, CE, EF, CD, DF ] 
reversed links: [ BA, GB, CA, EC, FE, DC, FD ]
reversed roots: [ G, F ]
reversed links: [ BA, CA, DC, EC, FE, FD, GB ] (in order of source)
topologically sorted: [ G, B, F, E, D, C, A ]
construction order : A, C->A, D->C, E->C, F->(D,E), B->A, G->B
9
ответ дан 4 December 2019 в 15:26
поделиться

Просто сделайте маркировку поиска в глубину, где Вы уже были, и каждый раз, когда Вы пересекаете стрелку, Вы добавляете реверс к своему результату DAG. Добавьте листы как корни.

2
ответ дан 4 December 2019 в 15:26
поделиться

Мое интуитивное предложение состояло бы в том, чтобы выполнить Глубину Первый обход Вашего графика и создать Ваш зеркальный график одновременно.

При пересечении каждого узла создайте новый узел в зеркальном графике и создайте край между ним и его предшественником в новом графике.

В какой-либо точке при достижении узла, который не имеет никаких детей, отметьте ее как корень.

2
ответ дан 4 December 2019 в 15:26
поделиться

Поиск в глубину смог генерировать то, что Вы после: Отметьте свой путь через дерево и каждый раз, когда Вы пересекаете, добавляет реверс к получающемуся DAG (листы являются корнями).

-1
ответ дан 4 December 2019 в 15:26
поделиться
Другие вопросы по тегам:

Похожие вопросы: