Shift elements in array by index

Question

Given array of n elements, i.e.

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

I can write an extension to the Array so I can modify array to achieve this output: [2, 3, 4, 5, 1]:

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

Is there a way to implement such a function that would shift array by any index, positive or negative. I can implement this function in imperative style with if-else clauses, but what I am looking for is functional implementation.

The algorithm is simple:

1. Split array into two by the index provided
2. append first array to the end of the second

Is there any way to implement it in functional style?

The code I've finished with:

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])
  }
}

Solution 1

You can use ranged subscripting and concatenate the results. This will give you what you're looking for, with names similar to the standard library:

extension Array {
    func shiftRight(var amount: Int = 1) -> [Element] {
        guard count > 0 else { return self }
        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]

Instead of subscripting, you could also return Array(suffix(count - amount) + prefix(amount)) from shiftRight().

Solution 2

With Swift 5, you can create shift(withDistance:) and shiftInPlace(withDistance:) methods in an Array extension with the following implementation in order to solve your problem:

extension Array {

    /**
     Returns a new array with the first elements up to specified distance being shifted to the end of the collection. If the distance is negative, returns a new array with the last elements up to the specified absolute distance being shifted to the beginning of the collection.

     If the absolute distance exceeds the number of elements in the array, the elements are not shifted.
     */
    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])
    }

    /**
     Shifts the first elements up to specified distance to the end of the array. If the distance is negative, shifts the last elements up to the specified absolute distance to the beginning of the array.

     If the absolute distance exceeds the number of elements in the array, the elements are not shifted.
     */
    mutating func shiftInPlace(withDistance distance: Int = 1) {
        self = shift(withDistance: distance)
    }

}

Usage:

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

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

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

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

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

var array = [Int]()
array.shiftInPlace(withDistance: -2)
print(array) // prints: []

Solution 3

I took a stab at writing some extensions for this. It has some nice features:

• Shifting by an amount greater than count causes a wrap-around.
• Shifting by negative amounts flips the direction
• Exposes functions as the bit-shift binary operators (<<, <<=, >>, >>=)

extension Array {
    public 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])
    }

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

    public mutating func shiftLeftInPlace(by rawOffset: Int = 1) {
        if rawOffset == 0 { return /* no-op */ }

        func shiftedIndex(for index: Int) -> Int {
            let candidateIndex = (index + rawOffset) % self.count

            if candidateIndex < 0 {
                return candidateIndex + self.count
            }

            return candidateIndex
        }

        // Create a sequence of indexs of items that need to be swapped.
        //
        // For example, to shift ["A", "B", "C", "D", "E"] left by 1:
        // Swapping 2 with 0: ["C", "B", "A", "D", "E"]
        // Swapping 4 with 2: ["C", "B", "E", "D", "A"]
        // Swapping 1 with 4: ["C", "A", "E", "D", "B"]
        // Swapping 3 with 1: ["C", "D", "E", "A", "B"] <- Final Result
        //
        // The sequence here is [0, 2, 4, 1, 3].
        // It's turned into [(2, 0), (4, 2), (1, 4), (3, 1)] by the zip/dropFirst trick below.
        let indexes = sequence(first: 0, next: { index in
            let nextIndex = shiftedIndex(for: index)
            if nextIndex == 0 { return nil } // We've come full-circle
            return nextIndex
        })

        print(self)
        for (source, dest) in zip(indexes.dropFirst(), indexes) {
            self.swapAt(source, dest)
            print("Swapping \(source) with \(dest): \(self)")
        }
        print(Array<(Int, Int)>(zip(indexes.dropFirst(), indexes)))
    }

    public mutating func shiftRightInPlace(by rawOffset: Int = 1) {
        self.shiftLeftInPlace(by: rawOffset)
    }
}

public func << <T>(array: [T], offset: Int) -> [T] { return array.shiftedLeft(by: offset) }
public func >> <T>(array: [T], offset: Int) -> [T] { return array.shiftedRight(by: offset) }
public func <<= <T>(array: inout [T], offset: Int) { return array.shiftLeftInPlace(by: offset) }
public func >>= <T>(array: inout [T], offset: Int) { return array.shiftRightInPlace(by: offset) }

