сдвига элементов в массиве по индексу

Question

Учитывая массив из п элементов, т.е.

var array = [1, 2, 3, 4, 5]

Я могу написать расширение к Array так что я могу изменить массив для достижения этого результата: [2, 3, 4, 5, 1]:

mutating func shiftRight() { 
    append(removeFirst()) 
    } 

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

Алгоритм прост:

1. Split массив на две части индекса при условии
2. добавить первый массив к концу второго

Есть ли способ, чтобы реализовать его в функциональный стиль?

код я закончил с:

extension Array { 
    mutating func shift(var amount: Int) { 
    guard -count...count ~= amount else { return } 
    if amount < 0 { amount += count } 
    self = Array(self[amount ..< count] + self[0 ..< amount]) 
    } 
} 

Answer 1

Вы можете использовать колебались индексацию и сцепить результаты. Это даст вам то, что вы ищете, с именами, похожими на стандартную библиотеку:

extension Array { 
    func shiftRight(var amount: Int = 1) -> [Element] { 
     assert(-count...count ~= amount, "Shift amount out of bounds") 
     if amount < 0 { amount += count } // this needs to be >= 0 
     return Array(self[amount ..< count] + self[0 ..< amount]) 
    } 

    mutating func shiftRightInPlace(amount: Int = 1) { 
     self = shiftRight(amount) 
    } 
} 

Array(1...10).shiftRight() 
// [2, 3, 4, 5, 6, 7, 8, 9, 10, 1] 
Array(1...10).shiftRight(7) 
// [8, 9, 10, 1, 2, 3, 4, 5, 6, 7] 

Вместо индексации, вы могли бы также вернуться Array(suffix(count - amount) + prefix(amount)) из shiftRight().

Answer 2

С Swift 3, вы можете создать shift(withDistance:) и shiftInPlace(withDistance:) методы с помощью всего нескольких строк кода:

extension Array { 

    func shift(withDistance distance: Int = 1) -> Array<Element> { 
     let offsetIndex = distance >= 0 ? 
      self.index(startIndex, offsetBy: distance, limitedBy: endIndex) : 
      self.index(endIndex, offsetBy: distance, limitedBy: startIndex) 

     guard let index = offsetIndex else { return self } 
     return Array(self[index ..< endIndex] + self[startIndex ..< index]) 
    } 

    mutating func shiftInPlace(withDistance distance: Int = 1) { 
     self = shift(withDistance: distance) 
    } 

} 

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

let array1 = Array(1...10) 
let newArray = array1.shift(withDistance: 3) 
print(newArray) // prints: [4, 5, 6, 7, 8, 9, 10, 1, 2, 3] 

var array2 = Array(1...10) 
array2.shiftInPlace(withDistance: -2) 
print(array2) // prints: [9, 10, 1, 2, 3, 4, 5, 6, 7, 8] 

let array3 = Array(1...10) 
let newArray3 = array3.shift(withDistance: 30) 
print(newArray3) // prints: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 

let array4 = Array(1...10) 
let newArray4 = array4.shift(withDistance: 0) 
print(newArray4) // prints: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 

var array5 = Array(1...10) 
array5.shiftInPlace() 
print(array5) // prints: [2, 3, 4, 5, 6, 7, 8, 9, 10, 1] 

Answer 3

Вслед за Nate Cook answers, мне нужно также перенести массив возвращая обратный порядок, поэтому я сделал:

//MARK: - Array extension 
Array { 
    func shiftRight(amount: Int = 1) -> [Element] { 
     var amountMutable = amount 
     assert(-count...count ~= amountMutable, "Shift amount out of bounds") 
     if amountMutable < 0 { amountMutable += count } // this needs to be >= 0 
     return Array(self[amountMutable ..< count] + self[0 ..< amountMutable]) 
    } 
    func reverseShift(amount: Int = 1) -> [Element] { 
     var amountMutable = amount 
     amountMutable = count-amountMutable-1 
     let a: [Element] = self.reverse() 
     return a.shiftRight(amountMutable) 
    } 

    mutating func shiftRightInPlace(amount: Int = 1) { 
     self = shiftRight(amount) 
    } 

    mutating func reverseShiftInPlace(amount: Int = 1) { 
     self = reverseShift(amount) 
    } 
} 

У нас есть, например:

Array(1...10).shiftRight() 
// [2, 3, 4, 5, 6, 7, 8, 9, 10, 1] 
Array(1...10).shiftRight(7) 
// [8, 9, 10, 1, 2, 3, 4, 5, 6, 7] 
Array(1...10).reverseShift() 
// [2, 1, 10, 9, 8, 7, 6, 5, 4, 3] 
Array(1...10).reverseShift(7) 
// [8, 7, 6, 5, 4, 3, 2, 1, 10, 9] 

Answer 4

Я принял удар по написанию некоторых расширений для этого. Он имеет несколько приятных функций:

• Смещение на величину, превышающую count, вызывает обертывание.
• Shifting отрицательные суммы переворачивает направление
• публично разоблачений функции как бит сдвига двоичных операторов (<<, <<=, >>, >>=)

