Как выполнять итерационные перемещения элементов в массиве в Swift

Question

Допустим, у нас есть массив:

var scrambledAlphabet = ["B", "C", "D", "E", "H", "F", "G", "A"]

, и мы хотим отсортировать его, переместив два элемента: элемент 7 («A») в местоположение 0 и элемент 4 ( "H") до 7, описанного массивом кортежей:

var moves = [(7, 0), (4, 7)]

Итак, желаемый результат:

[«A», «B», «C», «D», «E», «F», «G», «H»]

Спонтанное, которое легко решить с помощью этого:

var scrambledAlphabet = ["B", "C", "D", "E", "H", "F", "G", "A"]
var moves = [(7, 0), (4, 7)]

for (i, j) in moves  {
    scrambledAlphabet.insert(scrambledAlphabet.remove(at: i), at: j)
}
print(scrambledAlphabet)

Но не работает. Результат:

[«A», «B», «C», «D», «H», «F», «G», «E»]

Проблема в том, что как только первый элемент перемещается, индекс следующего элемента изменяется. Итак, как лучше всего с этим справиться? Я нахожу это на удивление трудным. Любая помощь приветствуется.

Ограничение состоит в том, что две переменные, scrambledAlphabet и moves, должны иметь возможность увеличиваться до любого числа.

И еще одно важное замечание: перемещение по индексу (второе число в кортеже) относится к старому массиву, не вновь созданному. Итак, входные данные ["B", "C", "E", "D", "H", "F", "G", "A"] и [(7, 0), (4, 7), (3, 2)] должны привести к:

[«A», «B», «C», «D», «E», «F» , "G", "H"]

Извините за путаницу по поводу этого последнего бита.

Answer 1

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

func scramble<T>(array: [T], moves: [(Int, Int)]) -> [T] {

    // Moves sorted by increasing destination index:
    var moves = moves.sorted(by: { $0.1 < $1.1 })

    // All indices which are not the source of a move:
    let sourceIndices = Set(moves.map { $0.0 })
    var otherIndices = array.indices.filter { !sourceIndices.contains($0)}

    // Fill each position with an element of a move source,
    // or one of the "other" array elements:
    return array.indices.map {
        if let (from, to) = moves.first, $0 == to {
            moves.removeFirst()
            return array[from]
        } else {
            return array[otherIndices.removeFirst()]
        }
    }
}

Пример 1:

print(scramble(array: ["B", "C", "D", "E", "H", "F", "G", "A"],
               moves:  [(7, 0), (4, 7)]))
// ["A", "B", "C", "D", "E", "F", "G", "H"]

Пример 2:

print(scramble(array: [0, 1, 2, 3, 4, 5, 6, 7],
               moves: [(1, 6), (7, 2), (3, 5), (5, 3), (4, 7)]))
// [0, 2, 7, 5, 6, 3, 1, 4]

Answer 2

Я подумал об этом (IMO немного неуклюжем) решении:

var newArray = Array(repeating: "", count: scrambledLetters.count)
for (start, end) in moves {
    newArray[end] = scrambledLetters[start]
    scrambledLetters[start] = ""
}
var scrambledLetterIndex = -1

func setScrambledLetterIndexToNextNonEmptyString() {
    scrambledLetterIndex += 1
    while scrambledLetterIndex < scrambledLetters.count - 1 && scrambledLetters[scrambledLetterIndex].isEmpty {
        scrambledLetterIndex += 1
    }
}

for i in newArray.indices {
    if newArray[i] == "" {
        setScrambledLetterIndexToNextNonEmptyString()
        newArray[i] = scrambledLetters[scrambledLetterIndex]
    }
}

scrambledLetters = newArray

По сути, я сначала создал новый массив, «вынул» строки, которые нужно переместить, и поместил их в правильная позиция в новом массиве. Это то, что сделал первый для l oop.

После первого для l oop два массива будут выглядеть так:

scrambledLetters:   ["B", "C", "D", "E", "", "F", "G", ""]
newArray:           ["A", "", "", "", "", "", "" , "H"]

Затем я медленно скопировал каждое non -пустой элемент в массиве зашифрованных букв в пустые места нового массива.

Поскольку это решение использует пустую строку, оно не будет работать, если входной домен содержит пустые строки. Если это так, вам придется использовать что-то вроде [String?].

Answer 3

Я решил это, объединив элементы в массиве с их исходным индексом и отсортировав ходы, чтобы вставки не нарушали порядок. Также весь код перемещен в расширение массива:

extension Array where Element : Equatable  {

    mutating func moveItem(from fromIndex: Int, to toIndex: Int) {
        self.insert(self.remove(at: fromIndex), at: toIndex)
    }

    func performIteratedMoves(_ moves: [(Int, Int)]) -> [Element] {
        var array = self
        let enumeratedArray =  array.enumerated().map{ (index: $0, item: $1) }
        let sortedMoves = moves.sorted { $0.1 > $1.1 }

        for (i, j) in sortedMoves {
            guard let (_, item) = enumeratedArray.first(where:{ $0.index == i }), let correctIndex = array.firstIndex(where:{ $0 == item }) else { continue }
            array.moveItem(from: correctIndex, to: j)
        }
        return array
    }
}

Использование:

var scrambledAlphabet = ["B", "C", "E", "D", "H", "F", "G", "A"]
var moves = [(7, 0), (4, 7), (3, 2)]
print(scrambledAlphabet.performIteratedMoves(moves))

// ["A", "B", "C", "D", "E", "F", "G", "H"]