You can see it in action here.

Here is a more general solution, which implements this functionality lazily for any type that meets the requirements:

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) }
}

Solution 4

An easy solution,

 public func solution(_ A : [Int], _ K : Int) -> [Int] {

    if A.count > 0 {
        let roundedK: Int = K % A.count

        let rotatedArray = Array(A.dropFirst(A.count - roundedK) + A.dropLast(roundedK))

        return rotatedArray
    }

    return []
}

Solution 5

I know I late to the party, but this answer based on the question works great?

extension Array {
  mutating func shiftRight(p: Int) {
    for _ in 0..<p {
      append(removeFirst())
    }
  }
}

start [5, 0, 4, 11, 0]
shift [5, 0, 4, 11, 0] shift 0
shift [0, 4, 11, 0, 5] shift 1
shift [4, 11, 0, 5, 0] shift 2
shift [11, 0, 5, 0, 4] shift 3

Even better, if you ask it to shift more elements than there are in the array, it simply keeps circling.

View more solutions

Comments

[Richard Topchii]

Great solution. The function I've ended up is a bit different, but I especially like how you treat shift if amount of shift is negative.

[Richard Topchii]

I've added the code I've finished with to my question. It's a bit different, but the idea is exactly the same.

[Sebastian Hojas]

Neat solution! I would rename the function thought, as the shift does not happen in place. I understand though that this is meant to imply its mutating characteristic.

[Richard Topchii]

The question was about implementation in Swift. To initialize NSMutableArray using NSArray it's possible to use [array mutableCopy]; method, it is shorter.

[mfaani]

1. what does ~= mean? I couldn't find any documentation on it? Likely it means return true if an amount is within a range. right? 2. Also I don't see where shiftRightInPlace is used. 3 concatenate the results. you mean concatenate 2 arrays by a simple + right?

[veaceslav.makarov]

Richard, if you use copy - you will receive copy, by copying pointers, not the new array. So your shorter method will break the logic ;)

[mfaani]

Kindly can you answer my comment?

[Alfishe]

Principle is clear, but you've provided incorrect code. Both sequences [2, 1, 4, 3, 5] and [4, 1, 2, 3, 5] are not rotations.

[Glenn Posadas]

Hello, I know this was posted around 5 years ago, but I'd like to ask, this solution of yours worked perfect on Hackerrank, but I wonder why it won't work if I set distance to 99 for array of [1,2,3,4,5,6]?

[muhasturk]

This solution will not work if u shift distance by more than array size. XCTest will be failed. func testShift() { var holder = [1,2,3,4] holder.shiftInPlace() XCTAssertEqual(holder, [2,3,4,1]) holder.shiftInPlace(withDistance: -2) XCTAssertEqual(holder, [4,1,2,3]) holder.shiftInPlace(withDistance: 5) XCTAssertEqual(holder, [2,3,4,1]) }

[Imanou Petit]

@muhasturk This is by design to mimic the behaviour of prefix(_:). The third example already shows this. I've added some comments to make it clearer.

[MrAn3]

@Honey In this context It means just what you said: More details about it can be found on: stackoverflow.com/questions/38371870/operator-in-swift

[D6mi]

@ImanouPetit, a cool solution indeed! I would only suggest to rename the methods, so it's more in line with the existing Swift APIs. shift to shifted and shiftInPlace to shift. See the sorting methods for comparison.

[Richard Topchii]

Great solution, but it doesn't allow shifting left and it's actually mutating the array mutliple times, so this should have a horrible complexity

[user3069232]

Absolutely, the complexity from hell :) use only for very small arrays :)

[Richard Topchii]

Maybe you could rewrite it so that it still keeps cycling, but doesn't suffer from this complexity? Basically, my question was all about not having to repeat removeFirst() and append multiple times and making it more elegant :)

[user3069232]

Richard, the answer to your question lies here. github.com/apple/swift-algorithms.

[Richard Topchii]

Nice, the question is from 2015 when Swift Algorithms weren't announced