extension Array { 
    func shiftedLeft(by rawOffset: Int = 1) -> Array { 
     let clampedAmount = rawOffset % count 
     let offset = clampedAmount < 0 ? count + clampedAmount : clampedAmount 
     return Array(self[offset ..< count] + self[0 ..< offset]) 
    } 

    func shiftedRight(by rawOffset: Int = 1) -> Array { 
     return self.shiftedLeft(by: -rawOffset) 
    } 

    mutating func shiftLeft(by rawOffset: Int = 1) { 
     self = self.shiftedLeft(by: rawOffset) 
    } 

    mutating func shiftRight(by rawOffset: Int = 1) { 
     self = self.shiftedRight(by: rawOffset) 
    } 
} 

//Swift 3 
func << <T>(array: [T], offset: Int) -> [T] { return array.shiftedLeft(by: offset) } 
func >> <T>(array: [T], offset: Int) -> [T] { return array.shiftedRight(by: offset) } 
func <<= <T>(array: inout [T], offset: Int) { return array.shiftLeft(by: offset) } 
func >>= <T>(array: inout [T], offset: Int) { return array.shiftRight(by: offset) } 

/*// Swift 2.2 
func << <T>(array: [T], offset: Int) -> [T] { return array.shiftedLeft(by: offset) } 
func >> <T>(array: [T], offset: Int) -> [T] { return array.shiftedRight(by: offset) } 
func <<= <T>(inout array: [T], offset: Int) { return array.shiftLeft(by: offset) } 
func >>= <T>(inout array: [T], offset: Int) { return array.shiftRight(by: offset) }*/ 

Вы можете увидеть его в действие here.

Вот более общее решение, которое реализует эту функцию лениво для любого типа, который отвечает требования:

extension RandomAccessCollection where 
    Self: RangeReplaceableCollection, 
    Self.Index == Int, 
    Self.IndexDistance == Int { 
    func shiftedLeft(by rawOffset: Int = 1) -> RangeReplaceableSlice<Self> { 
     let clampedAmount = rawOffset % count 
     let offset = clampedAmount < 0 ? count + clampedAmount : clampedAmount 
     return self[offset ..< count] + self[0 ..< offset] 
    } 

    func shiftedRight(by rawOffset: Int = 1) -> RangeReplaceableSlice<Self> { 
     return self.shiftedLeft(by: -rawOffset) 
    } 

    mutating func shiftLeft(by rawOffset: Int = 1) { 
     self = Self.init(self.shiftedLeft(by: rawOffset)) 
    } 

    mutating func shiftRight(by rawOffset: Int = 1) { 
     self = Self.init(self.shiftedRight(by: rawOffset)) 
    } 

    //Swift 3 
    static func << (c: Self, offset: Int) -> RangeReplaceableSlice<Self> { return c.shiftedLeft(by: offset) } 
    static func >> (c: Self, offset: Int) -> RangeReplaceableSlice<Self> { return c.shiftedRight(by: offset) } 
    static func <<= (c: inout Self, offset: Int) { return c.shiftLeft(by: offset) } 
    static func >>= (c: inout Self, offset: Int) { return c.shiftRight(by: offset) } 
} 

Answer 5

В Objective C, вы можете просто получить левый сдвинут массив как это:

- (NSMutableArray *)shiftedArrayWithOffset:(NSInteger)offset 
{ 
    NSMutableArray *bufferArray = [[NSMutableArray alloc] initWithArray:originalArray]; 
    for (int i = 0; i < offset; i++) 
    { 
     id object = [bufferArray firstObject]; 
     [bufferArray removeObjectAtIndex:0]; 
     [bufferArray addObject:object]; 
    } 
    return bufferArray; 
} 

Answer 6

Самый быстрый способ (но занимает двойную память!):

вход:

var arr = [1,2,3,4,5] 
let k = 1 (num steps to rotate) 
let n = arr.count (a little but faster) 

вращение ЛЕВЫЙ:

var temp = arr 
    for i in 0..<n { 
     arr[(n-i+k)%n] = temp[i] 
    } 

result: [2, 1, 4, 3, 5] 

вращения RIGHT:

var temp = arr 
    for i in 0..<n { 
    arr[(i+k)%n] = temp[i] 
    } 

result: [4, 1, 2, 3, 5] 

Answer 7

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

extension Array 
{ 
    mutating func rotateLeft(by rotations:Int) 
    { 
     let _ =            // silence warnings 
     (1..<Swift.max(1,count*((rotations+1)%(count+1)%1))) // will do zero or count - 1 swaps 
     .reduce((i:0,r:count+rotations%count))    // i: swap index r:effective offset 
     { s,_ in let j = (s.i+s.r)%count      // j: index of value for position i 
     swap(&self[j],&self[s.i])       // swap to place value at rotated index 
     return (j,s.r)          // continue with next index to place 
     } 
    } 
} 

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

Использование отрицательных значений для вращения в другом направлении (вправо).

Вращение массива из 3 элементов на 10 похоже на вращение на 1, первые девять вращений вернут его в исходное состояние (но мы не хотим перемещать элементы более одного раза).

Вращение массива 5 элементов справа на 3, то есть rotateLeft (by: -3) эквивалентно rotateLeft (по: 2). Это «эффективное смещение» функции учитывает это.